谁是天选之人

众所周知下棋是一个运气游戏，不过好像也是有规律可循的。

Graceful smiling cookies给它的n个棋子标序号，他决定以这些序号决定谁是天选。

最开始每个棋子标号都是0.

它要进行m次标序号。

第i次标序号，它会将第（i X a+b）%n +1个棋子和第(i X b + a)%n +1个棋子之间的棋子都标上序号i。我会告诉你a和b的值，你可以告诉我最后每个棋子的颜色吗？

C++ 解法, 执行用时: 2030ms, 内存消耗: 16008K, 提交时间: 2022-03-12 15:54:00

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int g[N];
int d[N];
int n,m,a,b;
int main(){
	cin>>n>>m>>a>>b;
	for(int i=m;i>=1;i--){
		int x=(i*a+b)%n+1;
		int y=(i*b+a)%n+1;
		if(x>y) swap(x,y);
		for(int j=x;j<=y;j++){
			if(!d[j]){d[j]=y;g[j]=i;}
			else j=d[j];
		}
	}
	for(int i=1;i<=n;i++)	cout<<g[i]<<endl;
	return 0;
}

C(clang11) 解法, 执行用时: 151ms, 内存消耗: 15924K, 提交时间: 2021-03-07 16:08:39

#include<stdio.h>
int f[1000010],vis[1000010];
int main()
{
	int n,m,a,b;
	scanf("%d%d%d%d",&n,&m,&a,&b);
	for(int i=m;i;i--)
	{
		int s=(i*a+b)%n+1,t=(i*b+a)%n+1;
		if(s>t) {int k=s;s=t;t=k;}
		for(int j=s;j<=t;j++)
		{
			if(!vis[j])
			{
				f[j]=i;
				vis[j]=t;
			}
			else j=vis[j];
		}
	}
	for(int i=1;i<=n;i++) printf("%d\n",f[i]);
}

详情