【AtCoder】【思维】【置换】Rabbit Exercise

题意：

有n只兔子，i号兔子开始的时候在a[i]号位置。每一轮操作都将若干只兔子依次进行操作：

加入操作的是b[i]号兔子，就将b[i]号兔子移动到关于b[i]-1号兔子现在所在的位置对称的地方，或者是关于b[i]+1号兔子现在所在的位置对称的地方，两者是等概率的。现在给出每一轮操作的兔子编号及顺序，要你求k轮之后每只兔子的位置的期望。保证操作的兔子编号为2~n-1。

数据范围：

1<=n,每一轮的操作数量<=100000

1<=k<=10^18

思路：

看见k这么大，肯定第一反应是有某种周期。

然后来看单独的一轮操作，是一个简单的求解期望的问题。因为选择b[i]-1号兔子和b[i]+1号兔子是等概率的，那么当前这只兔子的期望位置也就是确定的，也就是\(\dfrac{2a[b[i]-1]-a[b[i]]+2a[b[i]+1]-a[b[i]]}{2}=a[b[i]+1]+a[b[i]-1]-a[b[i]]\)。那么对于单轮的操作来说，就变得简单了，就是按顺序将每个兔子的位置变为上面所说的值。

那么考虑有多轮的情况。参考了网上的题解之后，原来是一个很妙的做法，考试的时候我当然没有想到╮(╯﹏╰）╭

观察改变之前的序列与查分之后的序列的差分数组。

之前：a[1],a[2],a[3] -> 差分数组：a[1],a[2]-a[1],a[3]-a[2]

之后：a[1],a[1]+a[3]-a[2],a[3] -> 差分数组：a[1],a[3]-a[2],a[2]-a[1]

神奇的事情发生了！！我们发现差分数组中，竟然是两个位置，也就是i和i+1对换了位置！！

那么到了这里，也就不难发现这就是置换了。将每一个循环求出来，然后对于每一个循环，假设循环长度为T，那么让k%=T，然后讲这个循环涉及到的所有的位置的答案都求出来，然后就做到O(n)。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define MAXN 100000

using namespace std;

typedef long long LL;

vector<int> turns[MAXN+5];//用vector来记录每一个循环

LL k;

int n,m,tcnt=0,chs[MAXN+5],id[MAXN+5],id2[MAXN+5];

//id存的是单次操作之后的状态,id2存的是k次操作之后的操作

LL x[MAXN+5],a[MAXN+5];

LL a2[MAXN+5],x2[MAXN+5];

//a2是之后的差分序列，x2是之后的兔子位置

bool vis[MAXN+5];

int main()

{

//	freopen("rabbit.in","r",stdin);

//	freopen("rabbit.out","w",stdout);

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lld",&x[i]),id[i]=i;

	for(int i=1;i<=n;i++)

		a[i]=x[i]-x[i-1];

	scanf("%d %lld",&m,&k);

	for(int i=1;i<=m;i++)

		scanf("%d",&chs[i]),swap(id[chs[i]],id[chs[i]+1]);

	for(int i=1;i<=n;i++)

	{

		int p=i;

		if(vis[p]==true)

			continue;

		tcnt++;

		while(vis[p]==false)

		{

			vis[p]=true;

			turns[tcnt].push_back(p);

			p=id[p];

		}

	}

	for(int i=1;i<=tcnt;i++)

	{

		int T=(int)turns[i].size();//对于每一个循环单独计算

		int pos=k%T;

		//处理出开头位置所对应的最终位置，然后向后挪到来求出这个循环里的其他元素所对应的答案

		for(int j=0,p=pos;j<(int)turns[i].size();j++,p=(p+1)%T)

			id2[turns[i][j]]=turns[i][p];

	}

	for(int i=1;i<=n;i++)

		a2[i]=a[id2[i]];

	for(int i=1;i<=n;i++)

		x2[i]=x2[i-1]+a2[i];

	for(int i=1;i<=n;i++)

		printf("%lld.0\n",x2[i]);//因为题目要求，强行加一个.0

	return 0;

}

巴特西

【AtCoder】【思维】【置换】Rabbit Exercise

题意：

数据范围：

思路：

代码：

最新文章

热门文章