SDU暑期集训排位（9）

2024-09-01 06:17:20

SDU暑期集训排位（9）

G. Just Some Permutations

基础 DP 练习部分

定义 \(f(S)\)，表示让 S 中的人全 happy 的方案数。
\(dp[i][j]\) 表示，\(\sum_{|s|=j,s\subset\{1,...i\}} f(s)\)。
考虑从 \(dp[i][j]\) 开始的转移，可惜它转移不得，因为 \(i+1\) 个人，不知道自己能不能匹配成功。
DP 状态记录 \(i+1,i\) 是否被匹配，大部分情况下 \(i+1\) 个人可以匹配 \(i,i+1,i+2\)
Cornner Case 是 1 可以匹配 n，n 可以匹配 1，怎么办？
DP 状态记录 \(1,n\) 是否被匹配。
于是 \(dp[i][j][\{i,i+1,1,n\} 匹配了哪些]\) 就是个很优雅的状态了，枚举第 \(i+1\) 个人匹配谁即可实现转移。

基础组合数学部分

\(ans[i]\) 表示 \(\sum_{|s|=i} f(s)\)
rdc 做完基础 DP 练习后人解体了。
\(g(x)\) 表示恰有 \(x\) 个 happy 的人的方案数。
\(ans[i]=\sum_{j=x}^{n}g(j)\binom{j}{i}\)

基础的优化部分

比赛中 TLE 掉了。
需要每次都做 \(O(n*m*64)\) 的恐怖 DP？
考虑 \(n=200,m=200\)，\(n=100,m=100\) 这个两组 Case 发现 \(dp[1][]\) 到 \(dp[98][]\) 值一样的。
不需要啊，对每组查询，更新 \(dp[i-1],dp[i]\) 即可。

D. Flood in Gridland

单纯形。rdc 比赛中调了一年，因为不知道默认有 \(x_i \geq 0\) 的条件，没文化。
调出来后 WA。
sdcgvhgj 比赛后单纯形一发就过了。

最新文章

热门文章