学到了什么
学到了虚脱
给学弟调树剖没调出来，我太菜了
- 断环成链的方法：任意选择一个位置断开，复制形成 2 倍长度的链。
- 区间DP的小套路
- 学文化课真爽
今日已完成
-
一节文化课：万能公式秒杀电容器动态分析
(E=dfrac{U}{d}=dfrac{Q}{varepsilon{S}})
如果再算上 (C=dfrac{Q}{U}) 就有七个物理量。
无脑带公式即可。
应用有- 判断受力
- 判断场强
- 判断静电计张角（看 (U)）
- 判断电容
- 定量计算
-
AcWing282 石子合并
区间DP基础题
int n, m, f[A][A], sum[A], a[A]; int main() { n = read(); for (int i = 1; i <= n; i++) a[i] = read(), sum[i] = sum[i - 1] + a[i]; memset(f, inf, sizeof(f)); for (int i = 1; i <= n; i++) f[i][i] = 0; for (int len = 2; len <= n; len++) { for (int l = 1; l <= n - len + 1; l++) { int r = min(l + len - 1, n); for (int k = l; k < r; k++) { f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]); } f[l][r] += sum[r] - sum[l - 1]; } } cout << f[1][n] << ' '; return 0; } -
AcWing283 多边形
区间 DP，断环成链降低时间复杂度。char s; int n, ys[A], w[A], f[2][A][A]; inline void checkmax(int &x, int y) { x = x < y ? y : x; } inline void checkmin(int &x, int y) { x = x < y ? x : y; } int main() { n = read(); for (int i = 1; i <= n; i++) { cin >> s >> w[i]; //x乘，t加 if (s == 't') ys[i] = 0; else if (s == 'x') ys[i] = 1; } for (int i = n + 1; i <= n * 2; i++) w[i] = w[i - n], ys[i] = ys[i - n]; memset(f[0], 0xcf, sizeof(f[0])); memset(f[1], 0x3f, sizeof(f[1])); for (int i = 1; i <= n * 2; i++) f[0][i][i] = f[1][i][i] = w[i]; for (int len = 2; len <= n; len++) { for (int l = 1; l <= n * 2 - len + 1; l++) { int r = l + len - 1; for (int k = l; k < r; k++) { checkmax(f[0][l][r], ys[k + 1] == 1 ? f[0][l][k] * f[0][k + 1][r] : f[0][l][k] + f[0][k + 1][r]); checkmin(f[1][l][r], ys[k + 1] == 1 ? f[1][l][k] * f[1][k + 1][r] : f[1][l][k] + f[1][k + 1][r]); if (ys[k + 1] == 1) { checkmax(f[0][l][r], f[0][l][k] * f[0][k + 1][r]); checkmax(f[0][l][r], f[1][l][k] * f[1][k + 1][r]); checkmax(f[0][l][r], f[0][l][k] * f[1][k + 1][r]); checkmax(f[0][l][r], f[1][l][k] * f[0][k + 1][r]); checkmin(f[1][l][r], f[0][l][k] * f[0][k + 1][r]); checkmin(f[1][l][r], f[1][l][k] * f[1][k + 1][r]); checkmin(f[1][l][r], f[1][l][k] * f[0][k + 1][r]); checkmin(f[1][l][r], f[0][l][k] * f[1][k + 1][r]); } } } } int ans = -32768; for (int i = 1; i <= n; i++) ans = max(ans, f[0][i][i + n - 1]); cout << ans << ' '; for (int i = 1; i <= n; i++) { if (f[0][i][i + n - 1] == ans) cout << i << " "; } return 0; } -
AcWing284 金字塔
区间DP，用 (f_{l,r}) 表示子串 (s_{l,r}) 对应着多少种可能的金字塔结构。
为了防止重复，只考虑子串 (s_{l,r}) 的第一棵子树是由哪一段构成的，枚举第一棵子树的划分点 (k)，令子串 (s_{l+1,k-1}) 作为第一棵子树，然后令子串 (s_{k,r}) 作为剩余部分。因为 (k) 不同，所以 (s_{l+1,r-1}) 就一定不同，因此就不会产生重复。
由此得到状态转移方程：
[f_{l,r}=egin{cases}0&s_{l} e{s_{r}}\f_{l+1,r-1}+sumlimits_{l+2le{k}le{r-2},s_{k}=s_{l}}f_{l+1,k-1} imes{f_{k,r}}&s_{l}=s_{r}end{cases} ]用记忆化搜索实现。
char s[A]; int n, f[A][A]; int solve(int l, int r) { if (l > r) return 0; if (l == r) return f[l][r] = 1; if (f[l][r] != -1) return f[l][r]; if (s[l] != s[r]) return f[l][r] = 0; f[l][r] = solve(l + 1, r - 1); for (int k = l + 2; k <= r - 2; k++) { if (s[l] == s[k]) f[l][r] = (f[l][r] + 1ll * solve(l + 1, k - 1) * solve(k, r) % mod) % mod; } return f[l][r]; } int main() { scanf("%s", s + 1); memset(f, -1, sizeof(f)); n = strlen(s + 1); cout << solve(1, n) << ' '; } -
AcWing285 没有上司的舞会
树形DP，找到一个不依赖别人的点作为根，然后进行树形DP，设 (f_{i,1/0}) 表示以 (i) 为根的子树，第 (i) 个点选或不选所能获得的最大价值，那么有：
[f_{i,0}=sumlimits_{toin{Son(x)}}max(f_{to,0},f_{to,1}) ][f_{i,1}=h_i+sumlimits_{toin{Son(x)}f_{to,0}} ]最后取 (max(f_{R,0},f_{R,1})) 就是答案，(R) 是选出的根节点，(Son(x)) 是 (x) 的子节点的集合。
struct node { int to, nxt; } e[A << 1]; int n, head[A], cnt, f[A][2], h[A], du[A], R; inline void add(int from, int to) { e[++cnt].to = to; e[cnt].nxt = head[from]; head[from] = cnt; } void dfs(int x) { f[x][1] = h[x], f[x][0] = 0; for (int i = head[x]; i; i = e[i].nxt) { int to = e[i].to; dfs(to); f[x][0] += max(f[to][0], f[to][1]); f[x][1] += f[to][0]; } } int main() { n = read(); for (int i = 1; i <= n; i++) h[i] = read(); for (int i = 1; i < n; i++) { int x = read(), y = read(); du[x] = 1; add(y, x); } for (int i = 1; i <= n; i++) { if (!du[i]) { R = i; break; } } dfs(R); cout << max(f[R][0], f[R][1]) << ' '; return 0; } -
P1895 数字序列
模拟int len[A]; int main() { for (int i = 1; i <= 1e5; i++) len[i] = len[i - 1] + ((int)log10(i) + 1); int T = read(); while (T--) { int n = read(); int k1 = 0, k2 = 0, tot = 0; while (++k1) { tot += len[k1]; if (tot >= n) break; } n -= (tot - len[k1]); while (++k2) { if (len[k2] >= n) break; } cout << k2 / (int)pow(10, len[k2] - n) % 10 << ' '; } return 0; }