2025年11月

atcoder dp contest

0 条评论 OI 无标签 SunJude
感觉该学点基础了。E考虑状态换维。J合并无用状态。发现只需要关心不同寿司个数的盘子的数量，所以设 $f[a][b][c]$ 表示当前还剩下 $a/b/c/(n - a- b - c)$ 盘有 $0/1/2/3$ 个寿司。O设 $f_S$ 表示前 $k$ 个男人和包含在 $S(|S| =k)$ 中的女人配对的方案数，枚举和第 $k$ 个男人匹配的女人转移。R基本套路：$A$ 为邻接矩阵，求出...

dp trick 之「连续段插入 dp」

0 条评论 OI 无标签 SunJude
模拟赛 T2 遇到的。对这类问题，一般会按值大小插入以消除后效性，先只在每段内考虑限制，再在两个段合并时考虑限制。P5999题意转化为求有多少个 $1 \sim n$ 的排列 $p$ 满足 $p_i$ 两边的数字同时大于或同时小于 $p_i$，且 $p_1 = s, p_n = t$。设 $f_{i, j}$ 表示前 $i$ 个数，分成 $j$ 段的方案数。从小到大加入每个数，对于 $i \...

题解：CF675E Trains and Statistic

0 条评论 OI 无标签 SunJude
首先考虑，对于点 $i$，如果要到达一个一步到不了的点，应该怎么走。显然，应该从 $i$ 到一个中转点，再往后走。考虑中转点应该怎么取，贪心的，我们让中转点取 $[i + 1, a_i]$ 中 $a_p$ 最大的点 $p$，因为 $p$ 的右端点最靠右，可以到达更多的点。考虑令 $f_i = \sum_{j = i + 1} ^ {n} \rho_{i, j}$，答案就是 $\sum f_i...

风光长物宜眼量 | CSP-S 2025 游记

1 条评论 游记 无标签 SunJude
10.31出发！听了一些第一年来 CSP 的时候听的歌。第三年来山外了啊……没赶上学校合影，太坏了。晚上去试机，发现删除键不太好用，还不给换键盘，【数据删除】。旗杆底下面了很多人，换了很多徽章。试完机去哥群群友合影。开拍前一秒钟断电了，被资本做局这一块。以及我拍的怎么这么奶龙。这是 CSP2025 最诡异的 14 个人，你敢跟他们对视十秒吗？我可以打破这个魔咒吗。希望明天 rp ++。11....