Codeforces Round #765 (Div. 2)

这场的难度梯度有点大，题面比较长，然后就可能大家花了很多时间读题，但其实cf的样例解释很详细，看不懂题面的话看看样例解释就懂了

A.Ancient Civilization

就是给我们n个数，给出一个上限l，要我们求一个数x使得${\sum }_1^n\backslash sum\_\{1\}^\{n\}$|$a_{i}a\_\{i\}$ - x|最小，并且x $\le 2^l-1\backslash leq\; 2^\{l\}\; -\; 1$, 那么做法就很显然嘛，对于这n个数，遍历所有的二进制位，如果对于第i位，n个数中1的数量多于0的数量，x中这一位为1，就是这样，至于上界，是肯定不会超过的

B.Elementary Particles

就是给我们n个数字，要求我们找出两个序列[$l_{1}l\_\{1\}$, $r_{1}r\_\{1\}$], [$l_{2}l\_\{2\}$, $r_{2}r\_\{2\}$],使得两个序列的长度相等，且有一个位置上的数是相等的，序列的长度不能是n，不能是1

好像很多人用的kmp什么的，但其实只是一个简单贪心题吧，我们肯定要从相等的数下手，我们假设对于相等的数x，他在给出序列中的位置依次为$x_1,x_2,x_3,x_4,\mathrm{.}\mathrm{.}\mathrm{.},x_{k}x\_\{1\},\; x\_\{2\},\; x\_\{3\},\; x\_\{4\},\; ...,x\_\{k\}$,如果我们当前选择了$x_2,x_{k}x\_\{2\},\; x\_\{k\}$，那么由此的到的答案就是$x_2+n-x_{k}x\_\{2\}\; +\; n\; -\; x\_\{k\}$，那么我们定住$x_{k}x\_\{k\}$，显然如果存在一个比$x_{2}x\_\{2\}$大的位置，显然答案更优，那么我们就依次定住右边界，那么右边界与其左边更近的配对，显然就可以得到答案，哦可能说的不清楚，给个代码吧，赛中代码

template <typename T>
void res(T x, char y = '\n') {
    cout << x << y;
}
 
constexpr int N = 2e5 + 10;
int n, cnt[N], a[N];
 
void solve() {
    cin >> n;
    rep(i, 1, 150000) {
        cnt[i] = 0;
    }
    int ans = -1;
    rep(i, 1, n) {
        cin >> a[i];
        if (cnt[a[i]]) {
            ans = max(cnt[a[i]] + n - i, ans); 
        }
        cnt[a[i]] = i;
    }
    res(ans);
}

C.Road Optimization

一个简单dp？ 给出了n + 1个位置$d_{i}d\_\{i\}$，起点为0，终点为m，除了终点外的每个点给出一个时间，代表从第i个点到第i + 1个点的速度，那么让我们从其中移除k个点，使得从起点到终点的时间最短，求出最短时间，起点的不能移除

这贪心可是太麻烦了，那么我们其实可以一眼看出了n三方的dp?

当我们处在第i个点时，肯定是从上一个未被移除的点k转移过来，那么在i这个点已经移除了几个点？，那么我们就需要在状态里交代清楚，显然我们的答案是在第n + 1个点的，第n + 1个点肯定是不需要移除的，那么也就是说我们从一个未被移除的点转移到后面一个未被移除的点的

定义dp[i][j]为从起点到达第i个点，移除了不包含起点和i号点的j个点所需要的最短时间，为什么i号点不能移除，如果我们从一个移除了点的转移过来，对于它的速度显然是未知的，那么就会显得很麻烦，不移除i号点，显然是可行的，那么最后的答案就是dp[n + 1][j] (j: 0->k)，显然符合我们的状态定义

k号点转移到i号点，那么[k + 1, i - 1]的所有点都会被删 那么dp[i][j] = dp[k][j - (i - 1 - (k + 1) + 1)] + (d[i] - d[k]) * v[k]且(j >= 0 && j < min(k,i - 1) 还是给个代码吧，赛中写的丑代码

constexpr int N = 600;
int n, m, k, d[N], v[N], dp[N][N];

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ) {
        cin >> d[i];
    }
    for (int i = 1; i <= n; i ++ ) {
        cin >> v[i];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    d[n + 1] = m;
    for (int i = 1; i <= n + 1; i ++ ) {
        dp[i][0] = dp[i - 1][0] + (d[i] - d[i - 1]) * v[i - 1]; 
    }
    if (k == 0) {
        cout << dp[n + 1][0] << endl;
        return;
    }
    d[n + 1] = m;
    for (int i = 2; i <= n + 1; i ++ ) {
        for (int j = 1; j < min(k + 1, i - 1); j ++ ) {
            for (int k = i - 1; k >= i - j - 1 && k >= 1; k --) {
                if (j - (i - k - 1) >= 0) {
                    dp[i][j] = min(dp[i][j], dp[k][j - (i - k - 1)] + (d[i] - d[k]) * v[k]); 
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i <= k; i ++ ) {
        ans = min(dp[n + 1][i], ans);
    }
    cout << ans << endl;
}

D. Binary Spiders

给我们n个数，和一个k，要求我们从这n个数中选出尽可能多的数大于一个，满足任意两数的xor值不小于k 输出个数和该方案下的数的下标

我们可以想到的是，对于两个数在什么条件下xor值大于等于k，那么假设k的最高位1在第id号位置，只要两数x，y在更高位有一位不相同就满足，或者两数的xor值与k不相等的位上为1，或者两数所有位相等

那么我们得到id号位置后，就把所有数按照最高位-(id + 1)号位置的值分类，对于每一类，高于id号位置都是相同的，那么他们在这些位置上的异或值都是0，对于不同类，显然在这些位至少有1位不同，那么不同类之间的异或值就是大于k的，对于相同类，我们最多选择两个数，或者1个数，如果选择了3个数及以上，那么抽屉原理，必然存在两数在id号位置相同,xor值就会小于k，那么我们就可以使用trie树判断同一类中否存在两数的xor值大于等于k。那么如何得到下标呢，当我们判断第下标为i的数是，如果我们在trie树上的某个结点，确定了一定大于等于k，那么我们记录一下能走到这个点的下标就行了，也就是我们另开一个pos数组，pos[j]能走到当前点j的数的下标，如果没有，则在此类中选择一个数即可； 最后判断一下是否由两个数及以上即可

举个例子k位0001111，那么假设一共7位，那么我们按照前面3位的值分类，最多3e5个类 贴个代码吧

#define int long long 
template <typename T>
void res(T x, char y = '\n') {
    cout << x << y;
}
constexpr int N = 3e5 + 10;
int n, k, a[N], tot, End[N * 31];
map<int, vector<int> > m;

struct node {
    int c[N * 31][2];
    void modify(int val, int pos) {
        int fa = 0;
        for (int i = 29; i >= 0; i -- ) {
            int &son = c[fa][val >> i & 1];
            if (!son) { son = ++tot; }
            fa = son, End[son] = pos;
        }
    }
    
    int query(int val) {
        int fa = 0;
        for (int i = 29; i >= 0; i -- ) {
            if (k >> i & 1) {
                int k1 = c[fa][~val >> i & 1];
                if (!k1) return -1;
                fa = k1;
            }
            else {
                int k1 = c[fa][~val >> i & 1];
                if (k1) {
                    return End[k1];
                }
                fa = c[fa][val >> i & 1];
            }
        }
        if (End[fa] == 0) return -1;
        return End[fa];
    }

    void clear() {
        while (tot > 0) {
            c[tot][0] = c[tot][1] = 0;
            End[tot] = 0;
            tot--;
        }
        c[0][1] = c[0][0] = 0;
    }
}tree;

void solve() {
    cin >> n >> k;
    rep(i, 1, n) {
        cin >> a[i];
    }
    int l = __lg(k) + 1;
    if (!k) {
        res(n);
        rep(i, 1, n) {
            res(i, ' ');
        }
        return;
    }
    rep(i, 1, n) {
        m[a[i] >> l].pb(i);
    }
    vector<int> ans;
    for (auto x : m) {
        vector<int> b = x.second;
        for (auto it : b) {
            tree.modify(a[it], it);
        }
        bool ok = false;
        for (auto it : b) {
            int k1 = tree.query(a[it]);
            if (k1 != -1) {
                ans.pb(k1);
                ans.pb(it);
                ok = true;
                break;
            }
        }
        if (!ok) {
            ans.pb(b[0]);
        }
        tree.clear();
    }
    if (sz(ans) < 2) {
        res(-1);
        return;
    }
    res(sz(ans));
    for (auto x : ans) {
        res(x, ' ');
    }
}

E1.Cats on the Upgrade (easy version)

就是给我们一个括号序列，然后每次询问一个区间[l, r]，询问的区间一定是一个合法的括号序列，问有多少个字序列也是合法的，位置不同也认为相同

还是举个例子吧，因为不太好说(()())()有6个，那么怎么计算能满足在log的时间内完成呢？ 我们首先引入一个简单问题 给出一个括号序列，问其中有多少个合法序列，那么我们只需要求一下以i为结尾的括号序列数，然后求和就行了

那么这个题怎么做的，((()))这种包含关系肯定是很好计算的，那么()(())()这种存在着并列关系和包含关系的同时存在的显然是不好计算的，那么我们就可以先求包含关系，最后求最外层的并列关系，那么也就是说我们把最外层的包含关系用来建成一棵树，这样我们用dfs序维护，就可以使用数据结构在log的时间里求出除了最外层的并列关系的情况数，只有一对(),我们也认为是并列关系，可能说的不太好，，我们举一个复杂一点的例子

例如((())())(()) 那么第一棵树父节点fa1为[1, 8],两个儿子x1为[2,5],x2为[6,7],x1的儿子x1x为[3,4]那么x1x对x1的贡献为1，x1,x2对fa1的贡献为3{(),(()),(())}，第二棵树类似，最后加最外层的并列2*(2 + 1) / 2 = 3