YZ 集训 向再见说再见 & 已经没有什么好怕的了

二维 DP+ 计数

https://blog.csdn.net/doyouseeman/article/details/53712392

第一个思路是将一定转化为至少

然后考虑至少n方案数=k*一定m方案数+一定n方案数，推出公式。（或者二项式反演，这个好理解一点）

这类题好像也有用更加奇怪的姿势来推，这就算容斥，上面那个大概只能算计数。

然后那个至少的 dp 方程，应当从乘法原理去考虑才对。可能有一些 dp 方程从乘法原理造成的结果去考虑来设计比较好一点。

分手是祝愿

https://www.luogu.org/problemnew/show/P3750

开关灯 + 期望 DP

关于开关灯一个古老的套路就是看某个时刻如果必须关某个灯，就去关。因为每个灯要么按要么不按，所以已经关了的灯我们肯定不按。直到所有的灯都被关闭为止。

当然只限于一类可以贪心的开关灯。

然后就是一个跟开关灯压根没一点关系的 dp 方程。

这个状态设计成从状态 $A$ 转移到状态 $B$ 所需要耗费的期望代价。
转移方程设计成：状态A->B的概率*1+转移回状态C的概率*(状态C->A的代价+状态A->B的代价+1)

这个大概是一个非常好参考的期望 dp 设计思路。再一次体现了期望的状态嵌套特征以及一个转移耗费的代价。

亚瑟王

https://www.luogu.org/problemnew/show/P3239

中难期望 DP

期望 = 概率×权值

若权值已知，则只需求得概率。

猜测思路如下：
对问题的本质进行思考：若第 i 张之前有 j 张被取，那么 i 若最终没被取，被考虑的轮数一定是 r -j。因此可以得到 i 的最终未被取的概率 -> 最终被取的概率。

由此设计状态 $f_{i, j}$ 表示 1~i 张中有 j 张被取的概率。并能求出 i 最终被取的概率。

[SCOI2016]美味

还蛮有意思的
在可持久化 Trie 树上强行再套一个 $\log$ 来避免一次询问自带的修改

小 Y 的地铁

第一次见到需要分析复杂度的搜索（不是枚举嘛雾）

CF438E The Child and Binary Tree

将生成函数用于组合意义的递推

然后解多项式方程...

CF960G Bandit Blues

https://www.luogu.org/blog/wsy/solution-cf960g

第一类斯特林数在确定 $n$ 的情况下可以用 $log^2$ 的时间构造生成函数求出。
本题确定了 $n$ 可以分成前后两半，然后发现 dp 方程就是第一类斯特林数。
然后就可以转化问题，$n-1$ 个数分成 $a+b-2$ 个环，然后再选出 $a-1$ 个环放在 $n$ 的前面。

射命丸文的笔记

直接统计一条哈密顿回路会在多少个竞赛图里出现，则总个数（一共有 $\frac{n!}{n}$ 种哈密顿回路，每种哈密顿回路出现在 $2^{C(n,2)-n}$ 种竞赛图里）：
$$\frac{n!}{n}\cdot 2^{C(n,2)-n}$$

求解有多少个强连通 $n$ 点竞赛图 $f_n$，枚举 缩点之后 拓扑序最小的强连通分量大小，然后其它点随便连，也就是：
$$f[n]=2^{C(n,2)}-\sum_{i=1}^{n-1}{f[i]\cdot C(n,i)\cdot 2^{C(n-i,2)}}$$

然后分治 NTT 优化。

付公主的背包

弄出每个无限物品的生成函数然后乘起来，显然复杂度并不够乘

那么对每个无限物品的生成函数手推 $\ln$ 然后再加起来然后再 $\exp$ 回去就是乘起来的结果了

发现前一步可以调和级数。

州区划分

子集卷积优化状压 dp
发现卷了自己，但其实在我们用 FWT 来做子集卷积的时候已经体现了一个分治 FWT 的过程（而在时间复杂度上我们确实也多了一个 $\log$）。记得卡卡常，逆元一开始就处理好，以及数组一定要稍微开大一点点...

CF622C Binary Table

包装得挺好... 考虑竖过来看，即翻转了每一行之后我们可以取每一列的 0 和 1 的数量最小值相加，就是当前行翻转状态的最优解。那么我们干脆钦定每一列是选 0 或者 1 的数量，然后就有个 $2^nm$ 的裸 dp。进一步考虑，如果 $i$ 与钦定每一列的 01 状态值 $j$ 有 $k$ 个相同值那么对于 $j$ 这个状态的贡献是 $min(k, n-k)$，然后我们就有个很妙的做法就是有 $k$ 个不同值 -> 异或 $k$ 个位置为 $1$ 的值然后就 FWT 完事了（

LP5250 东京夏日相会

求一群圆的最小圆覆盖
然后题解是这么说的在圆上取点，角度小于 $acos(1-0.005/r)$ 时误差可小于 $0.01$
然后我不知道为什么直接加弧度就 gg 了而加角度就是对的...

LP3793 由乃救爷爷

分块 O(1)魔法 RMQ
Win 上卡常还跟 Linux 上不同，绝了... 在 Win 上没什么明显作用的优化到 linux 上就快了...

总而言之，分块 + 好好安排数组位置还是挺有用的

CF528D Fuzzy Search

多项式匹配字符串
反正就是匹配串扭个转，然后卷积到一个位置上，看看位置上的那个数字达到要求没有

LP4173 残缺的字符串

比较玄妙的做法吧
yyb 多项式例题

IIIDX

思维绕进死胡同就没法紧急转弯的典型例子...
在考场上究竟如何才能果断抛弃一种做法去选择另外一种没有一点关联的做法也是很有意思的问题。

Coat

事实证明像这种标算看上去就复杂而且常数很大的东西都能被暴力踩过（雾）
涉及到了那个最近总是被提到的式子以及背包的优化做法以及玄学的常数优化...

Diff

对于二分图匹配，假设点数较小一侧为 $n$，那么右侧非孤立点数最多为 $n^2$，且左侧每个点边数也最多为 $n$。

Copperative Game

最裸的 floyd 判环可过。要用到一个简单的任何一篇 floyd 判环讲解的博客都会提到的结论。

问题就在于怎么实现两步内让 $slow$ 走一步，让 $fast$ 走两步。这个应该不难吧。

Deadline

rua 什么题目

从最小点覆盖的角度去解释，感觉可以感性理解，就这样吧。

[Code Plus#4] 最短路

如果我们从一个点 i，每次只走到变某一位的点，最后走到 j，那么满足至少存在一条 边权和 = i xor j 的路径，这个是比较显然的。

本文链接：https://pst.iorinn.moe/archives/some-problems.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆