思路

  • 首先考虑[l,r]分隔较远的情况。那么一定可以找到最高位为零1,其后全为0的数x(eg.1000),和x-1(eg.111),(x-1)^x=1111,当且仅当这一情况(存在这一跨度,即最高位不为0)下,可以保证答案为长度为n且全为1的串。
  • 接下来考虑lr最高位相同的情况。可以发现,当选择区间长度为偶数时,偶数次的前缀都会被置零,其中最高位必然被置零。也就是说,我永远也不可能选长度为偶数的区间。而我选择长度为1的区间,可以保证答案至少是r。
  • 那么是否存在答案大于r的情况呢?我们考虑区间的长度,不难发现,过长的区间,只会造成损失,而不会带来更大的收益,原因同上,偶数次reset。那么考虑截取一段“偶奇偶”的段,这样的一段,异或和为最大的偶数+1。故可选最大的偶数,答案为它+1。也与上述的最大数为r的奇数情况吻合。

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n;
char a[N], b[N];
inline void addOne() {
    bool add = 1;
    for (int i = n - 1; ~i && add; --i) {
        if (add) a[i]++, add = 0;
        if (a[i] == '2') a[i] = '0', add = 1;
    }
}
inline bool same() {
    for (int i = 0; i < n; ++i)
        if (a[i] != b[i]) return 0;
    return 1;
}
inline bool chk() {
    if (b[n - 1] != '0') return 0;
    if (b[n - 2] == '1') {
        for (int i = 0; i < n - 2; ++i)
            if (a[i] != b[i]) return 1;
        return a[n - 2] == '0' && a[n - 1] == '0';
    } else {
        if (same()) return 0;
        addOne();
        if (same()) return 0;
        return 1;
    }
    return 0;
}

int main() {
    scanf("%d%s%s", &n, a, b);
    if (a[0] != b[0])
        for (int i = 0; i < n; ++i) putchar('1');
    else {
        if (chk()) b[n - 1] = '1';
        puts(b);
    }
    return 0;
}