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

· · 题解

本蒟蒻的第一篇题解。

让我们来看一点不一样的解法——

（其实也不是那么不一样）

题解区大部分都是用周期的方式完成的。原因很简单：

所以，大多数人都选择用周期去做。

但是，当我拿到题目的时候，我第一个想到的是有点类似离散化的思想。如果在一个 0 之后有很多个连续字符都是 1，那么我只需要把第一个字符变为 1 即可，没有必要一一枚举每一个字符。,我只需要存储每一个需要变动的字符，然后一一变动就好了。

所以，这道题我选择了队列。

怎么变动呢？这里直接将队首元素取反即可，因为本题异或只与原来的数值有关，而它能进入队列说明它与周围的原数值一定满足需要变化的条件。

接下来，我们需要判断变化的字符需不需要继续变化。

不仅是这样，我们还要判断它后面的字符是否因为它的变化也需要变化。而它后面的字符可能因为一开始符合不变化的条件，所以它有可能根本没入队。因此需要额外的判断。

然后就是空间问题。我在调试代码的时候，发现空间不优化的话会炸掉。参照 SPFA 的优化经验，需要记录元素是否在队列中。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,t,len = 1;
int num[10005];
queue<pair<int,int> > que;
char tp;
int main(){
    scanf("%d%d",&n,&t);
    scanf("\n");
    scanf("%c",&tp);
    num[1] = tp-'0';
    for(int i = 2; i <= n; i++){
        scanf("%c",&tp);
        num[i] = tp-'0';
        if(num[i]^num[i-1] != num[i]){
            que.push({1,i});
        }
    }
    while(len <= n){
        len *= 2;
    }
    t %= len;
    while(que.size()){
        int a = que.front().first;
        int b = que.front().second;
        que.pop();
        if(a > t){
            break;
        }
        num[b] = num[b] ? 0 : 1;
        if(num[b]^num[b-1] != num[b]){
            que.push({a+1,b});
        }
        if(num[b]^num[b+1] != num[b+1]){
            que.push({a,b+1});
        }
    }
    for(int i = 1; i <= n; i++){
        printf("%d",num[i]);
    }
    return 0;
}