PKUWC2018题解

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

Minimax

请先思考后再展开

f[i][j]表示节点i,取值j的概率
每个节点开个动态开点的权值线段树,维护区间概率和
那么我们现在只要能合并两棵线段树即可

对于线段树节点x(权值=l~r)
$$
PX(p[left]down[right][l]+down[left][l]p[right])+\\
(1-PX)
((p[left](1-down[right][l])+(1-down[left][l])p[right]))
$$

$$
p[left]( PXdown[right][l]+(1-PX)(1-down[right][l]) )+\\
p[right]
( PXdown[left][l]+(1-PX)(1-down[left][l]) )
$$
那么两边有某个为空,则打个区间乘法的标记
都有则暴力合并

那么我们计算一下线段树合并的复杂度,主要就是公共区域
考虑每个叶子,只会被合并一次,此后再经过其祖先不算是他的贡献,那么就是深度也就是log
所以说个人认为这个东西并不是由启发式保证的,而是只会被合并一次,严格和不公共的地方无关

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出来

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
104
105
106
107
108
109
110
111
112
113
114
115
116
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
//#define pr pair<double,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=3100;
const int MOD=998244353;
ll qpower(ll x,int e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
int inv(int x) {return qpower(x,MOD-2);}
void add(int &x,int y)
{
x+=y;
if(x>=MOD) x-=MOD;
if(x<=-MOD) x+=MOD;
}
int fac[MAX_N],facinv[MAX_N];
int C(int n,int m)
{
if(n<m) return 0;//debug
return (ll)fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;
}
int A[MAX_N],B[MAX_N];
int fa[MAX_N][MAX_N],fc[MAX_N];
int fb[MAX_N][MAX_N],tb[MAX_N][MAX_N],fr[MAX_N];//fb,tb为i降k不降的前缀和
void main()
{
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=(ll)fac[i-1]*i%MOD;
facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=inv(fac[i]);
int T;scanf("%d",&T);
while(T--)
{
int n,m,k;scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
for(int i=1;i<=n;i++) scanf("%d",&B[i]);
sort(A+1,A+n+1);reverse(A+1,A+n+1);
sort(B+1,B+n+1);reverse(B+1,B+n+1);//debug……
for(int i=0;i<n;i++)
{
fa[i][0]=1;
for(int j=0;j<=i;j++) if(fa[i][j]>0)
{
if(j+1<=k-1) add(fa[i+1][j+1],(ll)fa[i][j]*A[i+1]%MOD);
else add(fa[i+1][j+1],fa[i][j]);
add(fa[i+1][j],fa[i][j]);
fa[i][j]=0;
}
}
for(int ln=1;ln<=n;ln++) for(int i=1;i<=n;i++) add(fc[ln],(ll)B[i]*C(n-i,ln-1)%MOD);
for(int i=0;i<=n;i++) fb[i][0]=0,tb[i][0]=1;
for(int k=1;k<=n;k++)
{
for(int i=k;i<=n;i++)
{
int now1=fb[i-1][k-1]+(ll)tb[i-1][k-1]*B[i]%MOD;now1%=MOD;
fb[i][k]=(fb[i-1][k]+now1)%MOD;tb[i][k]=(tb[i-1][k]+tb[i-1][k-1])%MOD;
}
}
for(int a=m-k;a<=n;a++)
{
int b=a-(m-k);
fr[a]=0;for(int i=b;i<=n;i++) add(fr[a], ll(fb[i][b]-fb[i-1][b])*C(n-i,a-b)%MOD );
}
int ans=0;
for(int a=0;a<=n and a<=m;a++)
{
int b=m-a;if(b>n or b==0) continue;
if(a<=k-1) add(ans,(ll)fa[n][a]*fr[b]%MOD);
else add(ans,(ll)fa[n][a]*fc[b]%MOD);
}
printf("%d\n",(ans+MOD)%MOD);
for(int i=0;i<=n;i++) fa[n][i]=fc[i]=fr[i]=0;
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) fb[i][j]=tb[i][j]=0;
}
}
};
int main()
{
srand(time(0));
mine::main();
}

随机算法

请先思考后再展开

方法一:
$O(n^2 2^n)$
设f(i,S)表示填了排列的前i个,当前独立集为S的方案数
然后为了避免那些无法被独立集记录但在排列中的点被重复计算,尽管他们的边集情况不同,
但对当前状态的影响都是相同的,那就是不能加入独立集,所以乘以【n-i-能加入S的点】就能不重不漏的计数了
这种做法理论上的分数为50,但在oj上可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
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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
//#define pr pair<double,int>
#define FR first
#define SE second
#define MP make_pair
const int MOD=998244353;
void add(int &x,int y)
{
x+=y;
if(x>=MOD) x-=MOD;
}
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]);
}
};
int main()
{
srand(time(0));
mine::main();
}

方法三:
$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)$

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
104
105
106
107
108
109
110
111
112
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
const int MOD=998244353;
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
ll add(ll x,ll y)
{
x+=y;
if(x>=MOD) x-=MOD;
if(x<=-MOD) x+=MOD;
return x;
}
const int MAX_N=4*110000;
struct NTT
{
int R[MAX_N];
void preR(int n)
{
R[0]=0;for(int i=1;i<=n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<((int)log2(n)-1));
}
ll w[2][MAX_N];
void prew(int n)
{
ll now0=qpower(3,(MOD-1)/n),now1=inv(now0);
w[0][0]=w[1][0]=1;for(int i=1;i<=n;i++) w[0][i]=w[0][i-1]*now0%MOD,w[1][i]=w[1][i-1]*now1%MOD;
}
void solve(ll A[],int n,int f)
{
for(int i=0;i<n;i++) if(i<R[i]) swap(A[i],A[R[i]]);
for(int ln=1;ln<=n/2;ln*=2)
for(int st=0;st<n;st+=ln*2)
for(int k=0;k<ln;k++)
{
ll a=A[st+k],b=w[f][(n/ln/2)*k]*A[st+ln+k]%MOD;
A[st+k]=add(a,b);A[st+ln+k]=add(a,-b);
}
}
}ntt;
ll C[MAX_N];
void cheng(ll A[],ll B[],int ln)
{
int n=1;while(n<=ln) n*=2;
for(int i=0;i<n;i++) C[i]=B[i];
ntt.preR(n);ntt.prew(n);
ntt.solve(A,n,0);ntt.solve(C,n,0);
for(int i=0;i<n;i++) A[i]=A[i]*C[i]%MOD;
ntt.solve(A,n,1);
for(int i=0;i<n;i++) A[i]=A[i]*inv(n)%MOD;
}
int w[MAX_N];
ll pp[30][MAX_N];
void solve(int l,int r,int dep)
{
if(l==r)
{
pp[dep][0]=1;pp[dep][w[l]-w[l-1]]=-1;
return;
}
int mid=(l+r)/2;
solve(l,mid,dep+1);int a=w[mid]-w[l-1];
for(int i=0;i<=a;i++) pp[dep][i]=pp[dep+1][i],pp[dep+1][i]=0;
solve(mid+1,r,dep+1);int b=w[r]-w[mid];
cheng(pp[dep],pp[dep+1],a+b+1);
for(int i=0;i<=b;i++) pp[dep+1][i]=0;
}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]),w[i]+=w[i-1];
if(2<=n) solve(2,n,0);
ll ans=0;for(int s=0;s<=w[n]-w[1];s++) ans=add(ans,pp[0][s]*w[1]%MOD*inv(s+w[1])%MOD);
printf("%lld",(ans+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

随机游走

请先思考后再展开

前置知识(套路):min-max容斥、树上高斯消元、fwt(非必要)
特性:有根树的根是固定的(不然就很麻烦了)
问题转化为,对于每个点集S,求从根出发的期望步数
$f(x)=\frac{1}{tot-\sum kson} f(fa)+\frac{tot+\sum bson}{tot-\sum kson}$
最后统计答案时最好用fwt,复杂度为 $O(30n 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
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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
const int MOD=998244353;
void add(int &x,int y)
{
x+=y;
if(x>=MOD) x-=MOD;
if(x<=-MOD) x+=MOD;
}
pr operator + (pr a,pr b) {add(a.FR,b.FR);add(a.SE,b.SE);return a;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
const int MAX_N=20;
int hou[MAX_N],dg[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int bin[MAX_N],nows;
pr dfs(int x,int fa)
{
if(bin[x]&nows) return MP(0,0);
pr tmp=MP(0,0);
for(int k=hou[x];k>0;k=e[k].g) if(e[k].y!=fa) tmp=tmp+dfs(e[k].y,x);
return MP( inv(dg[x]-tmp.FR),ll(dg[x]+tmp.SE)*inv(dg[x]-tmp.FR)%MOD );
}
int a[1<<MAX_N];
void fwt(int n)
{
for(int i=0;i<n;i++)
for(int j=bin[n]-1;j>=0;j--) if(j&bin[i])
add(a[j],a[j^bin[i]]);
}
void main()
{
bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;
int n,q,st;scanf("%d%d%d",&n,&q,&st);st--;
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);x--;y--;
ins(x,y);ins(y,x);dg[x]++;dg[y]++;
}
for(nows=1;nows<bin[n];nows++)
{
pr ans=dfs(st,-1);
for(int i=0;i<n;i++) if(nows&bin[i]) ans.SE*=-1;
a[nows]=-ans.SE;
}
fwt(n);
while(q--)
{
int k;scanf("%d",&k);
int wt=0;
for(int i=1;i<=k;i++)
{
int now;scanf("%d",&now);
wt|=bin[now-1];
}
printf("%d\n",(a[wt]+MOD)%MOD);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

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