牛客练习赛94

Nhk R1 A」Initiale Dorimu

alt 首先我们从a xor b xor c = 0入手，如果我们令a xor b = c,那么就会很容易的得到a xor b xor c = 0, 那么我们要如何满足a or b or c = d呢？也就是说d中为1的二进制位，a,b,c中都要有奇数个，那么我们就只需要将d拆开，让a中包含一部分为1的二进制位，b中包含另一部分为1的进制位，就是说b中每个为1的二进制位a,b中都会有一个恰好为1，那么就会满足a or b = d,那么怎么拆呢，用lowbit去掉最低一位1就行了

也就是a = n & -n, b = n - a, c = a ^ b 如果a,b,c中有一个为0，则答案为-1

「Nhk R1 B」Basement-er Without Wings

alt 此题我冲了一发O(nlogn)，成功的t掉了，可能是我常熟太大了了吧我们可以知道的是我们每次的 $x_{i}$ 一定是不递增的，显然 $a_{1} = x_{1}$ ，那么我们怎么找一个合适的 $x_{i}$ 使得gcd( $a_{1}, a_{2}, ..., a_{i}$ )恰好为 $x_{i}$ ，首先每次选择的 $a_{i}$ 肯定是 $x_{i}$ 的倍数。

那么假设gcd( $a_{1}, a_{2}, ..., a_{i - 1}$ ) = x, gcd( $a_{1}, a_{2}, ..., a_{i}$ ) = y，如果x是y的倍数，我们任意选择一个满足是y的倍数的数，就可能会导致gcd( $a_{1}, a_{2}, a_{3}, ..., a_{n}$ ) = x,那么可以想到我们每次选择满足条件的最小数就可以了。

那么这样枚举倍数，我可能是常数太大，t了，然后我就加入了，两个优化，一旦gcd = 1了，我们就可以退出循环了

以及记录f[t]为未使用过的是t的倍数的最小数，看代码吧

constexpr int N = 2e6 + 10;
int n, p[N], ans[N], vis[N], minn[N];  

void solve() {
    cin >> n;
    rep(i, 1, n) {
        cin >> p[i];
        minn[i] = i;
    }
    ans[1] = p[1];
    vis[p[1]] = 1;
    int id = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (p[i] == 1) {
            id = i;
            break;
        }
        for (int j = minn[p[i]]; j <= n; j += p[i]) {
            if (!vis[j]) {               
                vis[j] = 1;
                ans[i] = j;
                minn[p[i]] = j;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i += 2) {
        if (!vis[i]) {
            ans[id] = i;
            vis[i] = 1;
            break;
        }
    }
    for (int i = 1; i <= id; i ++ ) {
        cout << ans[i] << " ";
    }
    for (int i = 1; i <= n; i ++ ) {
        if (!vis[i]) {
            cout << i << " ";
        }
    }
}

「Nhk R1 C」Zet'ubou Another

alt alt

数据范围这么大，搜索肯定是不行的，我们可以注意到k很小，那么我们可以把这些坐标离散化一下，把所有需要的关键点离散化一下，就行了，就比如说我们读入一个障碍 $(x_{i}, y_{i})$ ,我们需要还离散化 $x_{i} + 1, y_{i} + 1$ ，不然我们就会把空白点和障碍映射到同一个点，就要有了所有关键点的图，那么就很好做了

「Nhk R1 D」Apocryphal Vir Pulcher

alt

爆搜肯定是不行的，其实我们可以看出他们是按周期变化的，但是这个周期可能会很大，就没有什么用，假设我们当前的值为cur，那么下一步我们就产生最多80个可能值，那么也就是说可以bfs + pq,但是被卡了常数，那么n很小就启发我们可以使用80个队列，每次找到每个队列的最小值cur，在第k个对列中，那么我们把[k, n] or [1, k]的队列中插入cur + a[i]即可，这里解释一下为什么不是每个队列都插入，因为这样会重复，就比如我们在cur 的基础上加上了a[2], a[3]，就可能还会使用一次cur + a[3] + a[2]，显然是重复的