P3491 [POI2009] SLW-Words题解

首先容易看出一个性质，这个Hx(0)
是一个具有斐波那契性质的串，然后就一直在想合并的做法，然后直接GG

1h后点开题解，只能大喊妙妙妙（得出结论，我又在混吃等死）

首先看性质，我们来具体地统计一下：

斐波那契性质：Hx=Hx−1+Hx−2
当2|x
时以0
结尾，否则以1
结尾
定义H−1(x)
为H1(x)
的逆操作，不难发现当s′
为s
字串时，H−1(s′)
仍为s
字串
再考虑一些不合法的情况：

出现00
必然不合法
上一条的推论，出现111
必然不合法，因为H−1(111)=00+s
上一条的推论，因为H(111)=101010=10101+0
，因此对于x≥5,2/|x
时，后缀必然为10101
，因此此时后面接上0
必然不合法
然后考虑具体怎么做，我们考虑对于当前的序列{a1,a2,⋯,an−1,an}

当mini∈[1,n]ai>0
时我们可以把所有的ai−1
，运用了前面的第三条性质

然后我们考虑0
怎么处理，显然前面是偶数必然不行（不合法1），前面如果是奇数：

前面是1
，那么1+0=10
，可以合并为2
前面是3
，那么101+0=1010
，可以合并为两个2
根据不合法3，此时必然无解
然后这样就做完了？交一发就得到了0分的好成绩，Why？

我们考虑对于11
，显然是合法的，然而被判了不合法（11→00
）

我们仔细分析一波，原因就在于这个结尾的1
既可以变成0
也可以变成1

那么显然这个1
不管怎么样都不会影响答案，那么直接把他删了就好

同理开头的0
由于前面必然是1
，因此直接转化为2(10)
即可
## 代码如下
```cpp
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,tp,a[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		RI i; bool flag=1; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&a[i]); while (n>1&&flag)
		{
			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; else if (a[i-1]==3) a[i-1]=a[i]=2;
				else { flag=0; break; }
			}
			for (tp=0,i=1;i<=n;++i) if (a[i]) a[++tp]=a[i];
			for (n=tp,i=1;i<=n;++i) --a[i];
		}
		puts(flag?"TAK":"NIE");
	}
	return 0;
}

```

正在渲染内容...