AtCoder Grand Contest 006 C：Rabbit Exercise

题目传送门：https://agc006.contest.atcoder.jp/tasks/agc006_c

题目翻译

数轴上有\(N\)只兔子，从\(1\)到\(N\)编号，每只兔子初始位置是\(x_i\)。现在兔子们要开始做运动，运动都有\(M\)个步骤，对于第\(i\)个步骤，我们用\(a_i\)来形容它，意思是：

在当前步骤中，从左至右数第\(a_i\)只兔子将会跳跃。我们在\(a_i-1\)和\(a_i+1\)两只兔子中等概率的选择一个兔子，假设我们选择的是\(x\)，那么第\(a_i\)只兔子将会跳到数轴上关于第\(x\)只兔子的坐标对称的另一个点上。

比如第\(a_i\)只兔子坐标为\(3\)，第\(x\)只兔子坐标为\(5\)，那么第\(a_i\)只兔子就会跳到\(7\)去。

接下来兔子们要做\(K\)轮这样的运动，请求出最后每个兔子所在坐标的期望。

\(N,M\leqslant 10^5,|x_i|\leqslant 10^9,K\leqslant 10^{18},a_i\in[2,n-1],x_i\)是整数。

题解

这种题目如果想到了就非常好做，可惜我想不到……

假设现在要跳第\(i\)只兔子，那么\(x_i=\frac{1}{2}\times (2*x_{i-1}-x_i)+\frac{1}{2}\times (2*x_{i+1}-x_i)=x_{i-1}+x_{i+1}-x_i\)。

原本这三只兔子分别在：\(x_{i-1},x_i,x_{i+1}\)

现在这三只兔子分别在：\(x_{i-1},x_{i-1}+x_{i+1}-x_i,x_{i+1}\)

看起来怪怪的，上下长度不一，所以我们把这俩序列差分一下。

原本三只兔子坐标差分序列：\(x_{i-1},x_i-x_{i-1},x_{i+1}-x_i\)

现在三只兔子坐标差分序列：\(x_{i-1},x_{i+1}-x_i,x_i-x_{i-1}\)

然后我们发现对于一次跳跃，只是交换了差分数组的两个位置而已……

也就是说，我们可以求出在\(M\)个步骤后差分数组的置换，然后根据置换求出每个位置在\(K\)轮运动之后最后是原数组的哪个元素，最后前缀和加起来就是答案了。

时间复杂度：\(O(N+M)\)

空间复杂度：\(O(N)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

ll k;

int n,m;

int c[maxn];

bool bo[maxn];

ll a[maxn],ans[maxn];//-1e9关于1e9对称就直接爆int了

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int main() {

	n=read();

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

	    scanf("%lld",a+i),c[i]=i;

	m=read();scanf("%lld",&k);

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

		int x=read();

		swap(c[x],c[x+1]);

	}

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

		if(!bo[i]) {

			int u=i,cnt=0,step,goal;

			while(!bo[c[u]])

				bo[c[u]]=1,cnt++,u=c[u];//求循环节大小

			step=k%cnt,goal=u=i;

			for(int j=1;j<=step;j++)

				goal=c[goal];

		    for(int j=1;j<=cnt;j++)

				ans[u]=goal,u=c[u],goal=c[goal];//u和goal相差step步

		}

	for(int i=2;i<=n;i++) {

		int x=ans[i];

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

	}

	ans[1]=a[1];

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

		ans[i]+=ans[i-1],printf("%.1lf\n",(double)ans[i]);

	return 0;

}

巴特西

AtCoder Grand Contest 006 C：Rabbit Exercise

题目翻译

题解

最新文章

热门文章