自动搬运

查看原文

来自洛谷，原作者为

	ImmortalWatcher Alone but not lonely.

搬运于2025-08-24 21:36:43，当前版本为作者最后更新于2020-02-04 16:23:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

说在前面

做之前：$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$!