首页 > 极客资料 博客日记
AT Educational DP Contest
2024-08-16 23:00:03极客资料围观22次
https://atcoder.jp/contests/dp
J - Sushi
设 \(f[i,j,k]\) 表示有 \(1/2/3\) 个寿司的盘子有 \(i/j/k\) 个
考虑随机到哪种盘子列出方程即可解出 \(f[i,j,k]\) 的递推式(\(k,j,i\) 递减)
或者注意到期望 \(\frac{n}{i+j+k}\) 次可以随机到非空盘子,再考虑是哪种
O - Matching
设 \(f[s]\) 表示前 \(i\) 个左部点匹配的右部点状态为 \(s\) 的方案数。时间复杂度 \(O(n^{2}2^{n})\)
注意到匹配的右部点状态为 \(s\) 时下一个被匹配的左部点一定是 \(\text{popcount}(s)\)。时间复杂度 \(O(n2^{n})\)
V - Subtree
(以 \(1\) 为根)设 \(fa[u]\) 为 \(u\) 的父亲,\(f[u]\) 表示 \(u\) 为 \(1\),子树 \(u\) 的方案数。\(f[u]=\prod(f[v]+1)\)
换根。问题是 \(f[v]+1\) 不一定有逆
(以 \(u\) 为根)设 \(ans[u]\) 为 \(u\) 为 \(1\) 的方案数,\(g[u]\) 为 \(u\) 为 \(1\),子树 \(fa[u]\) 的方案数
其中 \(\prod\) 通过维护前后缀积计算
W - Intervals
设 \(f[i,j]\) 表示前缀 \(i\) 中最后一个 \(1\) 位于 \(j\) 的最大收益,在 \(i=r\) 时计算 \((l,r,a)\) 的贡献,需要对第二维进行区间 \(+\),前缀 \(\min\)。线段树
X - Tower
真不会。也算是套路题,忘光了
要对序列而不是通常的集合做背包,所以需要考虑排序方式
考虑答案序列中相邻的元素 \(i,i+1\),需要满足 \(pre\le s_i,pre+w_i\le s_{i+1}\),交换后需要满足 \(pre\le s_{i+1},pre+w_{i+1}\le s_i\),后者能推出前者 \(\iff w_i-w_{i+1}\le s_{i+1}-s_i\),按 \(w_i+s_i\) 升序排序
Y - Grid 2
设值域为 \(X\)。从 \((0,0)\) 走到 \((x,y)\) 的方案数为 \(f(x,y)\)
考虑算补集。如果没有墙,那么 \(f(x,y)={x+y\choose x}\)。枚举非法路径上的第一个墙 \((x_0,y_0)\),方案数为 \(f(x_0,y_0)\times{x-x_0+y-y_0\choose x-x_0}\)
按二元组 \((x,y)\) 排序后 DP 即可
注意组合数要预处理到 \(2X\)。时间复杂度 \(O(X+n^2)\)
A - Frog 1 B - Frog 2
设 \(f[i]\) 表示跳到 \(i\) 的最小代价
C - Vacation
设 \(f/g/h[i]\) 表示第 \(i\) 天做了 \(a/b/c\) 的最大收益
D - Knapsack 1
01 背包
E - Knapsack 2
背包反转体积和价值
F - LCS
LCS 输出方案
G - Longest Path
DAG 最长路
H - Grid 1
设 \(f[i,j]\) 为走到 \((i,j)\) 的方案数
I - Coins
设 \(f[i,j]\) 表示前 \(i\) 个硬币有 \(j\) 个是正面的概率
K - Stones
设 \(f[i]\) 表示剩 \(i\) 个石子的时候先手是否必胜
L - Deque
设 \(f[l,r]\) 表示在区间 \([l,r]\) 博弈的先后手的分差
M - Candies
设 \(f[j]\) 表示前 \(i\) 个人分 \(j\) 个糖的方案数
N - Slimes
设 \(f[l,r]\) 表示把区间 \([l,r]\) 合并成一个的最小代价
P - Independent Set
设 \(f/g[u]\) 表示点 \(u\) 为 \(0/1\) 时子树 \(u\) 的方案数
Q - Flowers
带权 LIS
R - Walk
图上定长路径统计
S - Digit Sum
状态记录当前数位和 \(\bmod D\) 的值
T - Permutation
设 \(f[j]\) 表示前 \(i\) 个数中第 \(i\) 个数为第 \(j\) 大的方案数
U - Grouping
设 \(f[s]\) 表示集合 \(s\) 的最优解。枚举子集
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”