20260808

感觉应该把 T1 写出来的，基本上已经想到了，但是思维太乱了。

然后骗分...大样例能过啊，评测机太慢了。

T1 最长不下降子序列 (sequence)

最长不下降子序列 (sequence)。

竟然是水题。。。

考场上也想到了，就是序列相当于是 1...12...21...12...21...12...21...12...2 这种，然后很显然第 dp。但是我不知道为什么，没有继续？

也许单纯是在睡觉吧，睡了 30−60min30-60min。

美食节 (food)

美食节 (food)。

首先很容易判定无解，然后我们可以一直贪心填最小的。用优先队列或 set 维护。

字符串 (str)

字符串 (str)。

其实仔细想想也不难。考场我暴力各种玄学优化过了大样例于是就不管了。

实际上可以用 trie 树配合 manacher，就用 s 碰到结尾的回文串，二分能向前的值，塞反着进 t 建立的 trie 里面。可以用哈希快速维护所有的。

概率 (pr)

概率 (pr)。

其实问题就是问和相等的概率，然后可以转化成每一个和的概率。

我是直接这样 dp。

正解是求总和为 nmnm 的概率，因为右边可以先设成负数再整体加。

如果没有 ≤m\le m 的限制可以直接隔板法，这让我们想到了容斥。

从总数里减去至少有一个数 ≥m+1\ge m+1 的情况，加上至少有两个数的...

最后答案就是：

∑i=02n(−1)i(2ni)(nm−(m+1)i+2n−12n−1)\sum_{i=0}^{2n} (-1)^i \binom{2n}{i} \binom{nm-(m+1)i+2n-1}{2n-1}