发表于 | 分类于 | | + s

BZOJ 1008
方法1：
这种要求方案数而且范围大的，一般都是打表找规律题。通过暴力打表，发现$m=2$的时候答案就是$2^n-2$，所以按照这个继续找规律，发现$m=3$的时候答案是$3^n$减一些有倍数关系的数，然后可以得出答案是$m^n-m(m-1)^{n-1}$
方法2：
对于$1-n​$等类似的排列计数问题，以动态规划和组合数学2种大方向为基本解决方向。每个格子有$m$种选择，有$n$个格子，所以总方案数为$m^n$。然后第一个格可以有$m$个宗教可以填，后面的格子只能有$m-1$总选择，因为不能和前面的宗教相同，根据乘法原理，答案是$m^n-m(m-1)^{n-1}$

阅读全文 »

发表于 | 分类于 | | + s

Bzoj 1050
求$s-​>t$的路径上最大边权与最小边权的比值最小，就是让最小边权尽量接近最大边权。
我们枚举每一边作为最小边权，然后我们将边权大于该边权的边按边权大小依次连上，直到$s$与$t$连通，那么这样$s->t$的路径上的最大边权一定是最后加的这个边，因为加了这条边使得$s$与$t$连通。这条路径上的边权都是大于等于最小边权小于等于最大边权，而最小生成树保证最大边权最小，也就是最小瓶颈路，所以这样就解决了问题。
注意可能有最小边就是最大边的情况，这种情况下答案为$1$

求两点问题，用一点去求另一点，是一个很好的方法

阅读全文 »

发表于 | 分类于 | | + s

FJYZOJ 1773
一个点无法到达后使一条路径的最短路径变化，那么这个点一定在这条路径的“中转点”上，所以我们FLoyd，找出最终的中转点，就是重要的点。但是如果有几个点都可以作为最终的中转点，那么这几个点都不是重要的。

阅读全文 »

发表于 | 分类于 | | + s

Codeforces 235B
这题可能一开始连状态都不知道怎么设，这里先给出一个结论，如果有一个O，那么分数加$1$，如果有两个O且之间没有X，那么分数加$2$.

我们来证明：
由$2C^2_n+n=n^2$
分两种情况
1 一个O的情况
在一个全是O序列中，O有$n$个
那么这些O对答案的贡献是$1$
这样完成就完成了一个O的情况的贡献
2 两个O的情况
在一个全是O序列中，两个O的情况有$C^2_n$种
我们设$event(j,i)$为$\prod_i^jp_x$，即$[j,i]$都是O的概率
因为这两个O之间不能有X，所以这两个O之间都必须是O，概率为$event(j,i)$
设$dp(i)=\sum_{j=1}^{i-1}event(j,i)$，每个$i$对答案的贡献为$dp(i) \times 2$
而算$dp(i)​$是平方级算法，并且这个$dp(i)​$没有充分利用前面的状态，我们试着推导：
$\sum_{j=1}^{i-1}event(j,i) = p_1 \times p_2 \times … \times p_i + p_2 \times p_3 \times … \times p_i + … + p_{i-1} \times p_i$
所以$dp(i)=(dp(i-1)+p_{i-1} \times p_i)$，就是把原式结合律
这样完成就完成了两个O的情况的贡献

然后把答案相加就是最后的答案。可以直接DP。然后观察方程，$dp(i)$只和$dp(i-1)$有关，所以数组都可以省了

阅读全文 »

发表于 | 分类于 | | + s

Codeforces 768D
设$dp(i,j)$为前$i$天生产了$j$种不同的水晶的概率，转移方程：
$$dp(i,j)=dp(i-1,j) \times \frac{j}{k} + dp(i-1,j-1) \times \frac{k-j+1}{k}$$
之后判断$dp(i,k)$是否大于给定条件，答案为$i$
然后因为$p<=1000$，所以把所有情况先预处理出来，直接输出即可。
此题可以把第一维压掉，注意$eps=1e-7$不要写作$eps=1e7$

阅读全文 »

发表于 | 分类于 | | + s

设$dp(i,j,k)$为前$i$个挑战赢了$j$场，当前背包容量为$k$的状态存在的概率。
注意，背包容量超过$n$即无意义，所以要一直取$min$
状态转移方程：
$dp(i+1,j,k)=dp(i,j,k) \times (1 - P_{i+1})$
$dp(i+1,j+1,k+a_{i+1})=dp(i,j,k) \times P_{i+1}$
在转移的过程中不要忘了取$min$。
我们在DP前需要把挑战按背包容量排序，这样先打掉背包多的怪物，再打要装碎片的怪物，可以避免本来够但安排不合理，而不够背包装碎片的情况

阅读全文 »