A. Exercising Walk
以 $x$ 的移动为例，令 $dis = x2 - x1$，那么当它累积向左移动 $dis$ 步，同时累积向右移动 $dis$ 步时就会回到起始点，所以我们可以先将所有能够回到起始点的步数都减掉，使得所需要向左移动的步数以及向右移动的步数中，至少有一个的范围在 $dis$ 以内。
此时就可以用 if else 判断，先向左移动几步，再向右移动几步，…，是否出界。由于至少有一侧的移动步数是小于 $dis$ 的，所以讨论的情况并不多，只是细节需要考虑清楚。
#include <bits/stdc++.h>
using namespace std;
bool check(int p, int l, int r, int a, int b, int dis)
{
if (a <= p - l) {
p -= a;
return b <= r - p;
}
a -= p - l;
if (b <= dis)
return a <= b;
b -= dis;
return a <= dis && b <= a;
}
int main()
{
int T;
cin >> T;
while (T--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int x, y, x1, y1, x2, y2;
cin >> x >> y >> x1 >> y1 >> x2 >> y2;
int dis = x2 - x1, s;
if (dis)
s = min(a / dis, b / dis);
else
s = 0;
a -= s * dis, b -= s * dis;
if (check(x, x1, x2, a, b, dis)) {
dis = y2 - y1;
if (dis)
s = min(c / dis, d / dis);
else
s = 0;
c -= s * dis, d -= s * dis;
if (check(y, y1, y2, c, d, dis))
cout << "YES" << endl;
else
cout << "NO" << endl;
} else
cout << "NO" << endl;
}
return 0;
}
B. Composite Coloring
当几个数都是同一个质数的倍数时，它们就可以被涂上相同的颜色。
而题目又保证了颜色数量在 $11$ 以内一定存在解，所以我们可以先把 $1000$ 以内的质数筛出来（数据范围比较小，也不需要用线性筛），然后对于每个质数，再找它的倍数，如果这个倍数在原数组中且未被染色，就涂上一个新的颜色，最后输出颜色数组即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N];
unordered_set<int> exist;
unordered_map<int, int> color;
bool vis[N];
void init()
{
for (int i = 2; i < N; i++)
if (!vis[i])
for (int j = 2; i * j < N; j++)
vis[i * j] = true;
return;
}
int main()
{
init();
int T;
cin >> T;
while (T--) {
exist.clear();
color.clear();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
exist.insert(a[i]);
}
int c = 0;
for (int i = 2; i < N && c <= 10; i++)
if (!vis[i]) {
bool find = false;
for (int j = 1; i * j < N; j++)
if (exist.count(i * j) && !color.count(i * j)) {
if (!find) {
c++;
find = true;
}
color[i * j] = c;
}
}
cout << c << endl;
for (int i = 1; i <= n; i++)
cout << color[a[i]] << ' ';
cout << endl;
}
return 0;
}
C. K-Complete Word
我们来考虑建立这样一张图：
将字符串中的 $n$ 个下标当做点，最终需要变为同一个字母的两个下标之间连一条无向边，由于具有传递性，所以只需要已判定的相同字母的下标集合中的任意一点，与新加入的点连边即可。
建完图之后就可以发现，所有需要出现相同字母的下标之间一定直接或者间接有边相连，否则的话，两个字母可以相同也可以不同。即：这张图上会出现若干个连通块。
对于每一个连通块，记录一下连通块中点的数量以及连通块中每个字母出现的次数，想要改变的次数最少，就是取该连通块中本就存在的字母数量最多的字母，让其它的字母全都变为该字母的操作次数。
最终将每个连通块的操作次数相加即为答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 8e5 + 5;
int n, k, res;
int cnt[30];
char str[N];
int h[N], e[M], ne[M], idx;
bool vis[N];
void add(int u, int v)
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void init()
{
if (idx) {
for (int i = 0; i < idx; i++)
h[i] = -1;
idx = 0;
} else
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
vis[i] = false;
return;
}
void dfs(int u)
{
vis[u] = true;
cnt[str[u] - 'a']++;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (vis[j])
continue;
dfs(j);
}
return;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
cin >> n >> k >> str + 1;
init();
for (int i = 1, j = n; i < j; i++, j--)
add(i, j), add(j, i);
for (int i = 1; i <= k; i++)
for (int j = i + k; j <= n; j += k)
add(i, j), add(j, i);
res = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]) {
memset(cnt, 0, sizeof cnt);
dfs(i);
int sum = 0, val = 0;
for (int i = 0; i < 26; i++) {
sum += cnt[i];
val = max(val, cnt[i]);
}
res += sum - val;
}
printf("%d\n", res);
}
return 0;
}
D. Walk on Matrix
在样例 $2$ 的启发下，我们能否构造出这样一组解，使得 $(n, m - 1)$ 从上方转移的值为 $k$，从左侧转移的值大于 $k$，但是和 $k$ 进行与运算之后的结果为 $0$.
矩阵中数的范围为 $3 \cdot 10^5$，而 $k$ 的数据范围只有 $10^5$，所以一定存在一个数 $t$，使得 $10^5 < 2^t < 3 \cdot 10^5$，我们就来构造如下矩阵（令 $val = 2^t$）：
val + k k 0
val k 0
val val + k k
此时 $(3, 2)$ 这个点从上方转移的话，值为 $k$；从左侧转移的话，值为 $val$；而 $val > k$ ，所以 $dp[3][3] = val$，又因为$val \ \& \ k = 0$，所以 $(3, 3)$ 这个点从左侧转移的话值为 $0$，而从上方转移值也为 $0$。因此，根据题目所给代码得到的 $dp[3][3]$ 结果为 $0$，而实际上，$(3, 2)$ 这个点选择从上方转移，再转移到 $(3, 3)$ 的话，最终的值为 $k$。$k - 0 = k$，正好满足题意要求。
综上，只需要找到一个 $val$，使得 $val + k \leq 3 \leq 10^5$，然后不论输入的 $k$ 是多少，直接输出该矩阵即可。
#include <bits/stdc++.h>
using namespace std;
const int val = 1 << 17;
int k, a[5][5];
int main()
{
cin >> k;
a[1][1] = a[3][2] = val + k;
a[2][1] = a[3][1] = val;
a[1][2] = a[2][2] = a[3][3] = k;
cout << 3 << ' ' << 3 << endl;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++)
cout << a[i][j] << ' ';
cout << endl;
}
return 0;
}
E. Height All the Same
只使用操作 $1$ 的话，我们总能把格子上方块的数量变成只相差一个或者直接相等：
- 若初始的各个格子方块的数量的奇偶性相同，则通过操作 $1$ 总能使格子上方块的数量同时达到某一个值。
- 若初始的各个格子方块的数量的奇偶性不同，则通过操作 $1$ 总能使格子上方块的数量两两直接相同或者只相差 $1$ 个。
只使用操作 $2$ 的话，我们总能改变两个格子上方块数量各自的奇偶性，例如用操作 $2$ 变换这些格子：$(m_1, m_2), (m_2, m_3), …, (m_{k - 1}, m_k)$，除了 $m_1, m_k$ 上方块数量只增了 $1$，改变了数量的奇偶性之外，中间的所有格子上方块的数量都增加了 $2$，不改变奇偶性；而如果在操作之前，$m_1, m_k$ 上的方块数量相等，中间各个格子的方块数量相等且比 $m_1, m_k$ 的方块数量多 $1$，则经过这个操作之后，再在 $m_1, m_k$ 上各自执行一次操作 $1$，这条路径上的方块个数就会相等。
受此启发，不难发现，如果初始方块个数是偶数的格子数量也是偶数个，则它们之间可以两两通过上述方式改变，最终使得每个格子上方块的数量相同，而当 $n \cdot m$ 是奇数时，我们总能变化成该情况，即此时无论初始状态是什么，最终都可以将各个格子上方块的数量变成相等的个数。
接下去讨论 $n \cdot m$ 为偶数的情况，假设 $[L, R]$ 区间内奇数有 $odd$ 个，偶数有 $even$ 个，此时若要从中挑选 $i$ 个格子填偶数，则应有如下数量的填法：
$$
even^i \cdot odd ^{n \cdot m - i} \cdot C_{n \cdot m}^{i}
$$
因此，我们分别取 $i$ 为 $even$ 以内的偶数，累加起来就是答案数量，即：
$$
\sum_{i = 0}^{\frac{n \cdot m}{2}}{even^{2 \cdot i} \cdot odd^{n \cdot m - 2 \cdot i} \cdot C_{n \cdot m}^{2 \cdot i}}
$$
而
$$
(even + odd)^{n \cdot m} = \sum_{i = 0}^{\frac{n \cdot m}{2}}{even^{2 \cdot i} \cdot odd^{n \cdot m - 2 \cdot i} \cdot C_{n \cdot m}^{2 \cdot i}} + \sum_{i = 1}^{\frac{n \cdot m}{2}}{even^{2 \cdot i - 1} \cdot odd^{n \cdot m - (2 \cdot i - 1)} \cdot C_{n \cdot m}^{2 \cdot i - 1}}
$$
$$ (even - odd)^{n \cdot m} = \sum_{i = 0}^{\frac{n \cdot m}{2}}{even^{2 \cdot i} \cdot odd^{n \cdot m - 2 \cdot i} \cdot C_{n \cdot m}^{2 \cdot i}} - \sum_{i = 1}^{\frac{n \cdot m}{2}}{even^{2 \cdot i - 1} \cdot odd^{n \cdot m - (2 \cdot i - 1)} \cdot C_{n \cdot m}^{2 \cdot i - 1}} $$
这两式相加即为答案的两倍，而中间过程取模之后可能改变奇偶性，而 $mod + 1$ 是偶数，且对 $mod$ 取模之后为 $1$，所以可以将答案乘上 $mod + 1$ 再除以 $2$ 来得到最终的结果。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 998244353;
LL quickpow(LL a, LL b)
{
LL res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
LL n, m, l, r;
cin >> n >> m >> l >> r;
if (n * m % 2)
cout << quickpow(r - l + 1, n * m) << endl;
else {
LL odd, even;
if (l & 1) {
odd = r - l + 1 + 1 >> 1;
even = r - l + 1 - odd;
} else {
even = r - l + 1 + 1 >> 1;
odd = r - l + 1 - even;
}
cout << (quickpow(odd + even, n * m) + quickpow(even - odd, n * m)) * (mod + 1) / 2 % mod << endl;
}
return 0;
}
F. Independent Set
对于每一种合法的方案，都可以对应成：将这种方案中的独立集中的点染上色，然后把其余所有点、边都加进来，但是其余点都不染色的方案。
因此我们来考虑如下动态规划：$dp[i][0]$ 表示只考虑以 $i$ 为根的子树，且 $i$ 这个点未被染色的所有方案数；$dp[i][1]$ 表示只考虑以 $i$ 为根的子树，且 $i$ 这个点被染色的所有方案数，由于每一条边的选与不选也会对答案产生影响，所以再定义一个 $f[i]$ 表示删除 $i$ 这个点与其儿子节点的边的方案数。
现假设我们需要计算 $i$ 这个节点的上述三个值，而当前从 $j$ 这个儿子节点回溯：
- 首先，对于一个节点有多个不同的儿子的时候，每个儿子节点为根的子树的选择方案都不会影响其它儿子，所以不断将答案累乘即可。
- 对于 $dp[i][0]:$ 在不选择 $i -> j$ 这条边的情况下，$j$ 可以染色也可以不染色，只是当 $j$ 染色的情况下，$j$ 连向其儿子节点的边就至少得选一条，否则的话 $j$ 这个点将孤立，而题意中最后挑选的独立集中的点不可能是孤立点，所以需要减去 $f[j]$，因此该情况的方案数为：$dp[j][0] + dp[j][1] - f[j]$；在选择 $i->j$ 这条边的情况下，$j$ 也可以选择染色与不染色，该情况方案数为：$dp[j][0] + dp[j][1]$.
- 对于 $dp[i][1]:$ 在不选择 $i->j$ 这条边的情况下，与 $dp[i][0]$ 同理，该情况方案数为：$dp[j][0] + dp[j][1] - f[j]$；在选择 $i->j$ 这条边的情况下，$j$ 这个点就不能再被染色，因此方案数为：$dp[j][0]$.
- 对于 $f[i]:$ 与 $dp[i][0]$ 不选择 $i->j$ 这条边的情况同理，方案数为：$dp[j][0] + dp[j][1] - f[j]$.
只需要在 $DFS$ 过程中维护这三个值即可，注意中间过程很容易爆 $int$.
至于最终的答案，不妨设根节点为 $1$，根节点可以选择染色也可以不染色，而当根节点染色时，其连向儿子的边至少得有一条，不然根节点就会被孤立（跟上文同理），因此方案数为：$dp[1][0] + dp[1][1] - f[1]$，只是需要注意的是，有一种特殊情况也被包含进了该方案数中，即：一条边都不选，一个点都不染色。该情况是不满足题意的，因为题目要求选出的边不能为空集，所以，只需要将这种情况减掉，就是我们最终答案，即：$dp[1][0] + dp[1][1] - f[1] - 1$.
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 6e5 + 5, mod = 998244353;
int n;
int h[N], e[M], ne[M], idx;
int f[N], dp[N][2];
void add(int u, int v)
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void dfs(int u, int fa)
{
dp[u][0] = dp[u][1] = f[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa)
continue;
dfs(j, u);
dp[u][0] = dp[u][0] * (((2ll * dp[j][0] + 2 * dp[j][1] - f[j]) % mod + mod) % mod) % mod;
dp[u][1] = dp[u][1] * (((2ll * dp[j][0] + dp[j][1] - f[j]) % mod + mod) % mod) % mod;
f[u] = 1ll * f[u] * (((dp[j][0] + dp[j][1] - f[j]) % mod + mod) % mod) % mod;
}
return;
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
dfs(1, -1);
printf("%lld\n", ((1ll * dp[1][0] + dp[1][1] - f[1] - 1) % mod + mod) % mod);
return 0;
}
G. No Monotone Triples
一开始写了个线段树来维护，测完样例之后发现看漏了题目的约束条件，然后，然后，然后就，好像，对于蒟蒻而言不太可做了？（等以后变强了再补，如果还记得的话
