\(\mathrm{sum}=10+30+0+100\)
唉,我果然只是暴力选手。
在一个 \(n\times m\) 的棋盘上,选择一个黑点可使得矩阵 \((1,1,x,y)\) 翻转。无法操作的人败。问 \(k\) 组棋盘一起下,是否先手必胜。
先手最优一定是选一直选棋盘的左上角,所以统计左上角是 \(1\) 的个数,询问是否是奇数。证明不会,看来得增加博弈论的知识储备。
inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } int k, n, m; int main() { for (int T = Read(); T--; ) { k = Read(); int ans = 0; for (int t = 1; t <= k; t++) { n = Read(), m = Read(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int x = Read(); if (i == 1 && j == 1) ans ^= x; } } puts(!ans? "ld win": "lyp win"); } return 0; }
在一个 DAG 找到一条长度不到 \(20\) 的 \(s\rightarrow t\) 的路径,使得路径方差最小。
先化方差:
\[\begin{aligned} \sigma^2&=\frac{1}{n}\sum_{i=1}^n(a_i-\bar{a})^2\\ &=\frac{1}{n}\sum_{i=1}^n(a_i^2-2a_i\bar{a}+\bar{a}^2)\\ &=\frac{1}{n}\sum_{i=1}^n(a_i^2-2a_i\bar{a})+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-\frac{1}{n}\sum_{i=1}^n2a_i\bar{a}+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-2\bar{a}^2+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-\bar{a}^2\\ \end{aligned} \]然后设 \(f_{i,j,k}\) 表示当前在 \(i\) 楼梯,已经走了 \(j\) 个楼梯,且消耗了 \(k\) 体力的最小体力平方和。则有:
\[f_{u,j,k}=\min_{v\to u,\mathrm{val}}\{f_{v,j-1,k-\mathrm{val}}+\mathrm{val}^2\} \]统计答案时把 \(f_{i,j,k}\) 代回去就行了。
const int N = 60, M = 310, V = 1010; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } int n, m; int f[N][M][V]; struct edge { int to, val, nxt; }e[M]; int head[N], tot; void add(int u, int v, int w) { e[++tot] = (edge) {v, w, head[u]}, head[u] = tot; } int main() { freopen("library.in", "r", stdin); freopen("library.out", "w", stdout); memset (f, 127 / 3, sizeof f); n = Read(), m = Read(); for (int i = 1; i <= m; i++) { int u = Read(), v = Read(), w = Read(); add(u, v, w); } f[1][0][0] = 0; for (int len = 0; len < 19; len++) for (int u = 1; u < n; u++) for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; for (int sum = 0; sum <= 1000; sum++) f[v][len + 1][sum + e[i].val] = min(f[v][len + 1][sum + e[i].val], f[u][len][sum] + e[i].val * e[i].val); } double ans = 1e9; for (int j = 1; j <= 20; j++) for (int k = 0; k <= 1000; k++) if (f[n][j][k] < f[0][0][0]) ans = min(ans, f[n][j][k] * 1.0 / j - (k * k * 1.0 / j / j)); printf ("%.4f", ans); return 0; }
将字符串 \(t\) 中的一些字符往前移动若干位得到 \(s\),求次数及方案。
设 \(f_{i,j}\) 表示 \(s\) 串中 \([i,n]\) 与 \(t\) 串 \([j,n]\) 匹配(有可能有剩余的)的最小次数。
则分三部分:
顺便维护 \(g_{i,j,[0,1]}\) 表示 \(f_{i,j}\) 从哪两个点转移过来的。
然后从 \(1,1\) 往后跳,把不定点排除,枚举剩下的点即可。
const int N = 2010; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } int T, n; char s[N], t[N]; int a[30][N], b[30][N]; int f[N][N], g[N][N][2]; bool NoMoveA[N], NoMoveB[N]; int main() { freopen("chinese.in", "r", stdin); freopen("chinese.out", "w", stdout); for (T = Read(); T--;) { scanf ("%s%s", s + 1, t + 1); memset (a, 0, sizeof a); memset (b, 0, sizeof b); memset (NoMoveA, 0, sizeof NoMoveA); memset (NoMoveB, 0, sizeof NoMoveB); n = strlen(s + 1); for (int i = n; i; i--) { a[s[i] - 'a'][i] = 1, b[t[i] - 'a'][i] = 1; for (int j = 0; j < 26; j++) a[j][i] += a[j][i + 1], b[j][i] += b[j][i + 1]; } memset (f, 127 / 3, sizeof f); f[n + 1][n + 1] = 0; for (int j = n; j; j--) f[n + 1][j] = f[n + 1][j + 1] + 1; for (int i = n; i; i--) { for (int j = n; j; j--) { if (f[i][j] > f[i + 1][j] && a[s[i] - 'a'][i + 1] < b[s[i] - 'a'][j]) f[i][j] = f[i + 1][j], g[i][j][0] = i + 1, g[i][j][1] = j; if (f[i][j] > f[i + 1][j + 1] && s[i] == t[j]) f[i][j] = f[i + 1][j + 1], g[i][j][0] = i + 1, g[i][j][1] = j + 1; if (f[i][j] > f[i][j + 1] + 1) f[i][j] = f[i][j + 1] + 1, g[i][j][0] = i, g[i][j][1] = j + 1; } } printf ("%d\n", f[1][1]); int x = 1, y = 1; while (x <= n && y <= n) { int nxtx = g[x][y][0], nxty = g[x][y][1]; if (nxtx == x + 1 && nxty == y + 1) NoMoveA[x] = 1, NoMoveB[y] = 1; x = nxtx, y = nxty; } for (int i = 1; i <= n; i++) { if (NoMoveA[i]) continue; for (int j = i; j <= n; j++) { if (NoMoveB[j] || s[i] != t[j]) continue; bool tmp = NoMoveB[j]; for (int k = j; k >= i + 1; k--) t[k] = t[k - 1], NoMoveB[k] = NoMoveB[k - 1]; NoMoveB[i] = tmp; t[i] = s[i]; printf ("%d %d\n", j, i); break; } } } return 0; }
给你 \(n\) 条线段(他们要么平行要么垂直),求那些线段可以围成矩阵。
每行用 bitset 存一个与每列是否有交点的状态,然后枚举两行求同时拥有两列的数量。时间复杂度 \(\mathcal{O}(n^3\omega^{-1})\),其中 \(\omega=32\),勉强卡过。
const int N = 2010; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } int n; int cnt1, cnt2; struct Segment { int x1, y1, x2, y2; }a[N], b[N]; bool isInt (int u, int v) { return b[v].y1 <= a[u].y1 && a[u].y1 <= b[v].y2 && a[u].x1 <= b[v].x1 && b[v].x1 <= a[u].x2; } bitset<N> con[N], tmp; ll ans; int main() { n = Read(); for (int i = 1; i <= n; i++) { int x1 = Read(), y1 = Read(), x2 = Read(), y2 = Read(); if (x1 != x2) { if (x1 > x2) x1 ^= x2 ^= x1 ^= x2, y1 ^= y2 ^= y1 ^= y2; a[++cnt1] = (Segment){x1, y1, x2, y2}; } else { if (y1 > y2) x1 ^= x2 ^= x1 ^= x2, y1 ^= y2 ^= y1 ^= y2; b[++cnt2] = (Segment){x1, y1, x2, y2}; } } for (int i = 1; i <= cnt1; i++) for (int j = 1; j <= cnt2; j++) if (isInt(i, j)) con[i].set(j, 1); for (int i = 2; i <= cnt1; i++) for (int j = 1; j < i; j++) { tmp = con[i] & con[j]; ll cnt = tmp.count(); ans += cnt * (cnt - 1) / 2; } printf ("%lld\n", ans); return 0; }