太菜了，当时只写出来两题，赛后也只复盘了前三题，第四题看情况吧= =，感觉第三题都挺难了

A. Divan and a Store

题目大意:
规定一个购买物品的最小金额，最大金额，还有你自己的余额。给一排不同价格的物品，问在余额内最多可以买多少个物品。

题解：
排序一下，贪心选就行了。

代码:

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, l, r, k;
        n = read();
        l = read();
        r = read();
        k = read();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            p[i] = read();
        }

        sort(p, p + n);

        for (int i = 0; i < n; i++) {
            if (k - p[i] >= 0 && l <= p[i] && p[i] <= r) {
                k -= p[i];
                ans++;
            }
        }

        printf("%d\n", ans);
    }
}

B. Divan and a New Project

题目大意:
给你n个有不同访问次数的点，问怎样安排可以让累加的访问距离最近。打印最小距离和所有点的具体坐标。

题解：
先给所有点按访问次数的大小排序，然后访问次数越高的点离起点越近就好了。我用了个结构体来关联点序号和次数。总的来说还是贪心。

当时打印点坐标的时候没看清是按照输入顺序点的顺序打印，结果卡了一个钟，后面的题也没来得及看。
英语真的很关键，当时发了个问题得到的回复是：
You claimed answer 78, but your construction gives answer 104.
可能也是太紧张了，没理解'claimed'的意思，结果一直坐牢发呆。

代码:

#include <bits/stdc++.h>
#define MAXN 200010
#define INF 0x3f
using namespace std;
typedef pair<int, int> P;

struct build {
    long long id;
    long long vis;

    bool operator < (build b) {
        return vis < b.vis;
    }
} bu[MAXN];

long long line[MAXN];

int main() {
//  freopen("06.in", "r", stdin);
//  freopen("06.out", "w", stdout);
    int t;
    cin >> t;

    while (t--) {
        long long n;
        scanf("%lld", &n);

        for (int i = 1; i <= n; i++) {
            bu[i].id = i;
            scanf("%lld", &bu[i].vis);
        }

        sort(bu + 1, bu + n + 1);
        long long js = -1;
        long long os = 1;
        long long ans = 0;

        for (int i = n; i > 0; i--) {
            if (i % 2 == 0) {
                line[bu[i].id] = js;
                ans += (2 * -js) * bu[i].vis;
                js--;
            } else {
                line[bu[i].id] = os;
                ans += (2 * os) * bu[i].vis;
                os++;
            }
        }

        printf("%lld\n", ans);

        for (int i = 0; i <= n; i++) {
            printf("%lld ", line[i]);
        }

        if (t != 0)
            printf("\n");
    }

//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

C. Divan and bitwise operations

题目大意:
给出序列的总长度和一些数字片段的或运算和，保证序列的每一个数都至少被一个片段所覆盖，要求所有子序列的异或结果相加等于多少

题解:
对我来说有点难理解，所以比赛完还是花了很久去看其他人的题解。
首先要处理的是序列异或和的问题：
我们按二进制的逐个判断(因为所有位运算的结果不会对其他位数造成任何影响)，假设序列中有一个数在该位为 1， 那么则有1/2的子序列在该位的异或结果是1。
解释如下: 1 & 1 = 0 1 & 0 = 1， 如果不包括他的子序列运算结果为1，那么加上他就一定会变成0；如果不包括他的子序列运算结果为0，那么加上他就一定会变成1。
所以我们只需要判断所有数在该位上是否有 1 存在，就可以知道将他们全部异或后的结果是多少。这就是他给出的或运算的作用 -> 将所有数字或运算的结果就可以判断哪些位置上存在 1。
接下来就是解决子序列个数的问题:
这里要用到的是C_{n}^{1} +C_{n}^{2} +C_{n}^{3} +...+C_{n}^{n} = 2^n 那么二分之一的子序列个数，则是2^{n-1} 这样一来答案就出来了，即
[(a1|a2|a3|...|ak) * 2^{n-1}] MOD (1e9 + 7)
因为数可能很大顺便写了一个快速幂取余(复习一下)
代码:

#include<bits/stdc++.h>
using namespace std;

const int MODS = 1e9 + 7;

long long ksm(int a, int n) {
    if(n == 0) return 1;
    long long ans = a;
    int t = 1;
    while (t < n) {
        if (2 * t <= n) {
            ans = (ans * ans) % MODS;
            t *= 2;
        } else {
            ans = (ans * a) % MODS;
            t++;
        }
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int ans = 0;
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int x;
            cin >> x >> x >> x;
            ans |= x;
        }
        printf("%lld\n", ans * ksm(2, n - 1) % MODS);
    }
}

D1. Divan and Kostomuksha (easy version)

感谢wljss大佬教会了我这题(✿✿ヽ(°▽°)ノ✿)
大致题意：
给出一个序列，你可以任意重新排序，使得排序后的结果进行下面计算的值最大

\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),

输出计算的结果
题解:
很容易想到，第一个要提取的数是最大的数，因为这样才能得到最大的一个gcd值。
然后也很容易想到相同的数一定是放在一起的，因为a_{i}的范围并不是很大，所以我们直接开数组计数就行了。
对于每一个数 a_{i} 我们均计算它的倍数的个数，相当于一个前缀和。
然后就是本题的关键——DP。

f[i] = max(f[i], f[j] + (js[i] - js[j]) * i)

i是当前处理的数，j是i小于最大值的所有倍数

代码:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#define LL long long
using namespace std;
int n, maxx;
LL ans;
const int N = 100010, M = 5000000;
int tong[M + 10];
LL f[M + 10], js[M + 10];
int main() {
    cin >> n;
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        tong[x]++;
        maxx = max(maxx, x);
    }
    for (int i = maxx; i >= 1; --i) {
        for (int j = i; j <= maxx; j += i) {
            js[i] += tong[j];
        }
    }
    for (int i = maxx; i >= 1; --i) {
        f[i] = (LL)js[i] * i;
        for (int j = i * 2; j <= maxx; j += i){
            f[i] = max(f[i], f[j] + (LL)(js[i] - js[j]) * i);
        }
    }
    for (int i = 1; i <= maxx; ++i){
        ans = max(ans, f[i] + (n - js[i]));
    }
    cout << ans;
    return 0;
}

小总结

第二题卡太久了，导致最后分数只有800，第七分钟就AC了第一题，结果一直被卡到了将近比赛结束才过了第二题。感觉没有体现出自己真实水平吧...也是自己英文比赛打太少了，多练点应该会有提升吧。