Poker
http://zhengruioi.com/problem/119
有 $n$ 张牌，点数分别为 $a_1 \cdots a_{n}$。小 $\text{M}$ 和小 $\text{D}$ 从牌堆中随机抽 $\dfrac{n}{2}$ 张牌并按顺序排列。然后，他们按顺序出牌，如果小 $\text{M}$ 的牌的点数大于小 $\text{D}$ 牌的点数，则小 $\text{M}$ 加一分。否则小 $\text{D}$ 加一分。问两人的期望得分。
分析
可以认为一开始两个人的得分为 $\dfrac{n}{4}$，然后对于每对相同的牌，如果它被分到两个不同的牌堆里 $\left(概率 = \dfrac{\dfrac{n}{2}}{n - 1}\right)$ 并且在同一时间的时候出牌 $\left(概率 = \dfrac{1}{n}\right)$，那么小 $\text{M}$ 减一分，小 $\text{D}$ 加一分，所以我们只要统计相同牌的对数即可。
代码
http://zhengruioi.com/submission/52384
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5, P = 1e9 + 7;
int n, a[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
int X = n / 2;
for (int i = 2; i <= n - 2; i++) {
X = 1ll * X * i % P;
}
int M = 1ll * X * (n - 1) % P * (n / 2) % P, D = M;
int cnt = 0, sum = 0;
for (int i = 2; i <= n; i++) {
if (a[i] == a[i - 1]) {
++cnt;
sum = (sum + 1ll * X * cnt) % P;
} else {
cnt = 0;
}
}
printf("%d %d\n", (M - sum + P) % P, (D + sum) % P);
return 0;
}Label
http://zhengruioi.com/problem/120
给定一个 $n$ 个点 $m$ 条边的带权无向图，有的点的点权已经给定，剩下的点的点权要你来确定。求 $\sum_{i = 1}^{m} {w_i \times (val[u_i] - val[v_i])^2}$ 的最小值。
分析
发现第 $i$ 个点的点权取到周围的一圈点的带权平均数最优。于是高斯消元解一下方程即可。
代码
http://zhengruioi.com/submission/52649
#include <cstdio>
const int maxn = 505;
const int maxm = 6e4 + 5;
int n, m, N, u[maxm], v[maxm], w[maxm];
int id[maxn], ID[maxn], val[maxn];
int tot, lnk[maxn], nxt[maxm], ter[maxm], wei[maxm];
double a[maxn][maxn], b[maxn], x[maxn], nv[maxn];
void addEdge(int u, int v, int w) {
nxt[++tot] = lnk[u];
lnk[u] = tot;
ter[tot] = v;
wei[tot] = w;
}
double abs(double x) {
return x < 0 ? -x : x;
}
void gauss() {
for (int i = 1; i <= N; i++) {
int idx = i;
for (int j = i + 1; j <= N; j++) {
if (abs(a[j][i]) > abs(a[i][i])) {
idx = j;
}
}
for (int j = i + 1; j <= N; j++) {
double d = a[j][i] / a[i][i];
for (int k = i; k <= N; k++) {
a[j][k] -= d * a[i][k];
}
b[j] -= d * b[i];
}
}
for (int i = N; i >= 1; i--) {
x[i] = b[i] / a[i][i];
for (int j = 1; j < i; j++) {
b[j] -= a[j][i] * x[i];
}
}
}
double sqr(double x) {
return x * x;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &u[i], &v[i], &w[i]);
if (u[i] == v[i]) continue;
addEdge(u[i], v[i], w[i]);
addEdge(v[i], u[i], w[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
if (val[i] == -1) {
id[i] = ++N;
ID[N] = i;
}
}
for (int i = 1; i <= N; i++) {
int u = ID[i], s = 0;
for (int e = lnk[u]; e; e = nxt[e]) {
s += wei[e];
}
a[i][i] = -1;
for (int e = lnk[u]; e; e = nxt[e]) {
int v = ter[e], w = wei[e];
if (val[v] == -1) {
a[i][id[v]] += w;
} else {
b[i] -= 1ll * w * val[v];
}
}
for (int j = 1; j <= N; j++) {
a[i][j] /= s;
}
b[i] /= s;
a[i][i] = -1;
}
/*
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
printf("%lf ", a[i][j]);
}
printf("%lf\n", b[i]);
}
*/
gauss();
for (int i = 1; i <= n; i++) {
nv[i] = val[i];
}
for (int i = 1; i <= N; i++) {
nv[ID[i]] = x[i];
}
double ans = 0;
for (int i = 1; i <= m; i++) {
ans += w[i] * sqr(nv[u[i]] - nv[v[i]]);
}
printf("%.9lf\n", ans);
return 0;
}
/*
3 2
1 2 3
2 3 1
0 -1 1
*/Coin
http://zhengruioi.com/problem/121
有一个 $n\times m$ 的棋盘，一个格子中有至多一个正面 / 反面朝上的硬币。小 $\text{M}$ 和小 $\text{D}$ 轮流操作，每次一个人可以选一个没有操作过的行 / 列，并将整行 / 列的硬币翻过来。当所有硬币正面朝上或者所有行列都被选择，游戏结束。最后一次操作的人得 $1$ 分。如果所有硬币正面朝上，小 $\text{M}$ 和小 $\text{D}$ 都会获得额外 $2$ 分的收益。如果两人都按最优策略操作，求小 $\text{M}$ 最后的得分。
分析
如果硬币不能全都正面朝上，那么答案就是 $n + m \bmod 2$。
先考虑判断硬币是否可以全部正面朝上。对于每个硬币 $(i, j)$，要求 $第\ i\ 行是否被翻过 \oplus 第\ j\ 列是否被翻过 = 硬币 (i, j) 是否反面朝上$。于是，我们使用类似二分图染色的方式即可判断。
那么如何判断先手是否必胜呢？每个连通块都是一个独立的平等游戏，所以可以考虑求它的 $\text{SG}$ 值。记一个染色后有 $a$ 个 $0$，$b$ 个 $1$ 的联通块为 $a - b$ 联通块。分情况讨论。
- $偶 - 偶$ 联通块转移到的 $sg$ 值为 $1$，因此本身的 $sg$ 值为 $0$。
- $奇 - 奇$ 联通块转移到的 $sg$ 值为 $0$，因此本身的 $sg$ 值为 $1$。
- $奇 - 偶$ 联通块转移到的 $sg$ 值为 $0, 1$，因此本身的 $sg$ 值为 $2$。
最后看看所有联通块的 $sg$ 值异或起来是否为 $0$ 即可。
代码
http://zhengruioi.com/submission/52703
#include <cstdio>
const int maxn = 105;
const int maxv = 205;
const int maxe = 20005;
int T, n, m, a[maxn][maxn];
int tot, nxt[maxe], lnk[maxv], ter[maxe], wei[maxe];
int col[maxv], cnt, sg[maxn], xs;
char s[maxn];
void addEdge(int u, int v, int w) {
nxt[++tot] = lnk[u];
lnk[u] = tot;
ter[tot] = v;
wei[tot] = w;
}
bool dfs(int u, int &x, int &y) {
if (col[u] == 0) {
x++;
} else {
y++;
}
for (int e = lnk[u], v, w; e; e = nxt[e]) {
v = ter[e], w = wei[e];
if (col[v] == -1) {
col[v] = col[u] ^ w;
if (dfs(v, x, y) == true) {
return true;
}
} else if (col[v] != (col[u] ^ w)) {
return true;
}
}
return false;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j++) {
a[i][j] = s[j] == 'e' ? -1 : s[j] == 'o' ? 0 : 1;
}
}
tot = 0;
for (int i = 1; i <= n + m; i++) {
lnk[i] = 0;
col[i] = -1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] != -1) {
addEdge(i, j + n, a[i][j]);
addEdge(j + n, i, a[i][j]);
}
}
}
cnt = 0, xs = 0;
for (int i = 1; i <= n + m; i++) {
if (col[i] == -1) {
int x = 0, y = 0;
col[i] = 0;
if (dfs(i, x, y) == true) {
printf("%d\n", (n + m) & 1);
goto theEnd;
} else {
if (x % 2 == 0 && y % 2 == 0) {
sg[++cnt] = 0;
} else if (x % 2 == 1 && y % 2 == 1) {
sg[++cnt] = 1;
} else {
sg[++cnt] = 2;
}
}
}
}
for (int i = 1; i <= cnt; i++) {
xs ^= sg[i];
}
if (xs == 0) {
puts("2");
} else {
puts("3");
}
theEnd:;
}
return 0;
}
/*
1
2 5
exexe
xeoex
*/
