悲剧的一天


这次考试很可恶,题目很可恶,但是最可恶的是偏偏再我感冒的时候考这种恶心的题,结果做地一塌糊涂。

T1 pf

题目来源:未知

题意:用n个不同的数组成一个长p的序列,要求任意两个相同的数之间至少要有m个数。求排列方案数。

考场思路:(我揉了揉卫生纸,屏幕默默地滚动了几下)

思路1:可以考虑把所有可能的方案数减去与两种要求矛盾的方案数,即“容斥原理”。

思路2:可以考虑使用动态规划,若f[i][j]表示序列中前i个数用前j种给定数字有几种方案,那么

\begin{equation}
f[i][j]+=f[i-1][j-1];
\end{equation}
\begin{equation}
f[i][j]+=f[i-1][j]*(j-m);
\end{equation}

(1)式为用新的数字,(2)式为用原有的数字,不与中间m个重复。f[i][j]的递推有一定范围限制,详见代码。

最后,f[p][n]表示长度为p的序列用排列好的n种数字的方案数,所以我们需要将f[p][n]乘上n!。


T2 guard

题目来源:CodeVS1997

题意:(请过目)

打开了黑魔法师calashock的大门,队员们在迷宫般的路上漫无目的地搜寻着关押demo的监狱的所在地。突然,眼前一道亮光闪过。“我,nandemo,是黑魔法圣殿的守卫者。如果你能通过我的挑战,那么你可以带走黑魔法圣殿的地图……”瞬间,队员们被传送到了一个擂台上,最初身边有一个容量为k的包包。
擂台赛一共有m项挑战,各项挑战依次进行。第i项挑战有一个属性ai,如果,表示这次挑战成功后可以再获得一个容量为ai的包包;如果ai=-1,则表示这次挑战成功后可以得到一个大小为1 的地图残片。地图残片必须装在包包里才能带出擂台,包包没有必要全部装满,但是队员们必须把获得的所有的地图残片都带走(没有得到的不用考虑,只需要完成所有n项挑战后背包容量足够容纳地图残片即可),才能拼出完整的地图。并且他们至少要挑战成功次l才能离开擂台。
队员们一筹莫展之时,善良的守卫者nandemo帮忙预估出了每项挑战成功的概率,其中第项挑战成功的概率为pi/100。现在,请你帮忙预测一下,队员们能够带上他们获得的地图残片离开擂台的概率。

考场思路:简单的概率Dp,用f[i][j][k]表示前i场赢j场背包容量为k时的获胜概率,由于背包容量大于200是没有意义的,所以逆推时赢了也不给他200以上背包,输了再扣,但是上个厕所估计是忘了这回事,于是k开到100000,用滚动数组加上一堆很邪门的判断和优化水过了(数据太水了,没有容量很大的情况)

思路:就是考场思路的前半部分。

给出考场代码吧,懒得改了。


T3 hamilton

来源:CodeForces11D

题意:哈密顿回路计数

考场思路:暴力50分($O(n!)$)

思路:状压DP,($O(n^2*2^n)$),若f[k][i]表示从点集k中编号最小的点出发经过所有k中的点到达i点的简单路径条数,那么枚举:任意的i,j满足:i∈k,(i,j)∈E,j>=min{x,x∈k},那么如果j为k中编号最小的点,那么对ans+=f[k][i],如果j∉k,那么 f[k∪{j}][j]+=f[k][i],只需要按照k中点的数量的递增顺序枚举k的所有情况即可。最后由于每个环正着反着都计数了一遍,且二元环也计数了一遍,所以减去二元环数除以二。

↓超级不压行大发


T4 cg

来源:CodeVS4654

题意:给定非负序列,选取一些元素使没有任意k个元素相连,使元素和最大

考场思路:Dp骗几分吧,好歹是$O(nk)$的。虽然发现用线段树维护区间最大值可以做,但是懒得打了。

思路:问题转化成:每隔k个至少选1个元素,选的和最小

所以可以用单调队列优化。队列左边的比右边的先进来,值更小,每次维护队列单调性,队列最左端的就是可以选的最小值。