自动搬运

查看原文

来自洛谷，原作者为

	GeXXGe 一刀，我的5年。

搬运于2025-08-24 21:49:30，当前版本为作者最后更新于2023-09-02 10:10:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（本蒟蒻的第一篇题解，有问题请大佬指出，谢谢。

• 题目

  传送门（）

• 分析

  题目很好理解，没什么好分析了罢。

• 首先来看性质：

  1. 斐波那契性质： $H^x=H^{x-1}+H^{x-2}$
  2. 定义 $H^{-1}(x)$ 为 $H^1(x)$ 的逆操作，不难发现当 $s′$ 为 $s$ 字串时，$H^{-1}(s$$′)$ 仍为 $s$ 字串

• 我们可以不断的将连接起来的串进行逆转换。

• 如果当前序列仅剩一个元素则为可行。

• 如果在序列中存在一个元素 $=0$，则如果他前面的元素 $\ne 1$ 或 $3$，则返回 $0$。

• 再考虑一些不合法的情况：

  1. 出现 $00$ 必然不合法
  2. 上一条的推论，出现 $111$ 必然不合法，因为 $H^{-1}(111)=00+s$
  3. 上一条的推论，因为 $H(111)=101010=10101+0$，因此对于 $x≥5$ 时，后缀必然为 $10101$，因此此时后面接上 $0$ 必然不合法

• 代码

我相信没几个人会喜欢上面的一通分析的吧，那么，你们喜欢的代码来了——

#include <bits/stdc++.h>
using namespace std;
int n;
const int N=100100;
int a[N];
int check()
{
    while(n>1)
    {
        if(!a[1])
		{
			a[1]=2;
		}
        if(a[n]==1)
		{
			a[n]=-1;
		}
        else if(a[n]==3)
		{
			a[n]=2;
		}
        for(int i=2;i<=n;i++)
        {
           if(!a[i])
           {
                if(a[i-1]==1)
				{
					a[i]=-1;
					a[i-1]=2;
				}
                else if(a[i-1]==3)
				{
					a[i]=a[i-1]=2;
				}
                else return 0;
            }
        }
        int m=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=-1)
			{
				a[++m]=a[i];
			}
        }
        n=m;
        for(int i=1;i<=n;i++)
		{
			a[i]--;
		}
    }
    return 1;
}
int main()
{
    int x;
    cin>>x;
    while(x--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		puts(check()?"TAK":"NIE");
    }
    return 0;
}

感谢观看

不要复制完代码就走了啊，这样是不道德的，思路也是要看的， 对了，别忘了要点个赞！