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

Addicted_Game · 2023-12-14 20:32:16 · 题解

传送门

题目大意

给定一个 01 串，执行 t 次操作，每一次操作，第 i 个数将会变为与第 i-1 个数的异或结果，问操作执行后，01 串的结果。

思路

很明显这是一道数学找规律的题，先打一个暴力代码，枚举 t 次操作。

#include<bits/stdc++.h>
using namespace std;
long long n,t;
char c;
bool a[10005][10005];
bool num[10005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>c;
        a[0][i]=c-'0';
    }
    for(int i=1;i<=t;i++){
        for(int j=1;j<=n;j++){
            num[j]=a[i-1][j]^a[i-1][j-1];
        }
        for(int j=1;j<=n;j++){
            a[i][j]=num[j];
            //cout<<num[j];
        }
        //cout<<endl;
    }
    for(int i=1;i<=n;i++) cout<<a[t][i];
    return 0;
}
/*
1->1 2->2 3->4 4->4 5->8 6->8 9->8 10->8 11->16 12->16 15->16 16->16 17->32
*/

通过观察它的结果，可以发现一个规律：长度为 n 的 01 串，每 2^{\lfloor \log n \rfloor } 次就是一个循环所以只需要计算 t \bmod 2^{\lfloor \log n \rfloor } 次就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,t;
char c;
bool a[10005];
bool num[10005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>c;
        a[i]=c-'0';
    }
   int x=1;
    while(x<n) x*=2;
    t%=x;
    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;
}