题解 [蓝桥杯 2021 国 ABC] 异或变换

· · 题解

解题思路

看到数据范围就想到时间复杂度和 t 基本不太可能有关系（\log t 除外，但这题我没想到怎么和 \log t 扯上关系），既然这样就代表解题方法是和具体操作多少次无关的，那么我们再考虑另一个比较小的变量 n，既然 01 串长度不大，那么想必是一道找规律的妙妙题了。想到这里就自然打表找规律，既然已经大致确定了和 t 没什么关系，那么我们就把 t 看做无限大，然后去模拟每一次操作（觉得麻烦也可以写暴力，然后给 t 赋一个较大的值），我们发现，样例在第 4 次操作时就出现了循环，这真的是巧合吗？不妨改变 n，然后继续模拟，就不难找到规律。其它这种类似的题也可以优先考虑这种做法。

找到规律后就根据时空限制确定写法，本题蒟蒻把思路模拟了一遍就 AC 了，如果 TLE 了 或者 MLE 了就回去检查一下思路或者写法 qwq。

#include<bits/stdc++.h>
using namespace std;
namespace TO
{
    const int N=1e4+21;
    int n,x=1;
    long long t;
    bool a[N];
    char c;
    int mian()
    {
        cin>>n>>t;
        for(int i=1;i<=n;i++)
        {
            cin>>c;
            a[i]=c-'0';
        }
        while(x<n)
            x*=2;
        t%=x;
        a[0]=0;
        for(int i=1;i<=t;i++)
        {
            for(int j=n;j>=1;j--)
                a[j]^=a[j-1];
        }
        for(int i=1;i<=n;i++)
            cout<<a[i];
        return 0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    return TO::mian();
}