「PKUWC2018」题解

发表于 | 分类于 | | 浏览量： 次

PKUWC都是神仙题，蒟蒻我根本做不来。

传送门

Minimax
Slay the Spire
随机算法
随机游走
猎人杀
斗地主

Minimax

题解

答案的表达式看上去极其诡异，但是观察过后，不难发现，只要求出每种权值出现的概率，问题就迎刃而解了（废话）。

首先需要抓住题目中保证的两个性质，一个是权值互不相同，另一个是有儿子的节点最多只有两个儿子。

设第$i$个节点出现权值$j$的概率为$g_{i,j}$，那么由于权值互不相同，左右儿子中最多只有一个节点可能出现权值$j$。

设左儿子的编号为$L$，右儿子为$R$，如果左儿子可能出现权值$j$，那么就有：

右儿子可能出现权值$j$的情况同理。

考虑这个转移的过程，相当于权值$j$出现的概率被乘上了

仔细观察这个式子，里面是一个前缀和和一个后缀和，所以可以通过对支持乘法操作的线段树进行合并操作来实现转移，不断向上合并之后就可以求出根节点每种权值出现的概率了。具体实现参见代码（感觉还是挺妙的）。

时间复杂度和空间复杂度都是$O(n\log n)$。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300005,TT=998244353,inv=796898467;
int n,P[maxn],W[maxn],num[maxn],tot,lnk[maxn],son[maxn],nxt[maxn],ans;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
struct SegmentTree
{
	int tot,R[maxn];
	inline int New(){tot++;Tree[tot].Tag=1;return tot;}
	struct Node{int Sum,Tag,L,R;}Tree[maxn*40];
	inline void PushUp(int rt){Tree[rt].Sum=(Tree[Tree[rt].L].Sum+Tree[Tree[rt].R].Sum)%TT;}
	inline void PushDown(int rt)
	{
		Tree[Tree[rt].L].Sum=(LL)Tree[Tree[rt].L].Sum*Tree[rt].Tag%TT;Tree[Tree[rt].L].Tag=(LL)Tree[Tree[rt].L].Tag*Tree[rt].Tag%TT;
		Tree[Tree[rt].R].Sum=(LL)Tree[Tree[rt].R].Sum*Tree[rt].Tag%TT;Tree[Tree[rt].R].Tag=(LL)Tree[Tree[rt].R].Tag*Tree[rt].Tag%TT;
		Tree[rt].Tag=1;
	}
	inline int Merge(int rt1,int rt2,int P,int Pre1=0,int Suf1=0,int Pre2=0,int Suf2=0)
	{
		if(!rt1&&!rt2) return 0;
		PushDown(rt1);PushDown(rt2);
		int rt=New();
		if(!rt1)
		{
			int mul=((LL)P*Pre1+(LL)(1-P+TT)*Suf1)%TT;
			Tree[rt]=Tree[rt2];
			Tree[rt].Sum=(LL)Tree[rt2].Sum*mul%TT;
			Tree[rt].Tag=(LL)Tree[rt2].Tag*mul%TT;
		}
		else if(!rt2)
		{
			int mul=((LL)P*Pre2+(LL)(1-P+TT)*Suf2)%TT;
			Tree[rt]=Tree[rt1];
			Tree[rt].Sum=(LL)Tree[rt1].Sum*mul%TT;
			Tree[rt].Tag=(LL)Tree[rt1].Tag*mul%TT;
		}
		else
		{
			Tree[rt].L=Merge(Tree[rt1].L,Tree[rt2].L,P,Pre1,(Suf1+Tree[Tree[rt1].R].Sum)%TT,Pre2,(Suf2+Tree[Tree[rt2].R].Sum)%TT);
			Tree[rt].R=Merge(Tree[rt1].R,Tree[rt2].R,P,(Pre1+Tree[Tree[rt1].L].Sum)%TT,Suf1,(Pre2+Tree[Tree[rt2].L].Sum)%TT,Suf2);
			PushUp(rt);
		}
		return rt;
	}
	inline int NewTree(int P,int L=1,int R=num[0])
	{
		int rt=New();
		if(L==R){Tree[rt].Sum=1;return rt;}
		int M=(L+R)>>1;
		if(P<=M) Tree[rt].L=NewTree(P,L,M);
		else Tree[rt].R=NewTree(P,M+1,R);
		PushUp(rt);
		return rt;
	}
}ST;
void DFS(int now)
{
	if(!lnk[now]){ST.R[now]=ST.NewTree(W[now]);return;}
	for(int i=lnk[now];i;i=nxt[i])
	{
		DFS(son[i]);
		if(!ST.R[now]) ST.R[now]=ST.R[son[i]];
		else ST.R[now]=ST.Merge(ST.R[now],ST.R[son[i]],P[now]);
	}
}
void Solve(int L=1,int R=num[0],int rt=ST.R[1])
{
	if(L==R){ans=(ans+(LL)L*num[L]%TT*ST.Tree[rt].Sum%TT*ST.Tree[rt].Sum%TT)%TT;return;}
	int M=(L+R)>>1;
	ST.PushDown(rt);
	Solve(L,M,ST.Tree[rt].L);
	Solve(M+1,R,ST.Tree[rt].R);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int fi=read();
		if(fi) add_e(fi,i);
	}
	for(int i=1;i<=n;i++)
	{
		if(lnk[i]) P[i]=(LL)read()*inv%TT;
		else W[i]=num[++num[0]]=read();
	}
	sort(num+1,num+1+num[0]);
	for(int i=1;i<=n;i++)
		if(!lnk[i])
			W[i]=lower_bound(num+1,num+1+num[0],W[i])-num;
	DFS(1);Solve();
	printf("%d\n",ans);
	return 0;
}

Slay the Spire

题解

首先考虑一下，在抽到了$m$张牌之后，怎样打才比较优。

不难发现，肯定挑权值大的牌打，所有要打的攻击牌肯定都是在要打的强化牌打完之后才打的。

并且，由于强化牌上的数字最少为$2$，所以如果抽到的强化牌数量够多的话，一定会打出权值前$k-1$大的强化牌，然后再打出一张权值最大的攻击牌；如果抽到的强化牌数量比较少，那肯定会全部打出。

首先对两种牌的权值从大到小排序。

设权值第$i$大强化牌的权值为$p_i$，权值第$i$大的攻击牌的权值为$w_i$。

考虑两个DP：

  • $F[i][j][0/1]$：表示考虑了前$i$张强化牌，打出了$j$张，第$i$张强化牌没打/打了时所有方案强化牌的乘积的和。
  • $G[i][j][0/1]$：表示考虑了前$i$张攻击牌，打出了$j$张，第$i$张攻击牌没打/打了时所有方案攻击牌的加和的和。

不难推出转移方程：

上述两个数组处理好之后，可以开始考虑计算答案了。

首先可以枚举一下抽中的牌中强化牌的数量，设共$i$张，分两种情况考虑：

  1. $i<k$，那么这种情况对答案的贡献为:

  2. $i\geq k$，此时的贡献为：

累加起来即可得到答案。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3005,TT=998244353;
int T,n,m,k,C[maxn][maxn],w[maxn],p[maxn],F[maxn][maxn][2],G[maxn][maxn][2],ans;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main()
{
	for(int i=0;i<=3000;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(j==0) C[i][j]=1;
			else C[i][j]=(C[i-1][j-1]+C[i-1][j])%TT;
		}
	}
	T=read();
	while(T--)
	{
		n=read();m=read();k=read();ans=0;
		for(int i=0;i<=n;i++) F[i][0][0]=1;
		for(int i=1;i<=n;i++) p[i]=read();
		for(int i=1;i<=n;i++) w[i]=read();
		sort(w+1,w+1+n);reverse(w+1,w+1+n);
		sort(p+1,p+1+n);reverse(p+1,p+1+n);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				F[i][j][0]=F[i-1][j][0]+F[i-1][j][1];
				if(F[i][j][0]>=TT) F[i][j][0]-=TT;
				F[i][j][1]=((LL)F[i-1][j-1][0]+F[i-1][j-1][1])*p[i]%TT;
				G[i][j][0]=G[i-1][j][0]+G[i-1][j][1];
				if(G[i][j][0]>=TT) G[i][j][0]-=TT;
				G[i][j][1]=((LL)G[i-1][j-1][0]+G[i-1][j-1][1]+(LL)C[i-1][j-1]*w[i])%TT;
			}
		}
		for(int i=0;i<=m&&i<=n;i++)
		{
			int sum1=0,sum2=0;
			if(i<k)
			{
				for(int j=1;j<=n;j++)
				{
					sum1+=F[j][i][1];if(sum1>=TT) sum1-=TT;
					sum2=(sum2+(LL)G[j][k-i][1]*C[n-j][m-k])%TT;
				}
			}
			else
			{
				for(int j=1;j<=n;j++)
				{
					sum1=(sum1+(LL)F[j][k-1][1]*C[n-j][i-k+1])%TT;
					sum2=(sum2+(LL)G[j][1][1]*C[n-j][m-i-1])%TT;
				}
			}
			if(k==1||i==0) sum1=C[n][i];
			ans=(ans+(LL)sum1*sum2)%TT;
		}
		printf("%d\n",ans);
	}
	return 0;
}

随机算法

题解

排列的总数很好求，考虑有多少种排列能求出正确的答案。

数据范围很小，考虑一个状压DP：

$F[S][i]$表示当前的排列中已经包含了集合$S$中的所有元素，且最大独立的大小为$i$的方案数。

枚举下一个不在$S$中的节点$j$，使节点$j$加入到最大独立集中来。设$j$以及与$j$距离为$1$的点构成的集合为$T$，那么节点$j$需要放在排列中最靠前的一个空位，剩下的节点可以随意放排列中剩余的空位上。所以就有转移：

初始有$F[0][0]=1$，最后的答案为$\frac{F[U][mx]}{n!}$，其中$U$为全集，$mx$为最大独立集的大小。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=25,TT=998244353;
int n,m,lnk[maxn],A[maxn][maxn],cnt[(1<<20)+5],F[(1<<20)+5][21],mx,ifn,ans;bool vis[(1<<20)+5][21];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
inline void Inc(int& x,int y){x=(x+y>=TT?x+y-TT:x+y);}
int main()
{
	n=read();m=read();ifn=1;
	for(int i=1;i<=n;i++) ifn=(LL)ifn*i%TT;
	ifn=QP(ifn,TT-2);
	for(int i=1;i<=n;i++) lnk[i]|=1<<(i-1);
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read();
		lnk[a]|=(1<<(b-1));
		lnk[b]|=(1<<(a-1));
	}
	for(int i=0;i<=20;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(j==0) A[i][j]=1;
			else A[i][j]=(A[i-1][j]+(LL)A[i-1][j-1]*j)%TT;
		}
	}
	for(int i=1;i<(1<<n);i++) cnt[i]=cnt[i>>1]+(i&1);
	F[0][0]=vis[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int S=0;S<(1<<n);S++)
		{
			for(int j=1;j<=n;j++)
			{
				if(vis[S][i]&&!(S&(1<<(j-1))))
				{
					Inc(F[S|lnk[j]][i+1],(LL)F[S][i]*A[n-cnt[S]-1][cnt[lnk[j]-(lnk[j]&S)]-1]%TT);
					vis[S|lnk[j]][i+1]=true;
					if(i+1>mx) mx=i+1;
				}
			}
		}
	}
	ans=(LL)F[(1<<n)-1][mx]*ifn%TT;
	printf("%d\n",ans);
	return 0;
}

随机游走

题解

题目中要求经过$S$中所有点的期望步数，即$E(max(S))$，并不好搞，考虑到数据范围非常小，可以使用MinMax容斥，即$E(\max(S))=\sum_{T\subseteq S{}}(-1)^{|T|+1}E(\min(T))$，所以问题就转化为了求从起点出发，经过$T$中任意一个节点的期望步数。

首先可以暴力枚举集合$T$，然后考虑一个树形DP：

$F_i$表示从节点$i$出发，经过集合$T$中任意一个节点的期望步数，比较显然的转移是：

  1. 若$i\notin T$:
  1. $i\in T$

考虑第一种情况，这个式子不是很好看，考虑分离儿子与父亲的情况分别考虑。

设$F[i]=K[i]\cdot F[fa[i]]+B[i]$，那么就有：

其中$SumK[i]$表示$\sum_{j\in son[i]}{K[j]}$，$SumB[i]$同理。

所以就有：

这两个数的取值与$i$的父节点无关，只与子节点有关。

对于第二中情况，显然有$K[i]=B[i]=F[i]=0$。

所以就可以通过一趟$DFS$来求出每个节点的$K[i]$与$B[i]$。

对根节点$x$，因为没有父亲，所以就有$F[x]=B[x]$。

所以我们就可以求出所有集合$T$的期望，以及他们对答案的贡献。

但是由于询问数量很多，不能每次都暴力枚举子集。

不难发现，对于一个集合$T$，他是否会对$S$产生贡献以及贡献的大小只取决$T$是不是$S$的子集以及$T$本身。

所以我们可以先预处理出所有$2^n$个子集的贡献，然后就可以通过高维前缀和来快速统计每一个询问的答案了。

时间复杂度$O(n\cdot 2^n)$。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=20,TT=998244353;
int n,Q,x,tot,lnk[maxn],son[maxn*2],nxt[maxn*2],deg[maxn],K[maxn],B[maxn],SK[maxn],SB[maxn],G[(1<<18)+5],cnt[(1<<18)+5];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
inline void add_e(int x,int y){tot++;deg[y]++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
void DFS(int now,int fa,int S)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]!=fa)
		{
			DFS(son[i],now,S);
			SK[now]=(SK[now]+K[son[i]])%TT;
			SB[now]=(SB[now]+B[son[i]])%TT;
		}
	}
	if((1<<(now-1))&S) K[now]=B[now]=0;
	else
	{
		K[now]=QP((deg[now]-SK[now]+TT)%TT,TT-2);
		B[now]=((LL)SB[now]+deg[now])*K[now]%TT;
	}
}
int main()
{
	n=read();Q=read();x=read();
	for(int i=1;i<n;i++)
	{
		int a=read(),b=read();
		add_e(a,b);add_e(b,a);
	}
	for(int i=0;i<(1<<n);i++)
	{
		memset(K,0,sizeof(K));memset(SK,0,sizeof(SK));
		memset(B,0,sizeof(B));memset(SB,0,sizeof(SB));
		DFS(x,0,i);cnt[i]=cnt[i>>1]+(i&1);
		G[i]=(((cnt[i]&1)?1:-1)*B[x]+TT)%TT;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)
			if(j&(1<<i))
				G[j]=(G[j]+G[j-(1<<i)])%TT;
	while(Q--)
	{
		int k=read(),S=0;
		while(k--) S+=1<<(read()-1);
		printf("%d\n",G[S]);
	}
	return 0;
}

猎人杀

题解

对于这一道题，一个比较麻烦的问题就是当死了猎人之后，每个猎人的中枪概率会发生改变。

不妨对问题进行这样的转化：

当猎人中枪之后，他的尸体还在，并且在下一次开枪的时候，他的尸体仍然有机会被打中，打中的概率不变。如果一次开枪打中了一具尸体，那么就继续开枪，直到打到活人为止。

不难发现，这样转化问题之后，问题的答案并没有改变，而且此时每次猎人中枪的概率没变。

并且直接计算$1$号猎人最后死亡的概率并不容易，考虑容斥：

考虑如何计算一个集合内的所有猎人都在$1$号猎人之后死的概率。

令$S=\sum{i=1}^{n}w_i$，$W_T=\sum{i\in T}W_i$，那么就有：

所以，集合$T$对答案的贡献只与$W_T$和$|T|$有关。

但是数据范围非常大，直接背包肯定是不行的，考虑生成函数：

那么就有

那个生成函数直接用NTT或者FFT然后分治计算一下就好了，时间复杂度$O(n\log^2n)$。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005,TT=998244353;
int n,w[maxn],r[262160],ans,S;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
struct Polynomial
{
	int n;int* A;
	Polynomial(const Polynomial& b){n=b.n;A=new int[n+5];memcpy(A,b.A,4*(n+5));}
	Polynomial(int l=262160){n=l;A=new int[l+5];memset(A,0,(l+5)*sizeof(int));}
	~Polynomial(){delete A;}
}TA,TB;
inline void NTT(Polynomial& F,int limit,int typ)
{
	for(int i=0;i<limit;i++)
		if(i<r[i])
			swap(F.A[i],F.A[r[i]]);
	for(int mid=1;mid<limit;mid<<=1)
	{
		int gn=QP(3,(TT-1)/(mid<<1));
		if(typ<0) gn=QP(gn,TT-2);
		for(int j=0;j<limit;j+=(mid<<1))
		{
			int g=1;
			for(int k=0;k<mid;k++,g=(LL)g*gn%TT)
			{
				int x=F.A[j+k],y=(LL)g*F.A[j+k+mid]%TT;
				F.A[j+k]=(x+y)%TT;
				F.A[j+k+mid]=(x-y+TT)%TT;
			}
		}
	}
	if(typ<0)
	{
		int inv=QP(limit,TT-2);
		for(int i=0;i<limit;i++) F.A[i]=(LL)F.A[i]*inv%TT;
	}
}
inline Polynomial Calc(int L,int R)
{
	if(L==R)
	{
		Polynomial C(w[L]);
		C.A[0]=1;C.A[w[L]]=TT-1;
		return C;
	}
	int M=(L+R)>>1;
	Polynomial A=Calc(L,M),B=Calc(M+1,R);
	int limit=1,l=0;
	while(limit<=A.n+B.n){limit<<=1;l++;}
	for(int i=0;i<limit;i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	TA.n=A.n;TB.n=B.n;Polynomial C(limit);
	for(int i=0;i<limit;i++) TA.A[i]=TB.A[i]=0;
	for(int i=0;i<=A.n;i++) TA.A[i]=A.A[i];
	for(int i=0;i<=B.n;i++) TB.A[i]=B.A[i];
	NTT(TA,limit,1);NTT(TB,limit,1);
	for(int i=0;i<limit;i++) C.A[i]=(LL)TA.A[i]*TB.A[i]%TT;
	NTT(C,limit,-1);
	C.n=A.n+B.n;
	return C;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++){w[i]=read();if(i>1) S+=w[i];}
	Polynomial res=Calc(2,n);ans=1;
	for(int i=1;i<=S;i++)
		ans=(ans+TT+(LL)res.A[i]*w[1]%TT*QP(i+w[1],TT-2)%TT)%TT;
	printf("%d\n",ans);
	return 0;
}

斗地主

神仙题，蒟蒻我太菜了，做不来。