P3491 [POI2009] SLW-Words题解

GeXXGe · 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;
  }

感谢观看

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