12/17
11:25
OI

PKUWC/SC 乱做

Minimax

之前写过题解,在这里

很好想,不过代码有点难写…

Slay the Spire

看错输入啦OAO。以为强化牌可以有小数w。

强化牌> 1,并且都是整数的情况下,出强化一定比出攻击优秀。

分类讨论,有两种情况:

选的强化牌\geq k – 1,那么出k-1次,然后攻击一次。这种情况下剩下的牌两种都可以选。

选的强化牌< k - 1,全出然后攻击。这种情况下多出来的牌只能选攻击牌。

那么定义f_{i,j},g_{i,j}分别表示前i张牌,选了j张强化,各方案价值积的和,与前i张选了j张攻击价值和的和。然后分类随便统计即可。

斗地主

大模拟,咕咕咕

随机算法

考虑一个O(3^nn)的大暴力。令f_{s1,s2}表示s1集合,构成的独立集是s2的方案。枚举加点转移。

发现最优答案一定是由一个子最优状态扩展来的。那么可以压掉具体独立集的状态。

具体来说我们令f_s,g_s表示s集合构成最大独立集方案,最大独立集大小。

考虑加入一个点x,令w_x表示x与所有和x相连点的集合。

首先更新g,如果变大把f清零。

f_{s \cup w_x} \leftarrow f_s P_{n – |s| – 1}^{|w_x – (w_x \cap s) | – 1}

猎人杀

首先做一个非常脑洞的转化:一个猎人死了,不把它删掉,留在集合中。更改打枪方案为:如果打到的是死人,就继续再打一枪。

记录人数和为A,挂掉的人数为K。令打中某个人,原来的概率,新的概率为P_1,P_2

P_1 = \frac{ w_i }{A – K }

P_2 = \frac{K}{ A } P_2 + \frac{w_i}{A}

可以发现P_1 = P_2

那么一个容斥,枚举在1之后被打死的集合s。记sw和为S

ans = \sum_{s} (-1)^{| s |} \sum_{i=0}^{\infty} (1- \frac{S + w_1}{A}) \frac{w_i}{A}

拿出后面的部分,发现是收敛的,直接提出来:

\sum_{i=0}^{\infty} (1- \frac{S + w_1}{A}) \frac{w_i}{A} = \frac{w_1}{S + w_1}

ans = \sum_{s} (-1)^{| s |}\frac{w_1}{S + w_1} = w_1 \sum_{s} \frac{ (-1)^{| s |} }{S + w_1}

考虑记录对于S\sum (-1)^{|s|}是多少。

构造生成函数F(x)

F(x) = \prod_{i=2}^{A – w_1} (1 – x^{w_i})

那么[x^i]F(x)就是要的东西。

这个式子可以用分治FFT求出来。

随机游走

考虑\rm{min-max}容斥,求出到每个集合的\min即可。枚举集合s,定义f_xx点走进s的期望步数。

如果x \in sf_x = 0

否则有:

f_x = \frac{1}{deg_x} (f_{fa} + \sum_{y \in son} f_y) + 1

有一个树上高斯消元的套路:每个f都可以被表示为f_x = A_x f_{fa} + B_x

推一下式子:

deg_x f_x = f_{fa} + \sum_{y} A_y f_x + B_y

f_x = \frac{1}{deg_x – \sum_y a_y} f_{fa} + \frac{\sum_y b_y + deg_x}{deg_x – \sum_y a_y}

那么可以快速求出f_{root}


真实排名

签到题,考虑哪些选手翻倍不会影响自己。

如果自己不翻倍,翻倍后还是比自己小的,和本来就大于等于自己的可以动。

如果自己翻倍,那么翻倍前到翻倍后的一段都要翻。

组合数算一算就好了。

最大前缀和

观察数据范围发现显然是O(2^nn)的算法。考虑状压DP,钦定一些点是本次答案点。

f_s,g_s分别表示s集合排列,使得最后一个位置前缀和最大的方案数,与s集合排列,任意时刻前缀和\leq 0的方案数。

f_s = \sum_{s – i} f_{s – i} (sum_{s – i} > 0)

g_s = \sum_{s – i} g_{s – i} (sum_s \leq 0)

第二个意义很明确。第一个转移的意思是,把i元素插到s-i排列的最前面。

注意到本题中最小前缀和必须选择至少一个数字,所以这样转移合法。

最后用两个数组计算答案即可。

主斗地

并没有什么思维难度的恶心搜索题。。。还没写。。。

星际穿越

观察可以发现,最优秀的方案要么是直接向左跳,要么是向右跳一次再一直向左。钦定一个起点,向左走的距离一定是一段一段的。

于是利用性质可以考虑一个O(n^2)的简单暴力,计算出任意点对的距离就行了。

优化这个暴力,把记录两点间距离,改成记录一个点跳i次最左可以跳到哪里。倍增优化。

具体来说,定义数组f_{x,i}表示从\forall x \in [x, n]点开始跳2^i次可以跳到哪里。

求出f后,记录g_{x,i}表示跳整个[f_{x,i},x-1]的点一共需要多少次。

最后统计答案。首先向左跳一次,然后用f数组计算答案。容易发现这样是没有问题的。

神仙的游戏

考虑一个做法。问号是匹配符,无视之。我们定义A(x),B(x),使得A(x)=\sum [S_i == 0] x^i,B(x) = \sum [S_i == 1] x^i,然后做一个减法卷积。

然而这样是有问题的。对于长度大于一半的border,会有重复部分,然而这样匹配出的方案可能一个问号分别充当了0,1各一次。

考虑borderperiod的关系。如果存在一个border长度为x,那么剩下的部分在\mod | S | – x意义下相等。这个显然是不相交的。

NTT求一下减法卷积,然后枚举每一段检查。复杂度是一个调和级数。

PKUSC

把每个点的概率加起来就行了。考虑把一个点放在一个圆上,它与多边形交的弧长就是答案。

那么直接解方程解出所有的交点,极角排序,判断每一段弧在多边形内还是外。

判断一个点在多边形内外,可以考虑向任意方向作射线,如果没有和点相交,可根据与边交点数量奇偶性判断内外。

本题中坐标都是整数,所以选要判断的弧上一个非整数点作射线即可避免交到点上的事情。


下面的题并没有地方交OAO

题面

T1

f_s表示集合s的方案数,枚举拓扑序最后的点再枚举出边转移。

T2

钦定一个点或边做代表元素,考虑过这个元素的方案。把点和边分开计算,减一下,发现每种方案只被算了一次。

f_i为有i种颜色经过的点的数量,则有

ans_x = \sum_{i=x}^n f_i \binom{i}{k}

然后卷卷就行了。

T3

不会斗地主。

T4

网上找到的题和题解貌似不符,233,咕了

T5

如果两个环有公共边,它们在一个强联通内。先求强联通,考虑每个分量,把有向边变无向,可以感性理解到,如果有公共边一定在一个点双内。

T6

咕。


题在这里

T1

猜结论可以猜到就是逆序对数量

T2

大概就是做一个DP,记录f_{i,j,s}s表示其他桌子的状态。s记录大小关系。然后不会了233

T3

可以交换Trie的左右儿子,于是做一个小DP,bitset优化。

T4

做一个暴力大DP:f_{i,j}表示i点颜色j,转移显然。发现很多j的答案都是一样的,记录被钦定ban掉的颜色集合即可。然后做一个线段树合并。

T5

咕咕

T6

咕咕