PKUWC2018题解

当时太菜了没有去,(除斗地主外)题解合集
感觉这套题的idea不错

5/5

Minimax

请先思考后再展开

考虑$f[i][j]$表示节点i取值j的概率,注意到最多两个儿子,而且有效取值是做并,考虑线段树合并
$$
P_i+=left_i*(p_x*\sum_{j<i} right_j+(1-p_x)*\sum_{j>i} right_j) \\
P_j+=right_i*(p_x*\sum_{i<j} left_j+(1-p_x)*\sum_{i<j} left_j) \\
$$
当两边都有的时候暴力合并,合并的时候带上参数分别表示left、right的左侧、右侧和

当只有某边有节点的时候,相当于给里面的东西打上一个乘法标记,$O(nlogn)$

code

Slay the Spire

请先思考后再展开

首先,保证了单组数据在3000内,所以是可以n方的
其次,因为翻倍牌都大于1,所以如果可以,出k-1张翻倍牌一定是最优的,否则当然是所有翻倍牌
然后剩下的就非常容易了,应该也是签到题,不过我在一些细节的地方想错、写错了好多次

设fa(n,k)表示翻倍牌,考虑前n个用了k张的 $\sum 积$ ,然后根据美妙的乘法原理直接转移,但当k超过k-1的时候积的长度只能是k-1
设fb(n,k)表示攻击牌,考虑前n个而且用了第n个的 $\sum 和$ ,然后为了转移需要再记录一个tb表示sum的数量
设fr(a,b)表示攻击牌,选a个但求和b个的 $\sum 和$
设fc(n)表示攻击牌,选m个然后 $\sum 第一个$ ,这个很好做
然后我们枚举a和b=m-a表示两边分别选多少牌
$a \leq k-1,ans+=fa(n,a) \times fr(b,k-a)$
$a>k-1,ans+=fa(n,a) \times fc(m-a)$
那么不难注意到,有用的fr状态,a和b的差都是m-k,所以fr也能dp出来

code

随机算法

请先思考后再展开

方法一:
$O(n^2 2^n)$
设f(i,S)表示填了排列的前i个,当前独立集为S的方案数
然后为了避免那些无法被独立集记录但在排列中的点被重复计算,尽管他们的边集情况不同,
但对当前状态的影响都是相同的,那就是不能加入独立集,所以乘以「n-i-能加入S的点」就能不重不漏的计数了
这种做法理论上的分数为50,但在loj上可ac

方法二:
$O(n 2^n)$
这时候我们不能再记录多一维了
尝试直接dp概率而非计数,有的时候这样好做很多
注意到对于一个点集,独立集=去掉独立集中的某个点以及其相邻的点后的独立集+被去掉的独立集中的点
直接dp当排列的集合为S时的概率,枚举最后一个被加入独立集的点,转移就像上面说的那样
然后「你感受一下」,觉得他们到这里的概率应该是相同的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int MAX_N=23;
int bin[MAX_N],inv[MAX_N];
int mp[MAX_N];
int f[1<<MAX_N],mx[1<<MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;
inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;

int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
mp[x-1]|=bin[y-1];mp[y-1]|=bin[x-1];
}
f[0]=1;mx[0]=0;
for(int s=1;s<bin[n];s++)
{
int tot=0;
for(int i=0;i<n;i++) if(s&bin[i])
{
tot++;
int s2=s^(mp[i]&s)^bin[i];
if(mx[s2]+1==mx[s]) add(f[s],f[s2]);
else if(mx[s2]+1>mx[s]) f[s]=f[s2],mx[s]=mx[s2]+1;
}
f[s]=(ll)f[s]*inv[tot]%MOD;
}
printf("%d",f[bin[n]-1]);
}

方法三:
$O(n 2^n)$
这是我目前认为最靠谱的做法了
就是你顺便记录每个集合,最大的独立集大小
然后你只需要转移那些siz=mxsiz[S]的状态,也就是状态就少一维了
然后这个和上面的思想也是吻合的

猎人杀

有n堆石子,第i堆有wi个,每次随机选一颗石子,然后把整堆拿走,问第一堆最后拿走的概率

请先思考后再展开

update:经典面试题,要求将$[1,A]的随机数生成器修改为[1,B]$
这个的做法是如果不在B以内,则重新生成,这个你等比数列求和发现是对的

30分:按题意模拟

题意转化是本题的唯一难点(这东西似乎已经可以叫“猎人杀”转化了)

因为每次概率的分母变来变去很麻烦,考虑等效的转化:如果杀了一个已经死了的人,就重新杀一轮

1号最后被杀有点烦,容斥一下,固定后面还有多少个活着
令A为权值和,S为被固定的和
那么 $P=\sum_{i=0}^{\infty} (1-\frac{S+w_1}{A})^i \frac{w_1}{A}=\frac{w_1}{S+w_1}$
$ans=\sum_{k=0}^{n-1} (-1)^k ( \sum_{S=0}^A times(S) \frac{w1}{S+w_1} )$
$ans=\sum_{S=0}^A ( \sum_{k=0}^{n-1} (-1)^k times(S) ) \frac{w1}{S+w_1}$
显然中间那个,构造一下生成函数即可
$\prod (1-x^{w_i})$
然后显然用分治ntt求
每一层一定比AlogA小,共logn层,故复杂度为 $O(Alog^2A)$

code

随机游走

请先思考后再展开

前置知识(套路):min-max容斥、树上高斯消元、fwt(非必要)
特性:有根树的根是固定的(不然就很麻烦了)
问题转化为,对于每个点集S,求从根x出发的期望步数
$f(x)=\frac{1}{tot-\sum kson} f(fa)+\frac{tot+\sum bson}{tot-\sum kson}$
最后统计答案时最好用fwt,复杂度为 $O(30n 2^n)$

code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/be4c.html
转载请注明出处,谢谢!