[Noi2017] 游戏

sol

胡了假的3-sat, 预订明年的图灵奖了…

还是比较清楚这是一个2-sat模型:

先不考虑s_i=x的情况, 即该位置有种车是不能选择的.

进一步的, 也就是要在剩下的两种车中选择一个(恰好对应2-sat的选与不选)

继续阅读 [Noi2017] 游戏

[Snoi2017] 炸弹

sol

思维比较裸,考虑i点向可引爆的点x建条(i,x)的单向边。

直接想法: 线段树优化建图, 然后Tarjan即可。

那么就得到了一张DAG
缩完点后每个点的权值表示scc(i)中的炸弹个数

然后题目转化为求i连通块的所有后继节点的点权和。

继续阅读 [Snoi2017] 炸弹

[Pkuwc2018] 猎人杀

主要问题在于分母的数值时刻在变, 非常头疼.

考虑题目的转化:

定义枪杀i号猎人的概率为\frac{w_i}{\sum_{k=1}^n w_k}, 且当前局面可枪杀已死的猎人.
1号猎人可以留到最后的概率.

下面给出该转化的正确性证明.

继续阅读 [Pkuwc2018] 猎人杀

Stirling

为了方便: 简记第一类斯特林数为S_1,第二类斯特林数为S_2

\begin{aligned} {n\brack k}&=(n-1){n-1\brack k}+{n – 1\brack k – 1} \\ \binom nm &= m\binom {n-1}{m}+\binom {n-1}{m-1}\\ \end{aligned}

继续阅读 Stirling