思维习题集

一.E - Add and Mex (atcoder.jp)

        （1）题目大意

        给定你一串数，M次操作，每一次操作对于a[i]这个元素都会加上i，现在问你第i次操作后，该数组的最小非负整数补集是多少？

         （2）解题思路

                对于n来说，有2*10^5，不能够直接模拟，那么我们发现一些性质，对于第i次操作，如果他加上i后大于n了，那么这次操作和这次操作后的都属于无效操作。对于每一个元素来说，我们可以知道他要进行多少次操作才能把这个数变为非负数，对于这个操作次数之前的操作次数，都不会影响答案，因此我们对于每个元素处理就是次数小于等于m，并且+i小于等于n才会对答案有贡献。时间复杂度（nlogn）。

        （3）代码实现

#include "bits/stdc++.h"
using namespace std;
const int N = 2e5 + 10;
vector <int> num[N];
int a[N];
void solve()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        int k = 1;
        if(a[i] < 0) k = (-a[i] % i ? -a[i] / i + 1 : -a[i] / i);
        else k = 1;
        while(k <= m && a[i] + i * k <= n) {
            num[k].push_back(a[i] + i * k);
            k ++;
        }
    }
    for(int i = 1;i <= m;i++) {
        sort(num[i].begin(),num[i].end());
        num[i].erase(unique(num[i].begin(),num[i].end()),num[i].end());
        int mex = 0;
        for(auto x:num[i]) 
            if(x == mex) mex ++;
            else break;
        cout << mex << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T = 1;
    while(T --) {
        solve();
    }
    return 0;
}

二.F - Unfair Nim (atcoder.jp)

        （1）题目大意

                给定你n堆石头，每一堆石头最多有10^12个，Aoki 先手，Takahashi 后手，现在问你在你能把第一堆石子不能为空的情况下，可以把第一堆石子移动到第二堆，能否让Takahashi 胜利。

         （2）解题思路

                这可以看出来是个NIM游戏的变种，也就是说我们可以认为的操作第一堆和第二堆，看能否导致游戏局面发生变化，由NIM博弈可知，若n堆石子异或为0，则先手必败，因此Takahashi 胜利等价于Aoki必败，对于后面n-2堆石子是不可变状态，把后面n-2堆异或出来后，看能否把第一堆石子和第二堆石子的异或变成后面n-2堆异或的值。

                设后面n-2堆石子异或出来的值为x，前面2堆和为s，设d = （s - x) / 2（表示至少消除这么多石子）

                情况1，若x > s，则不可能得到。

                情况2，若x和s奇偶性不同，也不可能得到。

                情况3，若d > 第一堆或者(d & x)不为0，也不可能得到

                情况4，

        （3）代码实现

#include "bits/stdc++.h"
using namespace std;
const int N = 310;
long long a[N];
void solve()
{
    int n;
    cin >> n;
    long long x = 0,s = 0;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        if(i > 2) x ^= a[i];
        else s += a[i];
    }
    if(s < x) {
        cout << -1 << endl;
        return ;
    }
    if((s - x) & 1) {
        cout << -1 << endl;
        return ;
    }
    long long d = (s - x) / 2,an = (s - x) / 2;
    if(d > a[1] || (x & d)) {
        cout << -1 << endl;
        return ;
    }
    for(int i = 50;i >= 0;i--) {
        if((x >> i & 1) && !(d >> i & 1) && (an + (1LL << i)) <= a[1]) 
            an += 1LL << i;
    }
    if(an == 0) {
        cout << -1 << endl;
        return ;
    }
    cout << a[1] - an << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T = 1;
    while(T --) {
        solve();
    }
    return 0;
}