bzoj 3671: [Noi2014]随机数生成器【模拟+贪心】

佚名 6年前 (2019-05-08) 随笔 1898人围观抢沙发百度已收录

降智好题
前面随机部分按照题意模拟，然后字典序贪心，也就是记录每个值的位置从1~nm依次看能不能取，能取的话更新行的取值范围（它上面的行一定取的列小于等于这个数取的列，下面行大于等于）

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
int n,m,q,len,p[N*N],id[N*N],l[N],r[N];
long long x,a,b,c,d;
int read()
{
    int r=0,f=1;
    char p=getchar();
    while(p>'9'||p<'0')
    {
        if(p=='-')
            f=-1;
        p=getchar();
    }
    while(p>='0'&&p<='9')
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
int main()
{
    x=read(),a=read(),b=read(),c=read(),d=read(),n=read(),m=read(),q=read(),len=n*m;
    for(int i=0;i<len;i++)
        p[i]=i;
    for(int i=0;i<len;i++) 
        x=(a*x%d*x+b*x+c)%d,swap(p[i],p[x%(i+1)]);
    while(q--) 
    {
        int x=read(),y=read();
        swap(p[x-1],p[y-1]);
    }
    for(int i=0;i<len;i++) 
        id[p[i]]=i;
    for(int i=0;i<m;i++) 
        l[i]=0,r[i]=n-1;
    for(int i=0;i<len;i++)
        if(l[id[i]%m]<=id[i]/m&&r[id[i]%m]>=id[i]/m)
        {
            printf("%d ",i+1);
            for(int j=id[i]%m+1;j<m;j++) 
                l[j]=max(l[j],id[i]/m);
            for(int j=0;j<id[i]%m;j++) 
                r[j]=min(r[j],id[i]/m);
        }
    return 0;
}