题解 P2354 【[NOI2014]随机数生成器】

· · 题解

说在前面

做之前：NOI2014？？不应该黑题吗？？

做之后：好吧，还真应该降为紫题。

Description

题目好像说这么多没啥用，还是简化一下。

给你五个数 x0,a,b,c,d,让你构造两个序列。

X_i=(a\times X_{i-1}^2+b\times X_{i-1}+c)\mod d T_i=i

输入 n,m。

然后你要对 T_1~T_{n\times m} 做以下事情。

交换 T_i 和 T_{X_i\mod i}。

最后输入 q。

输入q 个 u,v，交换 T_u 和 T_v。

接着把 T 数组按照从左到右，从上到下的顺序放入一个 n\times m 的棋盘。

问：

从左上角走到右下角组成的序列排序后最小字典序的序列是什么？

Solution

其实不要被紫题所迷惑，其实这就是一道简单的贪心题。

由于要求字典序最小，所以我们肯定能走最小就走最小。

我们可以预处理出 1 ~ n\times m 的数在哪个位置，然后判断一下这个数是否在可以选的范围内。

如果能选，就要修改相应不能选的位置：

设 l_i,r_i 表示第i行能选的范围是 l_i~r_i，然后如果我们选了 (x,y) 这个位置的数，那么红色位置的数就不能选。

因为从(x,y)不可能再走到红色区域。然后依次修改l，r即可。

Code

#include<cstdio>
#include<algorithm>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
using namespace std;
int n,m,q,x[25000001],t[25000001],u,v,l[5001],r[5001],tot;
long long a,b,c,d;
int main()
{
    scanf("%d%lld%lld%lld%lld",&x[0],&a,&b,&c,&d);
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=n*m;i++)
        x[i]=(x[i-1]*(a*x[i-1]+b)+c)%d,t[i]=i;
    for (int i=1;i<=n*m;i++)
        swap(t[i],t[x[i]%i+1]);
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d",&u,&v);
        swap(t[u],t[v]);
    }
    for (int i=1;i<=n*m;i++)
        x[t[i]]=i;
    for (int i=1;i<=n;i++)
        l[i]=1,r[i]=m;
    for (int i=1;i<=n*m;i++)
    {
        int xx,yy;
        if (x[i]%m==0) xx=x[i]/m;
        else xx=x[i]/m+1;
        yy=x[i]%m;
        if (!yy) yy=m;
        if (yy>=l[xx]&&yy<=r[xx])
        {
            ++tot;
            printf("%d ",i);
            if (tot==n+m-1) return 0;
            for (int j=1;j<=n;j++)
                if (j<xx) r[j]=min(r[j],yy);
                else if (j>xx) l[j]=max(l[j],yy);
        }
    }
    return 0;
}

最后注意一下空间，可以把 X 数组循环用，这样就不用担心空超了。

祝大家早日 AC!