[BZOJ3671] [NOI2014] random data generator (greedy)

Problem surface

BZOJ

Title Solution

Previous simulation
It's really Chinese Reading Comprehension
Understand the meaning of the topic

And then you'll find that what you want is a greed
Enumeration from small to large, check whether the current number can be selected
If you can choose
It will limit the range that can be reached by other lines
Violent modification
And then we had a good AC

There is no other card for this question
Card space, card format
Are you kidding me?

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int X[5000*5000+10],T[5000*5000+10];
int l[5001],r[5001];
int A,B,C,D,N,M,Q;
int main()
{
    X[0]=read();A=read();B=read();C=read();D=read();
    N=read();M=read();Q=read();
    int tt=N*M;
    for(int i=1;i<=tt;++i)X[i]=(1ll*A*X[i-1]%D*X[i-1]%D+1ll*B*X[i-1]%D+C)%D;
    for(int i=1;i<=tt;++i)T[i]=i;
    for(int i=1;i<=tt;++i)swap(T[i],T[X[i]%i+1]);
    for(int i=1;i<=Q;++i)swap(T[read()],T[read()]);
    for(int i=1;i<=tt;++i)X[T[i]]=i;
    for(int i=1;i<=N;++i)l[i]=1,r[i]=M;
    int tot;
    for(int i=1,j,x,y;i<=tt;++i)
    {
        x=(X[i]+M-1)/M;y=X[i]%M;if(!y)y+=M;
        if(l[x]<=y&&y<=r[x])
        {
            if(i!=1)putchar(' ');
            printf("%d",i);++tot;
            if(tot==N+M-1)break;
            for(j=1;j<x;++j)r[j]=min(r[j],y);
            for(j=x+1;j<=N;++j)l[j]=max(l[j],y);
        }
    }
    return 0;
}

Posted on Thu, 30 Apr 2020 03:31:11 -0700 by fypstudent