A.Exercising Walk

题意：

一只猫初始在点 $(x,y)$ ，你需要移动它 $a+b+c+d$ 次，其中 $a$ 次向左移动一个单位， $b$ 次向右移动一个单位， $c$ 次向下移动一个单位， $d$ 次向上移动一个单位，你可以任意安排移动次序，询问这只猫能否每次移动后均位于 $(x1,y1)$ 到 $(x2,y2)$ 的矩形内。

题解：

每次左移和右移可以抵消，上移和下移可以抵消，所以最终只要判断 $(x+b-a,y+d-c)$ 在不在范围内即可。但是要特判一下 $x1$ 和 $x2$ 或者 $y1$ 和 $y2$ 是否相等，这种情况移动一步都不行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

void solve()
{
    int a, b, c, d;
    int x, y, xa, ya, xb, yb;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    scanf("%d%d%d%d%d%d", &x, &y, &xa, &ya, &xb, &yb);
    x += b - a;
    y += d - c;
    if (xa == xb && (a || b))
        puts("No");
    else if (ya == yb && (c || d))
        puts("No");
    else if (x >= xa && x <= xb && y >= ya && y <= yb)
        puts("Yes");
    else
        puts("No");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Composite Coloring

题意：

用最多不超过 $11$ 种颜色，对一个数组 $a_n$ 染色（ $a_i≤1000$ 且不为质数），并满足同色的任意数字不互质。

题解：

平方小于 $1000$ 的质因数只有 $11$ 个，所以对每个数按最小质因数进行染色即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int p[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int vis[12],a[1005],color[1005];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 11; ++j)
            if (a[i] % p[j] == 0)
            {
                if (!vis[j])
                    vis[j] = ++cnt;
                color[i] = vis[j];
                break;
            }
    printf("%d\n", cnt);
    for (int i = 0; i < n; ++i)
        printf("%d ", color[i]);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.K-Complete Word

题意：

判断一个字符串最少修改几个字符可以满足以下条件：

该字符串为回文串；
该字符串的周期为 $K$

每次修改可以将任意字符替换成其他任意字符

题解：

周期所以满足这个 $K$ 个序列均相同，加上为回文，则要求每个序列内均为回文，那么可以算出每个序列前后对应位置的各个字符数量，取其中的最大值把其他的字符都变成这个算出贡献，每个序列内对应前后对数的贡献和就是答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
bool vis[maxn];
int cnt[26];
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    string s;
    cin >> s;
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
    {
        if (vis[i])
            continue;
        vector<char> v;
        for (int j = i; j < n; j += k)
            if (!vis[j])
            {
                v.push_back(s[j]);
                vis[j] = true;
            }
        for (int j = n - i - 1; j >= 0; j -= k)
            if (!vis[j])
            {
                v.push_back(s[j]);
                vis[j] = true;
            }
        memset(cnt, 0, sizeof(cnt));
        for (char c : v)
            cnt[c - 'a']++;
        int mx = *max_element(cnt, cnt + 26);
        ans += int(v.size()) - mx;
    }
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Walk on Matrix（构造）

题意：

有一个迷宫，要从左上角可以走到右下角。每次走到一个格子，都可以得到当前的分数 $\&$ 当前格子数字之后的分数。初始拿着的分数是：左上角的格子的数。要求到最终能得到的分数最大值是多少。
现在有一位参赛者写了一个这样的 $dp$ ：
图片说明
很快参赛者发现了他的 $dp$ 是有问题的，现在让你构造一个迷宫，使得 $dp$ 的输出和最优输出相差 $k$ .
其中 $1≤n,m≤500,0≤a_{i,j}≤3⋅10^5$
给定 $k$ ，要求输出 $n,m$ 以及对应的完整矩阵

题解：

原来的 $dp$ 代码会因为追求当前的最大与值而舍弃掉会使答案更大的较小值，按照相同思路构造即可。 $\left[ \begin{matrix} n+k & k & n \\ n & n+k & k \\ \end{matrix} \right]$
其中 $n$ 是比 $k$ 大的一个数，并且是 $2$ 的幂次
通过这个思路构造的 $dp$ 如下:

$\left[ \begin{matrix} n+k & k & 0\\ n & n & 0\\ \end{matrix} \right]$
所得结果为 $0$ ，然而最大值可以从 $(1,1)->(1,2)->(2,2)->(2,3)$ 为 $k$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
pll p[1005];
int main()
{
    int k;
    scanf("%d", &k);
    int n = 1 << 17;
    printf("2 3\n");
    printf("%d %d %d\n", n + k, k, n);
    printf("%d %d %d\n", n, n + k, k);
    return 0;
}

E.Height All the Same

题意：

一个 $N×M$ 的网格图上的每个网格初始放有高度在 $[L,R]$ 范围内的立方体木块。你每次能在这个网格图中选择一个位置加上 $2$ 个立方体木块，或者选择两个相邻位置各加上 $1$ 个木块，询问有几种初始状态能够经过有限次操作是的所有位置的木块高度一致。

题解：

因为不论怎么操作，都是给现有的方块堆加上 $2$ 个方块，因此奇偶性不变。我们假设初始最高的一堆木块高度为 $h$ ，如果最终能够使得所有位置高度一致为 $k$ ，则需要满足： $(n*m*k+(n*m*h−∑cnt[i][j])) \%2 = 0$ ，其中 $cnt[i][j]$ 指代网格图中位置为 $(i,j)$ 的方块数。
不难发现如果 $n*m$ 为奇数，则上式必然能成立，则方案数为 $(R−L+1)^{nm}$ ；若 $n*m$ 为偶数，则能否变成高度一致取决于 $n*m*h−∑pos[i][j]$ 的奇偶性，又因为此时 $n*m$ 为偶数，因此初始的总方块数若为奇数就必定不行，我们减去初始方块数为奇数的情况即为答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll ksm(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    ll n, m, l, r;
    scanf("%lld%lld%lld%lld", &n, &m, &l, &r);
    if ((n & 1ll) && (m & 1ll))
        printf("%lld\n", ksm((r - l + 1ll), n * m, mod));
    else
    {
        ll even = r / 2ll - (l - 1ll) / 2ll, odd = r - l + 1ll - even;
        ll ans = (ksm(r - l + 1, m * n, mod) - ksm(odd - even, m * n, mod) + mod) % mod;
        ans = (ans * ksm(2ll, mod - 2ll, mod)) % mod;
        ans = (ksm(r - l + 1, n * m, mod) - ans + mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}

F.Independent Set（树形dp）

题意：

给一棵树，你从中任意挑选出一个非空边集 $E$ ， $E$ 中的每条边都会连接两个点，这些点又形成了一个点集 $G$ ，在 $G$ 中再挑出独立集（独立集中任意两点没有边相连，空集也算独立集），问总共能挑出多少独立集（两种不同的边集最后挑出的含有相同点的独立集要算两种）

题解：

首先考虑选的边是全集的情况，这就是很经典的树形dp。 $dp[u][0]$ 表示当前节点没有染色的方案数， $dp[u][1]$ 表示当前节点染色的方案数，最终所求就是 $dp[1][0]+dp[i][1]$ ，状态转移方程： $\begin{cases} dp[u][0] = \prod_{v \in son[u]}^{}dp[v][1] \\ dp[u][1] = \prod_{v \in son[u]}^{}dp[v][0] \end{cases}$
考虑到这道题，我们只需要用 $dp[u][0]$ 表示当前节点没有被染色但与儿子节点有连边的方案数， $dp[u][1]$ 表示当前节点被染色但与儿子节点有连边的方案数， $dp[u][2]$ 表示当前节点与它的所有儿子节点所连的边均不选的方案数即可，用 $sum[u]$ 表示当前节点的所有方案数，因为如果当前节点与它的所有儿子节点所连的边均不选，那么儿子节点的状态就不会影响到当前节点，那么 $dp[u][0]$ 和 $dp[u][1]$ 均包含了 $dp[u][2]$ ，所以 $sum[u]=dp[u][0]+dp[u][1]-dp[u][2]$ ，可以得到状态转移方程： $\begin{cases} dp[u][0] = \prod_{v \in son[u]}^{} (dp[v][0]+dp[v][1] + sum[v]) \\ dp[u][1] = \prod_{v \in son[u]}^{} (dp[v][0]+sum[v]) \\ dp[u][2] = \prod_{v \in son[u]}^{} sum[v] \end{cases}$
于是最终所求就是 $sum[1]$ ，但是注意到题目要求边集非空，所以要减去边集为空这种情况，最终答案为 $dp[1][0]+dp[1][1]-dp[1][2]-1$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
vector<int> G[maxn];
ll dp[maxn][3];
int n;
void dfs(int u, int fa)
{
    dp[u][0] = dp[u][1] = dp[u][2] = 1;
    for (auto v : G[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
        ll sum = (dp[v][0] + dp[v][1] - dp[v][2] + mod) % mod;
        dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1] + sum) % mod;
        dp[u][1] = dp[u][1] * (dp[v][0] + sum) % mod;
        dp[u][2] = dp[u][2] * sum % mod;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld\n", (dp[1][0] + dp[1][1] - dp[1][2] - 1 + mod) % mod);
    return 0;
}

Codeforces Round #630 (Div. 2)