A. Sum of Odd Integers

奇数个奇数相加为奇数，偶数个奇数相加为偶数，同时，$k$ 个不同的奇数之和的最小值可以由等差数列求和直接确定。

因此，只需要 if else 判断一下即可。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        if ((n & 1) != (k & 1) || n < 1ll * k * k)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

B. Princesses and Princes

不难发现，如果 $n$ 个公主与 $n$ 个王子能够一一配对，那么根据规则匹配的时候，每一个公主都可以唯一确定一个王子。

相反，如果不能够一一配对，则只需要任意选择一个未配对的公主和一个未配对的王子，在他们之间连线即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n;
bool vis[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++)
            vis[i] = false;
        int g = -1;
        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            bool success = false;
            while (k--) {
                int p;
                cin >> p;
                if (!vis[p] && !success)
                    vis[p] = success = true;
            }
            if (!success)
                g = i;
        }
        if (g == -1)
            cout << "OPTIMAL" << endl;
        else {
            cout << "IMPROVE" << endl;
            for (int i = 1; i <= n; i++)
                if (!vis[i]) {
                    cout << g << ' ' << i << endl;
                    break;
                }
        }
    }
    return 0;
}

C. Game with Chips

由于 $chip$ 在移动时可以重合，那么，我们可以先将所有的 $chip$ 移动到左上角，再遍历一遍所有格子，此方法需要移动的次数为：$n - 1 + m - 1 + n \cdot (m - 1) + n - 1$.

其中 $n - 1 + m - 1$ 为将所有 $chip$ 移动到左上角的移动次数；$n \cdot (m - 1) + n - 1$ 为从左上角的格子开始遍历一遍所有格子所需要的移动次数。推这个式子比较简单，这里就不再赘述

整理一下，上式为：$n \cdot m + n + m - 3$

题目要求操作总次数不能操作 $2 \cdot n \cdot m$

那么 $n \cdot m + n + m - 3 \leq 2 \cdot n \cdot m$ 是否成立？

先将 $m$ 当成常数，上式可以化为：$n \cdot (1 - m) \leq 3 - m$

此时可以分情况讨论一下：

• $m = 1:$ $0 \leq 2$ 成立。
• $m > 1:$ 此时 $1 - m < 0$，那么 $n \geq \frac{3 - m}{1 - m} = 1 + \frac{2}{1 - m} \geq 1$，即：$n \geq 1$，成立。

综上，$n \cdot m + n + m - 3 \leq 2 \cdot n \cdot m$ 一定成立。

因此，直接输出上述移动过程即可。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 210;
int n, m, k;
PII s[N], f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
        cin >> s[i].first >> s[i].second;
    for (int i = 1; i <= k; i++)
        cin >> f[i].first >> f[i].second;
    cout << n * m + n + m - 3 << endl;
    for (int i = 1; i < n; i++)
        cout << 'U';
    for (int i = 1; i < m; i++)
        cout << 'L';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++)
            cout << (i & 1 ? 'R' : 'L');
        if (i < n)
            cout << 'D';
    }
    cout << endl;
    return 0;
}

D. Infinite Path

对于 $p ^1$ 这个序列而言，从任意一个起点 $i$ 开始，它的下一个点是 $p_i$，再下一个点是 $p_{p_i}$，以此类推。

对于 $p ^ 2$ 这个序列而言，从任意一个起点 $i$ 开始，它的下一个点是 $p_{p_i}$，再下一个点是 $p_{p_{p_{p_i}}}$，以此类推。

......

不难发现，如果事先固定 $p ^ 1$ 中的某个循环圈，只考虑这个循环圈中的数的话，在 $p ^ k$ 这个序列中的某些循环，就是在原循环圈中，间隔着 $k - 1 $ 个取数，判断这些数是否颜色相等。

例如：若事先固定的循环圈长度为 $m$，那么，在 $p ^ 2 $ 这个序列中的循环就包括：

• 原循环圈中下标为 $0, 2, 4, …, 2 \cdot (n - 1)\ \% \ m$ 直至循环。
• 原循环圈中下标为 $1, 3, 5, …, (2 \cdot n - 1)\ \% \ m$ 直至循环。
• 当起始下标为 $2$ 时，就相当于是从起始下标 $0$ 开始，只是循环中的数出现的顺序不同而已，此时就可以跳出这个循环圈的枚举。

同时，在起点递增的等差数列取模中，如果公比与取模数互质，那么一定会遍历原循环圈中所有点才能找到循环，此时就相当于 $k = 1$ 时的情况，所以上述的枚举只需要考虑满足 $k \mid m$ 的 $k$ 即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
int n, res;
int p[N], c[N];
vector<int> color;
bool vis[N];

void get_res(int n, int d)
{
    for (int i = 0; i < d; i++) {
        bool success = true;
        for (int j = i + d; j < n; j += d)
            if (color[i] != color[j]) {
                success = false;
                break;
            }
        if (success) {
            res = min(res, d);
            break;
        }
    }
    return;
}

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 >> p[i];
            vis[i] = false;
        }
        for (int i = 1; i <= n; i++)
            cin >> c[i];
        res = n;
        for (int i = 1; i <= n; i++)
            if (!vis[i]) {
                color.clear();
                for (int j = i; !vis[j]; j = p[j]) {
                    vis[j] = true;
                    color.push_back(c[j]);
                }
                int sz = color.size();
                for (int i = 1; i <= sz / i; i++)
                    if (sz % i == 0) {
                        get_res(sz, i);
                        if (i != sz / i)
                            get_res(sz, sz / i);
                    }
            }
        cout << res << endl;
    }
    return 0;
}

E. Count The Blocks

设当前计算的长度为 $k$，那么，这段区间的数字有 $10$ 中选择，与这段区间相邻的数只能在与该区间不同的 $9$ 个数中选，剩余的位置都有 $10$ 种选法，由此就可以得到如下公式：
$$ 2 \cdot 10 \cdot 9 \cdot 10^{n - k - 1} + (n - k - 1) \cdot 10 \cdot 9 \cdot 9 \cdot 10^{n - k - 2} $$
上式经过化简整理可以得到：
$$ 18 \cdot 10^{n - k} + 81 \cdot (n - k - 1) \cdot 10^{n - k - 1} $$
枚举长度 $k$，就可以用上述公式计算出答案，当然，当 $k = n$ 时直接输出 $10$ 即可。

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

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;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
        cout << (18ll * quickpow(10, n - i) % mod + 81ll * (n - i - 1) * quickpow(10, n - i - 1) % mod) % mod << ' ';
    cout << 10 << endl;
    return 0;
}

F. AND Segments

我们来考虑 $n$ 个数的某个二进制位有多少种填法，然后将 $k$ 个二进制位的填法相乘即为答案。

以第 $t$ 位二进制位为例：

如果存在 $(l_i, r_i, x_i)$，其中 $x_i$ 的第 $t$ 位为 $1$，那么 $[l_i, r_i]$ 这段区间的每个数的第 $t$ 位都只能为 $1$.

而在处理完 $m$ 组限制之后，某段区间 $[l, r]$ 的第 $t$ 位为 $0$，则这段区间至少需要有一个数的第 $t$ 位为 $0$ 才能满足要求。

我们用 $dp[i]$ 来表示这样一个集合：在只考虑前 $i$ 个数的前提下，最后一个第 $t$ 位二进制位为 $0$ 的恰好为第 $i$ 个数的所有情况。当然，这个集合的属性为数量。

接着我们来分情况讨论 $dp[i]$ 该从哪些集合转移：

1. 第 $i$ 个数的第 $t$ 位二进制位只能为 $1$，显然此时 $dp[i] = 0$.
2. 第 $i$ 个数的第 $t$ 位二进制位可以为 $0$，那么，在第 $i$ 个数之前存在一段离 $i$ 最近的区间 $[l, r],\ r < i$，使这段区间中数的第 $t$ 位都可以为 $0$ 且不能再向两边延伸，则 $dp[i]$ 的其中一部分就是 $[l, r]$ 这段区间的所有 $dp$ 值之和，表示这段区间中至少存在一个位置的第 $t$ 位为 $0$ 的方案数量；而对于在开区间 $(r, i)$ 中的数来说，它们虽然没有必须存在 $0$ 的限制，但是能填 $0$ 的位置填上 $0$ 也是一种方案，所以 $dp[i]$ 还需要加上 $(r, i)$ 中的 $dp$ 值之和。因此，$dp[i]$ 就可以计算为区间 $[l, i)$ 的和，这个快速求和的操作可以用前缀和来实现，而边界值可以经过预处理后快速得到。特别的，如果不存在 $l$，则需要在累加上前缀和后再加上 $1$，表示前面这一段可以全都填 $1$，这一种方案数。

那么最终数量是什么？

在处理完第 $t$ 位的 $n$ 个数之后，再进行一次上述的第二个操作就是第 $t$ 位能够填的方案数量，即：可以循环到 $n + 1$，此时 $dp[n + 1]$ 即为方案数量。

最终将 $k$ 位二进制位各自的 $dp[n + 1]$ 相乘即可。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
const int N = 5e5 + 5, K = 30, mod = 998244353;
int n, k, m;
PIII s[N];
int p[N], one[N];
int dp[N], sum[N];

int solve(int t)
{
    memset(p, 0, sizeof p);
    memset(one, 0, sizeof one);
    for (int i = 1; i <= m; i++) {
        int l = s[i].first.first, r = s[i].first.second, x = s[i].second;
        if (x >> t & 1)
            one[l]++, one[r + 1]--;
        else
            p[r] = max(p[r], l);
    }
    for (int i = 1, j = 0; i <= n + 1; i++) {
        one[i] += one[i - 1];
        dp[i] = 0;
        if (!one[i])
            if (!j)
                dp[i] = (sum[i - 1] + 1) % mod;
            else
                dp[i] = ((sum[i - 1] - sum[j - 1]) % mod + mod) % mod;
        sum[i] = (sum[i - 1] + dp[i]) % mod;
        j = max(j, p[i]);
    }
    return dp[n + 1];
}

int main()
{
    scanf("%d %d %d", &n, &k, &m);
    for (int i = 1; i <= m; i++) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        s[i] = { { l, r }, x };
    }
    int res = 1;
    for (int i = 0; i < k; i++)
        res = 1ll * res * solve(i) % mod;
    printf("%d\n", res);
    return 0;
}

G. Letters and Question Marks

不会字符串！！！（等以后变强了再补，如果没忘记的话