A – 串
如果本身就不是回文串，那么答案就是 \(1\)；如果本身是的话，考虑找一个分割点使得左右都不是，那么答案就是 \(2\)；如果还是没找到，那么就是无解了，因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200, base = 133;
typedef unsigned long long ull;
int T, n;
ull basepow[MAX_N], posHash[MAX_N], revHash[MAX_N];
char str[MAX_N];
ull getPosHash(int l, int r) { return posHash[r] - posHash[l - 1] * basepow[r - l + 1]; }
ull getRevHash(int l, int r) { return revHash[l] - revHash[r + 1] * basepow[r - l + 1]; }
int main()
{
scanf("%d", &T), basepow[0] = 1;
for (int i = 1; i < MAX_N; i++)
basepow[i] = basepow[i - 1] * base;
while (T--)
{
scanf("%d%s", &n, str + 1);
for (int i = 1; i <= n; i++)
posHash[i] = posHash[i - 1] * base + str[i] - 'a';
revHash[n + 1] = 0;
for (int i = n; i >= 1; i--)
revHash[i] = revHash[i + 1] * base + str[i] - 'a';
if (posHash[n] != revHash[1])
puts("1");
else
{
bool flag = true;
for (int i = 1; i <= n; i++)
flag &= (getPosHash(1, i) == getRevHash(1, i)) || (getPosHash(i + 1, n) == getRevHash(i + 1, n));
if (flag)
puts("-1");
else
puts("2");
}
}
return 0;
}
B – 变量
这题比较显然可以看出是一个最小割的题目，然而建图还是比较难的。我们考虑最后算 \(W\)，然后把 \(p\) 个式子化简成：
\[ H_i=a_i|w[x_i]-w[y_i]|+b_i|w[y_i]-w[z_i]|+c_i|w[z_i]-w[x_i]|+ (d_i – f_i)w[x_i] + (e_i – d_i)w[y_i] + (f_i – e_i)w[z_i] \]
我们可以算 \(w_x \neq w_y\) 时的贡献，也就是双倍的系数和，记为 \(absmat[x][y]\)；算单纯的系数到 \(udtable[x][0/1], 0 \to +, 1 \to -\)。单纯的系数可以直接放在 \(S \to x\) 和 \(x \to T\) 的边上，哪个满流就被割掉；然后再枚举 \((x, y)\)，如果这两个之间的绝对值系数不为零，那么就连边 \((x, y, absmat[x][y])\)。
再考虑不等关系，如果 \(w[x] = w[y]\)，那么就连一条双向无限边使其强行等流；如果 \(w[x] < w[y]\)，那么就是说明 \(w[x] = -W, w[y] = W\)，就让他们的相对应的边满流防割即可；如果是 \(w[x] \leq w[y]\)，那么 \(w[y] \neq -INF\)，则防割即可。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4 + 200, MAX_M = 4e5 + 200, INF = 0x3f3f3f3f;
typedef long long ll;
int T, n, p, q, head[MAX_N], current, start_pos, end_pos, dep[MAX_N], cur[MAX_N], W;
int absmat[550][550], udtable[550][2];
struct edge
{
int to, nxt, weight;
} edges[MAX_M << 1];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void addtube(int src, int dst, int weight) { addpath(src, dst, weight), addpath(dst, src, 0); }
bool bfs()
{
memset(dep, 0, sizeof(dep));
queue<int> q;
q.push(start_pos), dep[start_pos] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (dep[edges[i].to] == 0 && edges[i].weight > 0)
dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
}
return dep[end_pos] != 0;
}
int dfs(int u, int flow)
{
if (flow == 0 || u == end_pos)
return flow;
for (int &i = cur[u]; i != -1; i = edges[i].nxt)
if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0)
{
int di = dfs(edges[i].to, min(flow, edges[i].weight));
if (di > 0)
{
edges[i].weight -= di, edges[i ^ 1].weight += di;
return di;
}
}
return 0;
}
int dinic()
{
int ret = 0;
while (bfs())
{
memcpy(cur, head, sizeof(head));
while (int di = dfs(start_pos, INF))
ret += di;
}
return ret;
}
int main()
{
scanf("%d", &T);
while (T--)
{
memset(head, -1, sizeof(head)), memset(udtable, 0, sizeof(udtable)), memset(absmat, 0, sizeof(absmat));
scanf("%d%d%d%d", &n, &W, &p, &q), current = 0;
start_pos = n + 1, end_pos = n + 2;
for (int i = 1, x, y, z, a, b, c, d, e, f; i <= p; i++)
{
scanf("%d%d%d%d%d%d%d%d%d", &x, &y, &z, &a, &b, &c, &d, &e, &f);
absmat[x][y] += (a << 1), absmat[y][x] = absmat[x][y];
absmat[y][z] += (b << 1), absmat[z][y] = absmat[y][z];
absmat[z][x] += (c << 1), absmat[x][z] = absmat[z][x];
udtable[x][0] += (d - f), udtable[x][1] -= (d - f);
udtable[y][0] += (e - d), udtable[y][1] -= (e - d);
udtable[z][0] += (f - e), udtable[z][1] -= (f - e);
}
for (int i = 1; i <= n; i++)
udtable[i][0]++, udtable[i][1]--;
for (int i = 1, x, y, r; i <= q; i++)
{
scanf("%d%d%d", &x, &y, &r);
if (r == 0)
addtube(y, x, INF);
else if (r == 1)
addtube(x, y, INF), addtube(y, x, INF);
else
udtable[x][0] = udtable[y][1] = INF;
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
int tmp = min({udtable[i][0], udtable[i][1], 0});
ans += tmp, addtube(start_pos, i, udtable[i][0] - tmp), addtube(i, end_pos, udtable[i][1] - tmp);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (absmat[i][j] != 0)
addtube(i, j, absmat[i][j]);
ans += dinic(), printf("%lld\n", 1LL * W * ans);
}
return 0;
}
C – 石子
博弈论题，需要细心的观察性质。
先把所有的 \(x_i\) 对 \(a + b\) 取个模，然后来讨论。假设 \(a < b\)：
- \(cnt_0\) 统计 \(x \in [0, a)\)，这个没啥用。
- \(cnt_1\) 统计 \(x \in [a, b)\)，这个部分可以导致 \(Alice\) 必胜。
- \(cnt_2\) 统计 \(x \in [b, 2a)\)，这个部分双方都可以选，所以这个的奇偶性会影响最后的博弈情况。
- \(cnt_3\) 统计 \(x \in [2a, a + b)\)，这个部分 \(Alice\) 可以把它弄成 \(1\) 的情况，使其必胜，所以这个东西的个数大于一，那么 \(Alice\) 是完全可以必胜的。如果只有一个，\(Bob\) 可以把它搞成 \(0\)。
考虑 \(Alice\) 必胜的条件，满足其一即可：
- \(cnt_1 > 0\)
- \(cnt_3 > 1\)
- \(cnt_3 = 1, cnt_2 \in odd\)。
\(Bob\) 显然不会胜利。我们考虑先手的胜利条件，在 \(cnt_1 = 0\) 时：
- \(cnt_3 = 1, cnt_2 \in even\)
- \(cnt_3 = 0, cnt_2 \in odd\)
后手胜的情况跟先手差不多，反过来即可。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200, mod = 1e9 + 7;
int n, a, b, xi[MAX_N], pow2[MAX_N], cnt[4];
int main()
{
scanf("%d%d%d", &n, &a, &b), pow2[0] = 1;
for (int i = 1; i <= n; i++)
scanf("%d", &xi[i]), pow2[i] = (pow2[i - 1] << 1) % mod, xi[i] %= (a + b);
bool swapped = false;
if (a > b)
swapped = true, swap(a, b);
int ans_a = 0, ans_b = 0, ans_first = 0, ans_second = 0;
for (int i = 1; i <= n; i++)
if (xi[i] < a)
cnt[0]++;
else if (xi[i] >= a && xi[i] < b)
cnt[1]++;
else if (xi[i] >= b && xi[i] < (a << 1))
cnt[2]++;
else
cnt[3]++;
ans_a = (0LL + pow2[n] + mod - pow2[n - cnt[1]] + 1LL * pow2[cnt[0] + cnt[2]] * (pow2[cnt[3]] + mod - cnt[3] - 1) % mod) % mod;
ans_first = 1LL * cnt[3] * pow2[cnt[0] + max(0, cnt[2] - 1)] % mod;
if (cnt[2])
{
ans_a = (0LL + ans_a + 1LL * pow2[cnt[0] + cnt[2] - 1] * cnt[3] % mod) % mod;
ans_first = (0LL + ans_first + pow2[cnt[0] + cnt[2] - 1]) % mod;
}
ans_second = pow2[cnt[0] + max(cnt[2] - 1, 0)];
if (swapped)
swap(ans_a, ans_b);
printf("%d %d %d %d\n", ans_a, ans_b, ans_first, ans_second);
return 0;
}