类打表做法

xingyu671 · 2023-08-29 15:18:32 · 题解

这是一道绿色水题。

如果直接模拟，考虑到 t \le 10^{18} 的数据范围，肯定会 TLE。
所以，我们需要 构造样例+分析，不难发现：

(n = 15)  
0.101010101001101
1.111111111101011
2.100000000011110
3.110000000010001
4.101000000011001
5.111100000010101
6.100010000011111
7.110011000010000
8.101010100011000
9.111111110010100
10.100000001011110
11.110000001110001
12.101000001001001
13.111100001101101
14.100010001011011
15.110011001110110
16.101010101001101 ←这里与第0行一样
17.111111111101011
18.100000000011110

16正好是 2^{\lceil \log\,n \rceil}。
所以：
上表中的第 2^{\lceil \log\,n \rceil} 行一定和第0行一样。

补充证明：
我们来演示一下迭代 t 次的 s_i 和哪些有关。如果 s_j=1 ，则 s_i 和 s_j 有关。为了更直观，用 # 和空格来表示 1 和 0。

（n = 16)

               #
              ##
             # #
            ####
           #   #
          ##  ##
         # # # #
        ########
       #       #
      ##      ##
     # #     # #
    ####    ####
   #   #   #   #
  ##  ##  ##  ##
 # # # # # # # #
################

和 南蛮图腾 很像。当这行全是 # 的时候，下一行一定是初始状态。而全是 # 的行是 2^{\lceil \log\,n \rceil} 行。
所以我们可以写出代码了。

#include<bits/stdc++.h>
#include<string>
using namespace std;
long long fun(long long x)
{
    long long y = 1;
    while(y < x)
    {
        y *= 2;
    }
    return y;
}//求2^⌈logn⌉

string s[17005];
int main(void)
{
    long long n,t,vla;
    cin >> n >> t >> s[0];
    vla = fun(n);
    for(int i = 1;i < vla;i++)
    {
        s[i].resize(n);//如果不写这一行，s[i]将为空。
        s[i][0] = s[0][0];//关于这一行，我就不多说了。请自行理解它为啥待在这。
        for(int j = 1;j < n;j++)
        {
            if(s[i-1][j-1] == s[i-1][j]) s[i][j] = '0';
            else s[i][j] = '1';
        }
    }// 相当于打表
    t %= vla;
    cout << s[t];
    return 0;
}

但是即使是这样，还是会 TLE ( 80\text{pts} )。
把 string 数组变为 string 变量即可。
AC 代码：

#include<bits/stdc++.h>
#include<string>
using namespace std;
long long fun(long long x)
{
    long long y = 1;
    while(y < x)
    {
        y *= 2;
    }
    return y;
}
int main(void)
{
    long long n,t,vla;
    string s;
    cin >> n >> t >> s;
    vla = fun(n);
    t %= vla;
    if(t == 0) cout << s;
    for(int i = 1;i < vla;i++)
    {
        string u = s;//得把上一次的s保存下来
        for(int j = 1;j < n;j++)
        {
            s[j] = (u[j-1]-'0')^(u[j]-'0')+'0';
        }
        if(i == t) cout << s;
    }
    return 0;
}

蒟蒻的第一篇题解，求过！！
xingyu671 衷心提醒您：题解千万条，理解第一条。直接交题解，棕名两行泪。