PKUWC&SC 2018 刷题记录
minimax
线段树合并的题，似乎并不依赖于二叉树。
之前写的草率的题解在这里：PKUWC2018 minimax
Slay the Spire
注意到强化牌的强化倍数都是大于\(1\)的正整数，所以可以发现能强化就尽量强化。
用\(F(x,y)\)表示强化牌抽\(x\)张打出\(y\)张的倍率之和
用\(G(x,y)\)表示攻击牌抽\(x\)张打出\(y\)张的攻击之和
那么我们枚举抽了多少张攻击牌，在利用以上两个函数就可以算出答案了。
至于怎么计算那两个函数就看代码把。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int sz=3e3+7;
const int mod=998244353;
int T;
int ans;
int n,m,k;
int a[sz],b[sz];
int inv[sz],fac[sz],ifac[sz];
int sum[sz],f[sz][sz],g[sz][sz];
void init(){
fac[0]=ifac[0]=1;
fac[1]=ifac[1]=inv[1]=1;
for(int i=2;i<sz;i++){
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
fac[i]=1ll*i*fac[i-1]%mod;
ifac[i]=1ll*inv[i]*ifac[i-1]%mod;
}
}
int C(int n,int m){
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int F(int x,int y){
//抽出x张强化牌,y张打出去的效用和
if(x<y) return 0;
if(y==0) return C(n,x);
int ret=0;
rep(i,x-y+1,n-y+1)
ret=(ret+1ll*f[y][i]*C(i-1,x-y)%mod)%mod;
return ret;
}
int G(int x,int y){
//抽出x张攻击牌,y张打出去的效用和
if(x<y) return 0;
if(y==0) return 0;
int ret=0;
rep(i,x-y+1,n-y+1)
ret=(ret+1ll*g[y][i]*C(i-1,x-y)%mod)%mod;
return ret;
}
int main(){
init();
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
rep(i,1,n) rep(j,1,n) f[i][j]=g[i][j]=0;
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n) scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
rep(i,1,n){
f[1][i]=a[i];
sum[i]=(sum[i-1]+f[1][i])%mod;
}
rep(i,2,n){
rep(j,1,n-i+1)
f[i][j]=1ll*a[j]*((sum[n]-sum[j]+mod)%mod)%mod;
rep(j,1,n)
sum[j]=(sum[j-1]+f[i][j])%mod;
}
rep(i,1,n){
g[1][i]=b[i];
sum[i]=(sum[i-1]+g[1][i])%mod;
}
rep(i,2,n){
rep(j,1,n-i+1)
g[i][j]=(1ll*b[j]*C(n-j,i-1)%mod+(sum[n]-sum[j]+mod)%mod)%mod;
rep(j,1,n)
sum[j]=(sum[j-1]+g[i][j])%mod;
}
ans=0;
rep(i,max(m-n,0),min(n,m)){
int j=m-i;
ans=(ans+1ll*F(i,min(i,k-1))*G(j,max(k-i,1))%mod)%mod;
}
printf("%d\n",ans);
}
}
斗地主
不可能写的，这辈子都不可能写的。
随机算法
枚举不可选择的集合\(S\)(不可选择的集合为现在已经有的独立集以及和这些独立集相连的点)
每次，选择一个新的点放入独立集，那么它会新增一些点不可选。
这些点只要放在放入独立集的新点的后面就可以了，它的贡献就是一个组合数。
然后就没了。
#include<bits/stdc++.h>
using namespace std;
const int sz=24;
const int mod=998244353;
int n,m;
int u,v,t;
int link[sz];
int bit[1<<20];
int fac[sz],ifac[sz],inv[sz];
int dp[1<<20],g[1<<20];
void init(){
fac[0]=ifac[0]=1;
fac[1]=ifac[1]=inv[1]=1;
for(int i=2;i<sz;i++){
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
fac[i]=1ll*i*fac[i-1]%mod;
ifac[i]=1ll*inv[i]*ifac[i-1]%mod;
}
}
int C(int n,int m){
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
init();
scanf("%d%d",&n,&m);
t=1<<n;
for(int i=1;i<=n;i++) link[i]|=1<<(i-1);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
link[u]|=1<<(v-1);
link[v]|=1<<(u-1);
}
for(int i=1;i<t-1;i++) bit[i]=bit[i>>1]+(i&1);
dp[0]=1,g[0]=0;
for(int i=0;i<t;i++){
for(int j=1;j<=n;j++)
if(((i>>(j-1))&1)==0){
int s=i|link[j],p=s^i;
if(g[i]+1<g[s]) continue;
else if(g[i]+1==g[s])
dp[s]=(dp[s]+1ll*dp[i]*C(n-bit[i]-1,bit[p]-1)%mod*fac[bit[p]-1]%mod)%mod;
else{
g[s]=g[i]+1;
dp[s]=1ll*dp[i]*C(n-bit[i]-1,bit[p]-1)%mod*fac[bit[p]-1]%mod;
}
}
}
int ans=1ll*dp[t-1]*ifac[n]%mod;
printf("%d\n",ans);
}
猎人杀
你以为我会吗？
不，我不会。
随机游走
\(min-max\)容斥好题
之后再\(FMT\)一下就可以了。
#include<bits/stdc++.h>
#define go(x) for(int i=head[x];i;i=edge[i].nxt)
#define now edge[i].v
using namespace std;
const int sz=20;
const int mod=998244353;
int S;
int t;
int k,x;
int n,q,rt;
int u,v,cnt;
int head[sz];
int a[sz],b[sz],d[sz];
int s[1<<20],bit[1<<20];
struct Edge{
int v,nxt;
}edge[sz<<1];
int qpow(int x,int y){
int ret=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*x*ret%mod;
return ret;
}
void add(int u,int v){
edge[++cnt]=(Edge){v,head[u]};head[u]=cnt;
edge[++cnt]=(Edge){u,head[v]};head[v]=cnt;
}
void dfs(int x,int fa){
int asum=0,bsum=0;
go(x) if(now!=fa){
dfs(now,x);
asum=(asum+a[now])%mod;
bsum=(bsum+b[now])%mod;
}
if(S>>(x-1)&1) a[x]=b[x]=0;
else{
int inv=qpow((d[x]-asum+mod)%mod,mod-2);
a[x]=inv,b[x]=1ll*inv*(d[x]+bsum)%mod;
}
}
int main(){
scanf("%d%d%d",&n,&q,&rt);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
d[u]++;
d[v]++;
add(u,v);
}
t=1<<n;
for(S=1;S<t;S++){
dfs(rt,0);
bit[S]=bit[S>>1]^(S&1);
s[S]=bit[S]?b[rt]:(mod-b[rt])%mod;
}
for(int i=1;i<t;i<<=1)
for(int j=0;j<t;j+=2*i)
for(int k=0;k<i;k++)
s[i+j+k]=(s[i+j+k]+s[j+k])%mod;
while(q--){
S=0;
scanf("%d",&k);
while(k--){
scanf("%d",&x);
S|=1<<(x-1);
}
printf("%d\n",s[S]);
}
}
真实排名
简单题，拿\(two-point\)随便搞搞就可以了。
之前写的草率的题解在这里：PKUSC2018 真实排名
最大前缀和
似乎又是一个状态压缩的\(DP\)?
好像是我很久以前写的（可能还是我给别人胡完让他帮我写的），已经不记得了。
先咕着。
主斗地
不好意思，我是不会写的。
星际穿越
不会，咕着。
神仙的游戏
把\(border\)变成循环节就可以了,再\(FFT\)一下就可以了。
之前写的草率的题解在这里：PKUSC2018 神仙的游戏
PKUSC
似乎并不难想。
只需要将每个点在多边形内的概率算出来再相加就可以得到期望了。
每个点的贡献大概就是以它到原点的距离作圆，看圆弧有多少在多边形内。
但是看到隔壁的ATS 大佬肝了快一天还没肝出来，我实在是缺乏勇气。