题解：P17867 [FJCPC 2026] 哦搞错了

chenzhixuan2010 · 2026-11-13 14:35:27 · 题解

简单构造题。

考虑使所有为 1 的位置的数都为 2^k + x_i，使所有为 0 的位置都为 y_i，其中 x_i,y_i 为小于 2^k 的任意非负整数，最后只要使总异或值在 2^k 到 2^{k + 1} - 1 之间就可以满足要求。但如果有偶数个位置是 1 那总异或和肯定不能满足要求。注意到答案只要求构造的 W 与 S 的海明距离小于等于一，所以这种情况下直接把最后一位取反来做就好了。

由于每个 A_i 都不相同，所以对于所有 1 \leq i < n：

若 S_i = 0，则令 A_i = i。
若 S_i = 1，则令 A_i = 2^k + i。其中 k 可以取任意大于 \log_2 n 且小于 60 的数，这里我取了 58。

对于最后一位，根据前面 1 的位置个数来调整即可。时间复杂度 O(n)。

::::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Fast{
    inline int fr(){
        int x = 0,f = 1;
        char c = getchar();
        while (c < '0' || c > '9'){
            if (c == '-') f = 0;
            c = getchar();
        }
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        return (f ? x : -x);
    }
    char putstk[1005];
    inline void fw(int x){
        if (x == 0) return putchar('0'),void();
        if (x < 0) x = -x,putchar('-');
        int tp = 0;
        while (x) putstk[++tp] = ((x % 10) ^ 48),x /= 10LL;
        while (tp) putchar(putstk[tp--]);
    }
}

using namespace Fast;
int a[114514];
signed main(){
    string s;
    cin>>s;
    int n = s.size();
    s = ' ' + s;
    int cnt1 = 0;
    for (int i = 1;i < n;i++){
        int res = i;
        if (s[i] == '0') a[i] = res;
        else a[i] = res + (1LL << 58),cnt1++;
    }
    if (cnt1 % 2 == 0) a[n] = ((1LL << 58) + n);
    else a[n] = n;
    for (int i = 1;i <= n;i++) fw(a[i]),putchar(' ');
    return 0;
}

::::

题解：P17867 [FJCPC 2026] 哦 搞错了

题解：P17867 [FJCPC 2026] 哦搞错了