Luogu

BZOJ

分析

首先要生成这个棋盘。算一下发现按照题意模拟就行了。

这里注意一下是 $x_i\mod i+1$ 而不是 $x_i\mod (i+1)$ ,也就是说其实是 $(x_i\mod i)+1$ 是不是只有我这种菜鸡看错了

然后既然是重排后的字典序最小,那么考虑贪心。

从小到大枚举每个数,如果能选到就选。

考虑如何判断一个数能否选到。显然对于每一行,它会有一个范围 $[l_i,r_i]$ ,表示路径最左从上一行的 $l_i$ 位置下来,最右从 $r_i$ 位置出去。显然如果当前数的 $y$ 不在 $[l_x,r_x]$ 内就不能选到。

那么只要动态维护 $l$ 和 $r$ 就可以判断了。每次选了一个数后直接扫一遍更新即可。

如果不懂可以画图理解。具体实现及细节见代码。

另外这题比较卡空间、卡常,请注意优化。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

namespace IO {
    const int SIZE=(1<<21)+1;
    char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55]; int f,x;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
    
    inline int read() {
        for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
        for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15);
        return x*f;
    }
}
using IO::read;

const int N=5000+10;
const int M=5000*5000+10;

int T[M],X[M],L[N],R[N];

int main() {
    X[0]=read();
    int a=read(),b=read(),c=read(),d=read();
    int n=read(),m=read(),Q=read();
    
    //生成T
    for (re int i=1;i<=n*m;++i)
        X[i]=(1ll*a*X[i-1]%d*X[i-1]%d+1ll*b*X[i-1]%d+c)%d;
    for (re int i=1;i<=n*m;++i) T[i]=i;
    for (re int i=1;i<=n*m;++i) swap(T[i],T[X[i]%i+1]);
    for (re int i=1;i<=Q;++i) {
        int u=read(),v=read();
        swap(T[u],T[v]);
    }
    for (re int i=1;i<=n*m;++i) X[T[i]]=i;
    
    //贪心
    for (re int i=1;i<=n;++i) L[i]=1,R[i]=m;
    for (re int i=1,s=0,*px=X;i<=n*m;++i) {
        ++px; int now=*px;
        int x=(now-1)/m+1,y=now%m?now%m:m;
        if (L[x]<=y&&y<=R[x]) {
            printf("%d ",i);
            ++s; if (s==n+m-1) break;
            for (re int j=1;j<x;++j) R[j]=min(R[j],y);
            for (re int j=n;j>x;--j) L[j]=max(L[j],y);
        }
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 13 PM