1. 题目
2. 题解
数学归纳法
什么鬼?其实就是找规律……
考试找了两个小时没找到规律然后就爆炸了
不难发现当前状态进行 $2^k$次操作后,第 i 位上的数字只受第 $i-2^k$位上的数字和第 $i+2^k$位上的数字,即它们如果相同则第 i 位上的数字为 1,否则为 2。
于是乎,我们就可以做出这题了。
二进制拆分 t,用 lowbit 就行了,总复杂度 $O(nlogt)$
当然我还要引用一段证明:
我们可以把每两次操作看成是一次操作,那么每经过一次操作后所有的硬币的位置都不会变化。很容易可以得知每一次操作时的第 i 个硬币是由上一次操作后的第 i+1 个硬币和第 i-1 个硬币异或而来。那么现在我们来求证在第 2^k 次操作时硬币 i 由初始状态的第 i+2^k 和第 i-2^k 个硬币异或而来。首先当 k=0 时是满足条件的,那么我们假设当 k=n 时满足条件,则当 k=n+1 时每一个硬币 i 由经过 2^n 次操作后的状态的第 i+2^n 和第 i-2^n 个硬币异或而来,设这两个硬币为 x1 和 x2,那么 x1 就是由初始状态的第 i 和第 i+2^(n+1) 个硬币异或而来,x2 是由初始状态的第 i 和第 i-2(n+1) 个硬币异或而来,那么很容易发现第 i 个硬币被抵消掉了,那么当 k=n+1 时第 i 个硬币就由初始状态下的第 i+2^(n+1) 和 i-2^(n+1) 个硬币得到。
但是对于 $2^0=1$我们得特殊处理,我懒得写那么长的代码,搞个栈从大到小搞就行了。
还有,bzoj 上不能输出多余空格,不然会
顺便吐槽一下:网上那些 dalao 们的代码怎么那么像呢?
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,n2,t,a[200005],b[200005],st[70],top;
inline LL lowbit(LL x){return x&-x;}
int main()
{
scanf("%lld%lld",&n,&t),n2=(n<<1);
for(LL i=1;i<=n2;i+=2)scanf("%lld",&a[i]);
while(t)st[++top]=lowbit(t),t-=st[top];
while(top)
{
LL x=st[top],i,l,r;
for(t-=x,memset(b,0,sizeof(b)),i=x==1?2:1,x%=n2;i<=n2;i+=2)
l=((i-x-1+n2)%n2)+1,r=((i+x-1+n2)%n2)+1,b[i]=a[l]==a[r]?1:2;
swap(a,b),top--;
}
for(LL i=1;i<n2;i++)printf("%lld ",a[i]);printf("%lld",a[n2]);
return 0;
}
0 条评论