A. Level Statistics

只要读懂题就能过，只涉及两个值：$the\ number\ or\ plays\ and\ the\ number\ of\ clears$

当有人选择挑战某个难度时，$the\ number\ of\ plays$ 增加相应的数量；而当有人成功完成某个挑战时，$the\ number\ of\ plays$ 以及 $the\ number\ of\ clears$ 都会增加相应的数量。

不难发现，$the\ number\ of\ plays$ 不会减少，$the\ number\ of\ clears$ 也不会减少，前者不会少于后者，同时，两者的差值也不会减少，否则的话，就会不满足题意要求的数量增加的规则。

因此，在读懂题意细节之后，只需要 if else 判断即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n;
int p[N], c[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        bool success = true;
        for (int i = 1, d = 0; i <= n; i++) {
            cin >> p[i] >> c[i];
            if (p[i] < c[i] || p[i] < p[i - 1] || c[i] < c[i - 1] || p[i] - c[i] < d)
                success = false;
            d = p[i] - c[i];
        }
        cout << (success ? "YES" : "NO") << endl;
    }
    return 0;
}

B. Middle Class

排序之后，从大到小选择，直到其平均值不满足要求即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, x;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> x;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int bound = n;
        double sum = 0;
        while (bound) {
            sum += a[bound];
            if (sum / (n - bound + 1) < x)
                break;
            bound--;
        }
        cout << n - bound << endl;
    }
    return 0;
}

C. Circle of Monsters

一只怪物阵亡之后，就会对后面一只怪物造成伤害，而如果后面的这只怪物不能因为上一只怪物的爆炸而死亡的话，就只能用子弹射死，而第一只怪物的血量一定是因为子弹的攻击下降的。

又由于这些怪物围成了一个环，所以只需要枚举第一只击杀怪物是哪个，后续对怪物造成的伤害只需要补足即可。

显然，朴素做法是 $O(n^2)$ 的，并不可取，那么，是否有办法快速得到答案？

首先，这个一个环，常见的破环成链的做法就是复制一段接在后面，然后每次只取其中连续的 $n$ 只。

接着，如果击杀第一只怪物，那么第二只怪物就会因为第一只怪物的死亡而受到 $b_1$ 点伤害，如果不至死，就需要用子弹补足 $a_2 - b_1$ 点伤害，以此类推，可以将每只怪物需要补足的子弹数量算出来。

那么，在枚举先击杀第二只怪物时，不难发现，后续的怪物需要补足的子弹数量造成的伤害是相同的，唯一区别就是首只被击杀的怪物，需要用子弹耗尽 $a_2$ 滴血，与上述计算的值对比，只需要补足差值即可；同理，在枚举先击杀第三只怪物时，所相差的子弹数量也是类似的。

又因为我们需要求一段区间的子弹数量之和，很容易可以想到求个前缀，然后枚举先击杀哪只怪物，利用前缀和求个值再加上击杀首只怪物需要补的子弹数量。

最后，再在 $n$ 个数中取个最小值即为答案。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 6e5 + 5;
int n;
LL a[N], b[N];
LL cnt[N], sum[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i] >> b[i];
            a[i + n] = a[i];
            b[i + n] = b[i];
        }
        n <<= 1;
        for (int i = 1; i <= n; i++) {
            cnt[i] = a[i] - b[i - 1] > 0 ? a[i] - b[i - 1] : 0;
            sum[i] = sum[i - 1] + cnt[i];
        }
        LL res = 1e18;
        for (int i = 1; i <= n >> 1; i++) {
            LL ans = sum[i + (n >> 1) - 1] - sum[i - 1];
            ans += a[i] - cnt[i];
            res = min(res, ans);
        }
        cout << res << endl;
    }
    return 0;
}

D. Minimum Euler Cycle

贪心的思想，能向字典序小的点走就往那个点走，然后拿纸笔涂涂画画就能发现其中会有规律，然后慢慢写循环模拟即可。

对于以某个点为顶点的循环总数是可以计算得到的，如果加上这些数量还达不到要求的区间，则可以直接跳过，进入下一个循环，而题目要求的区间总长度不会太大，所以这种模拟枚举不会超时。

规律其实不难找，动手画一画就能知道，这里就不再赘述

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
LL n, l, r;

bool check(LL s)
{
    return s >= l && s <= r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> l >> r;
        LL step = 0;
        step++;
        if (check(step))
            cout << 1 << ' ';
        for (int ne = 2; ne < n; ne++) {
            if (check(++step))
                cout << ne << ' ';
            if (check(++step))
                cout << 1 << ' ';
        }
        if (check(++step))
            cout << n << ' ';
        for (int st = 2; st < n && step < r; st++) {
            LL s = 2 * (n - st);
            if (step + s < l) {
                step += s;
                continue;
            }
            if (check(++step))
                cout << st << ' ';
            for (int ne = st + 1; ne < n && step < r; ne++) {
                if (check(++step))
                    cout << ne << ' ';
                if (check(++step))
                    cout << st << ' ';
            }
            if (check(++step))
                cout << n << ' ';
        }
        if (check(++step))
            cout << 1 << ' ';
        cout << endl;
    }
    return 0;
}

E. Divisor Paths

我们将 $u -> v$ 的最短路径分成两部分考虑，即：找一个公共点 $w$，使得 $u -> w,\ w-> v$ 分别最短。

由于一个点，只能向它的质数倍数的点或者除以质数次后的点移动，而要找一个 $w$，使它离 $u, v$ 都较近，直觉上讲应该选择 $gcd(u, v)$ 作为 $w$ 的选择，因为当 $w < gcd(u, v)$ 时，减少的那部分还需要另一部分路径加回来，而如果选一个 $>u, v$ 的点作为 $w$ 的话，最小公倍数吗？但这个数可能很大，所以我们选择 $gcd(u, v)$ 作为中间点。

严谨的证明可以参照官方题解或者利用搜索引擎！！！蒟蒻就不再不自量力了

那么路径数量怎么计算？

以 $w->u$ 为例（因为是无向边，所以两个点固定的情况下，谁是起点谁是终点没有影响），它们之间相差了 $\frac{u}{w}$，这个数可以拆分成若干个质数的乘积，$w$ 每乘一个其中的质数就相当于走了一条边到达另一个点，而乘质数的顺序是可以任意的，只要一点点组合数的知识就可以推出来，比如：

拆分后一共有 $cnt$ 个质数，其中 $2$ 有 $c_1$ 个，$3$ 有 $c_2$ 个，…, 那么，需要在 $cnt$ 个坑中占 $c_1$ 个坑给 $2$，即：$C_{cnt}^{c_1}$，需要在剩下的 $cnt - c_1$ 个坑中占 $c_2$ 个给 $3$，即：$C_{cnt - c_1}^{c_2}$…，以此类推，不难得出其计算公式如下：
$$ cnt! \cdot \frac{1}{c_1!} \cdot \frac{1}{c_2!} \cdot … \cdot \frac{1}{c_k!} $$
同样的，$w->v$ 也可以用上述公式得到一个数，而最终的方案数就是这两个数的乘积。

再来看数据范围，$D$ 很大，也就是说 $\frac{u}{w}, \frac{v}{w}$ 也可能达到这个数量级，如果对于每个询问，都暴力找能够被 $\frac{u}{w}, \frac{v}{w}$ 整除的质数以及质数个数的话，会导致程序 $TLE$.

那么，能够优化这个过程？

由于每个 $u, v$ 都是 $D$ 的约数，所以，如果 $D$ 不能被某个质数整除，那么，$u, v$ 也就一定不行。

因此，我们只需要实现预处理出来能够被 $D$ 整除的所有质数，然后在每个询问的 $u, v$ 里，只对这些质数进行试除并计算个数，就会减少很多重复的计算量，让程序能够顺利 $AC$.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 51, mod = 998244353;
LL D;
vector<LL> primes;
int u[N], d[N];

void get_primes()
{
    for (int i = 2; i <= D / i; i++)
        if (D % i == 0) {
            primes.push_back(i);
            while (D % i == 0)
                D /= i;
        }
    if (D > 1)
        primes.push_back(D);
    return;
}

int quickpow(int a, int b)
{
    int res = 1;
    while (b) {
        if (b & 1)
            res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

void init()
{
    u[0] = d[0] = 1;
    for (int i = 1; i < N; i++) {
        u[i] = 1ll * u[i - 1] * i % mod;
        d[i] = quickpow(u[i], mod - 2);
    }
    return;
}

LL gcd(LL a, LL b)
{
    while (b) {
        LL t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int solve(LL n)
{
    int res = 1, cnt = 0;
    for (auto p : primes)
        if (n % p == 0) {
            int s = 0;
            while (n % p == 0) {
                s++;
                n /= p;
            }
            cnt += s;
            res = 1ll * res * d[s] % mod;
        }
    if (n > 1)
        cnt++;
    return 1ll * res * u[cnt] % mod;
}

int main()
{
    init();
    scanf("%lld", &D);
    get_primes();
    int q;
    scanf("%d", &q);
    while (q--) {
        LL a, b;
        scanf("%lld %lld", &a, &b);
        LL c = gcd(a, b);
        printf("%lld\n", 1ll * solve(a / c) * solve(b / c) % mod);
    }
    return 0;
}

F. Strange Function

使删掉的数最小，也就是说留下的数要最大，可以从这个方面入手。

我们来考虑用动态规划在解决这个问题：

$dp[i]$ 表示 $a$ 数组中第 $i$ 位能够出现在 $b$ 数组中的所有情况的集合，属性为最大值。

先来考虑第一位数，假设 $a$ 数组中第 $i$ 位为操作过后对应于 $b$ 数组的第一位数，那么，前 $i - 1$ 个数都应该删去，否则的话就会矛盾，显然此时 $dp[i] = p[i]$.

那么如何转移到第二位数？

假设 $a$ 数组中第 $j$ 位为操作过后对应于 $b$ 数组的第二位数，就应该存在若干个 $i$，第 $i$ 位可以成为操作后的第一个数的备选方案，且 $i < j$，此时，$j$ 就可以从这些 $i$ 中转移：
$$ dp[j] = max\{dp[i] + (i到j范围内所有小于等于操作后第1位数的且价格为正数的所有价格之和)\} $$
首先，如果是负数价格的数如果留下了，就一定会使得留下的数变小，而如果价格为 $0$ 的数，如果在能选择留下与删除的情况下，都不会对答案造成影响，所以可以直接删掉价格非正的数；其次，如果 $i$ 到 $j$ 中有数大于操作后第 $1$ 位数了，那么就会取代 $a_j$ 的位置，因此也需要删掉。那么，剩下的数就应该在 $i$ 转移到 $j$ 的过程中累加上。

同理，如果第 $j$ 位为操作过后的第 $k$ 位数，那么转移方程就应该这样：
$$ dp[j] = max\{dp[i] + (i到j范围内所有小于等于操作后第k - 1位数的且价格为正数的所有价格之和)\} $$
那么最后答案如何计算？

不难发现，对于所有满足 $a_i = b_m$ 的下标 $i$ 而言，$dp_i$ 还需要加上 $i$ 到 $n$ 范围内所有小于等于操作后第 $m$ 位数的且价格为正数的所有价格之和，这样才能保证操作之后的序列能够完全与 $b$ 相等。

因此，留下的数的最大值就应该在上述值中取最大值，而最终答案数量就应该为所有数价格总和减去该最大值。

那么如何快速完成上述操作？

总结一下可以发现，上述操作涉及到了区间求和以及单点更新，这两个操作可以用线段树来维护，当然，更简便的方法是用树状数组。

由于在状态转移方程中，只涉及了 $b$ 数组中相邻两个数在 $a$ 中对应的下标之间的关系，我们可以在状态转移之前把这些下标找出来排个序，然后依次枚举更新。

而在更新完之后，就需要为下一次转移做准备，将 $a$ 数组中满足下一次转移需求的价格都用单点更新操作更新到树状数组中。

至此，就能够 $AC$ 此题。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 5e5 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int a[N], p[N], b[N];
LL sum[N], dp[N];
unordered_map<int, vector<int>> pos;
vector<PII> a_id;

int lowbit(int x)
{
    return x & -x;
}

void add(int p, int c)
{
    for (int i = p; i <= n; i += lowbit(i))
        sum[i] += c;
    return;
}

LL get(int p)
{
    LL s = 0;
    for (int i = p; i; i -= lowbit(i))
        s += sum[i];
    return s;
}

LL get(int l, int r)
{
    return get(r) - get(l - 1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        pos[a[i]].push_back(i);
        a_id.push_back({ a[i], i });
    }
    sort(a_id.begin(), a_id.end());
    for (int i = 1; i <= n; i++)
        scanf("%d", p + i);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        scanf("%d", b + i);
    memset(dp, -0x3f, sizeof dp);
    for (auto t : pos[b[1]])
        dp[t] = p[t];
    int a_id_pos = 0;
    while (a_id_pos < n && a_id[a_id_pos].first <= b[1]) {
        int id = a_id[a_id_pos++].second;
        if (p[id] > 0)
            add(id, p[id]);
    }
    for (int i = 2; i <= m; i++) {
        vector<int> all_pos;
        for (auto t : pos[b[i - 1]])
            all_pos.push_back(t);
        for (auto t : pos[b[i]])
            all_pos.push_back(t);
        sort(all_pos.begin(), all_pos.end());
        int last = 0;
        LL best = -INF;
        for (auto t : all_pos) {
            best += get(last + 1, t);
            last = t;
            if (a[t] == b[i - 1])
                best = max(best, dp[t]);
            else
                dp[t] = best + p[t];
        }
        while (a_id_pos < n && a_id[a_id_pos].first <= b[i]) {
            int id = a_id[a_id_pos++].second;
            if (p[id] > 0)
                add(id, p[id]);
        }
    }
    LL res = 0, best = -INF;
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[m])
            best = max(best, dp[i] + get(i + 1, n));
        res += p[i];
    }
    res -= best;
    if (res > INF / 2)
        printf("NO\n");
    else
        printf("YES\n%lld\n", res);
    return 0;
}

G. Substring Search

$fft$？？？打扰了，溜了溜了等以后变强了再说