题目大意：给定一个01串，定义h(s)为将s中所有的"0"变成"1"，所有的"1"变成"10"，求Σh^ai("0")是否是h^m("0")的子串 其中m∈[0,﹢∞)
跪VFK。。。
令Si=h^i("0")
打表会发现Sn=S(n-1)+S(n-2) 但是这个性质对于这题帮助不大 我们暂且忽略这个性质。。。(后面某个地方会用到)
首先我们定义h^-1(s)为h(s)的逆变换 即对于每个"1" 如果后面是“0”就变成“1” 否则变成“0”
由此可发现如果s中含有“00” 那么s是不可以逆变换的
显然s是Sm的子串等价于h^-1(s)是S(m-1)的子串
那么算法就很好想了
我们每次对ΣS(ai)求一次逆变换 这个操作相当于对所有的ai减一
那么如果某个ai是0怎么办呢？
我们讨论：
如果i=1 那么前面必须要有个“1”才能完成逆变换 因此我们不妨把ai改成2 这样相当于在前面加了一个"1"
如果a(i-1)是偶数 那么a(i-1)显然是以0结尾的(由Sn=S(n-1)+S(n-2)可证) 因此s中出现了"00" 输出"NIE"
如果a(i-1)是奇数且>=5 由于S5="10110101"，因此所有S(2k+1) (k>=2)都以"10101"为后缀(由Sn=S(n-1)+S(n-2)可证)
而"101010"逆变换2次后就出现了"00"，故这种情况下直接输出"NIE"
如果a(i-1)=1 那么a1+a0=a2 因此将a(i-1)改为2，删掉ai即可。
如果a(i-1)=3 那么a3+a0="1010"=a2+a2，故将a(i-1)和a(i)都改为2即可。
这样我们就把所有的0都消掉辣。。。然后把每个ai减一就可以了
当n=1时算法结束，输出"TAK"。
然后就开开心心地WA掉啦！
为什么呢？我们可以测下这组样例：
1
2
1 1
s="11"，，这个显然是可以出现的，但是我们逆变换之后居然变成了"00"！
为什么呢？因为结尾的"1"既可以变成"0"又可以变成"1"！
既然可以变成"0"和"1" 那么这个“1”完全不会导致s不出现在Sm中
那么我们删掉这个"1"不就好辣。。。
同理，如果结尾是3那么我们就把这个3变成2
什么你说5？5是不能接“0”的啊忘了么= =
然后这题就做完了。。。太神了QAQ
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 100100using namespace std;int n;int a[M];bool Solve(){int i;while(n>1){if(!a[1]) a[1]=2;if(a[n]==1) n–;else if(a[n]==3) a[n]=2;for(i=n;i;i–)if(!a[i]){if(a[i-1]==1)a[i-1]=2,a[i]=-1;else if(a[i-1]==3)a[i-1]=2,a[i]=2;elsereturn false;}int temp=0;for(i=1;i<=n;i++)if(a[i]!=-1)a[++temp]=a[i];n=temp;for(i=1;i<=n;i++)a[i]–;}return true;}int main(){int T,i;for(cin>>T;T;T–){cin>>n;for(i=1;i<=n;i++)scanf("%d",&a[i]);puts(Solve()?"TAK":"NIE");}return 0;}
微笑拥抱每一天，做像向日葵般温暖的女子。
