Codeforces Round #779 (Div. 2) D2 E

63 阅读 0 评论 42 点赞

我是靠谱客的博主寒冷柠檬，最近开发中收集的这篇文章主要介绍Codeforces Round #779 (Div. 2) D2 E，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

D2. 388535 (Hard Version)

prob. : 给出l，r，和一个数列a，a是l到r中间这些数的排列，数列b是由数列a每个数异或上一个x得到，给出数列b要求x。

idea：

刚开始的想法是对于每一位考虑，在l到r的区间内这一位为1次数记为cnt1和在b数组中这一位为1的次数记为cnt2，但由于l不一定为0，当 $c n t 1 = = c n t 2$ 且 $c n t 1 = = n / 2$ 的时候不知道这一位到底要不要取，有想过一些奇怪的判定方法都给否了。

考虑到异或的性质，存在 $b_i = x bigoplus l$ ，则x一定出现在一个 $b_i bigoplus l$ 中，将所有的 $b_i bigoplus l$ 取出判断，成立的一个必要条件是 $b_i bigoplus l$ 与数列b能异或出的最小恰好是l，最大值恰好是r

暂时没有充分性证明

code

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 18) + 10;

int cnt = 0;
int nex[N * 20][2];

void insert(int x) {
    int p = 0;
    for (int i = 17; i >= 0; --i) {
        int c = (x >> i) & 1;
        if (!nex[p][c]) {
            nex[p][c] = ++cnt;
            nex[cnt][0] = nex[cnt][1] = 0; //init
        }
        p = nex[p][c];
    }
}

int getMx(int x) {
    int p = 0, ans = 0;
    for (int i = 17; i >= 0; --i) {
        int c = (x >> i) & 1;
        if (nex[p][!c]) {
            p = nex[p][!c];
            ans = ans ^ (1 << i);
        } else p = nex[p][c];
    }
    return ans;
}

int getMn(int x) {
    int p = 0, ans = 0;
    for (int i = 17; i >= 0; --i) {
        int c = (x >> i) & 1;
        if (nex[p][c]) p = nex[p][c];
        else {
            p = nex[p][!c];
            ans = ans ^ (1 << i);
        }
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        vector<int> vec;
        cnt = 0;
        nex[0][0] = nex[0][1] = 0;

        int l, r;
        cin >> l >> r;
        int n = r - l + 1;
        for (int i = 1, x; i <= n; ++i) {
            cin >> x;
            insert(x);
            vec.push_back(x ^ l);
        }
        int ans;
        for (auto tt : vec) {
            if (getMn(tt) == l && getMx(tt) == r) {
                ans = tt;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

E. Gojou and Matrix Game

prob. : 格子棋盘两个人玩游戏，轮流取数，可以重复取，每次取数必须距离上个人的取数曼哈顿距离大于k，对于先手第一次的不同取法，问每次游戏无限次操作后谁赢

idea:
dp/SG，经典曼哈顿转切比雪夫
首先如果A比B上一轮拿的少，A就输了，则在满足条件的情况下拿的数字一定递增
考虑反过来，从最大的开始，此时一定是必胜态，考虑按递减顺序每个位置与之前所有必胜态的距离最大值是否小于等于k，是的话则说明当前状态一定是必胜态，否则为必败态，当当前状态为必胜态的时候更新切比雪夫判断条件

刚开始不知道为什么mle1，很怪，就数组重用了

code

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int a[N][N];

int mxx, mnx, mxy, mny;

struct node {
   int x, y;
};

vector<node> vec;

int getDis(int x, int y) {
    int nx = x + y;
    int ny = x - y;
    int disX = max(abs(mxx - nx), abs(mnx - nx));
    int disY = max(abs(mxy - ny), abs(mny - ny));
    return max(disX, disY);
}

void renew(int x, int y) {
    mxx = max(mxx, x + y);
    mnx = min(mnx, x + y);
    mxy = max(mxy, x - y);
    mny = min(mny, x - y);
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n, k;
    cin >> n >> k;

    int mx = 0, posx = 0, posy = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
            if (a[i][j] > mx) {
                mx = a[i][j];
                posx = i;
                posy = j;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == posx && j == posy) continue;
            vec.push_back({i, j});
        }
    }

    sort(vec.begin(), vec.end(), [&](auto le, auto ri) {
        return a[le.x][le.y] > a[ri.x][ri.y];
    });

    mxx = posx + posy, mnx = posx + posy;
    mxy = posx - posy, mny = posx - posy;

    for (auto tt : vec) {
        int x = tt.x;
        int y = tt.y;
        if (getDis(x, y) <= k) {
            a[x][y] = 1;
            renew(x, y);
        } else {
            a[x][y] = 0;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i][j]) cout << "M";
            else cout << "G";
        }
        cout << endl;
    }
    return 0;
}