其他

博弈论

NIM

必胜态：\(a_1XORa_2XOR\dots XORa_n \neq 0\)​

必败态：\(a_1XORa_2XOR\dots XORa_n = 0\)​

其他：

Staircase Nim：POJ 1704

Grundy值

void grundy() {
    grundy[0] = 0; //必败，其实也可以不写让j从0开始
    int maxa = *max_element(a, a+n);
    for(int j = 1; j <= maxa; j++){
        set<int> s;
        for(int i = 0; i < k; i++)
            if(a[i] <= j) 
                s.insert(grundy(j-a[i]));

        int g = 0;
        while(s.count(g) != 0) g++;
        grundy[j] = g;
    }
}

离散化

//白书P164，二维坐标离散化
typedef long long ll;
const int maxn = 600;

int x1[maxn], x2[maxn], y1[maxn], y2[maxn];
int n; 

int compress(int *x1, int *x2, int w)  {
    vector<int> vec;

    for (int i = 0; i < n; i++) {
        for (int d = -1; d <= 1; d++) {
            int tx1 = x1[i] + d, tx2 = x2[i] + d;
            if (tx1 >= 1 && tx1 <= w) vec.push_back(tx1);
            if (tx2 >= 1 && tx2 <= w) vec.push_back(tx2);
        }
    }

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for (int i = 0; i < n; i++) {
        x1[i] = find(vec.begin(), vec.end(), x1[i]) - vec.begin();
        x2[i] = find(vec.begin(), vec.end(), x2[i]) - vec.begin();
    }
    return vec.size();
}