清华大学学生程序设计竞赛暨高校邀请赛（THUPC）2023 - 初赛（待补题）

心得

看题跟榜比较无力，最终5h4题罚坐

M. 世界杯

输出China即可

K. 众数（前缀和）

最优策略是先取最大的数x，设其出现次数为cnt[x]，

然后把小于x的数y每个取min(cnt[y],cnt[x])，

下一轮再取剩下的最大的数x，重复这个过程，直至所有数都取完

由于前缀是一定要取的，后缀一定会取完，

所以，维护前缀和、前缀已经取了多少个数即可，统计每个数的贡献

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,a[N],b[N],pos[N];
ll ans,now,sum[N],del;
ll cal(int x,int v){return 1ll*(n-x)*v+sum[x];
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+n+1);for(int i=1;i<=n;++i){sum[i]=sum[i-1]+b[i];}for(int i=1;i<=n;++i){pos[i]=upper_bound(b+1,b+n+1,a[i])-b;pos[i]--;//printf("i:%d pos:%d cal:%lld\n",i,pos[i],cal(pos[i],a[i]));}for(int i=n;i>=1;--i){if(a[i]<=now)continue;now=a[i];ans+=1ll*i*(cal(pos[i],a[i])-del);//printf("now:%lld cal:%lld del:%lld add:%lld\n",now,cal(pos[i],a[i]),del,1ll*now*(cal(pos[i],a[i])-del)*a[i]);del=cal(pos[i],a[i]);//printf("i:%d now:%lld pos:%d sum:%lld add:%lld\n",i,now,pos[i],sum[pos[i]],1ll*now*pos[i]*a[i]);}printf("%lld\n",ans);return 0;
}

A.大富翁（树上博弈）

 注意到，若a是b的祖先，则a支配b，

a和b被不同的人选时，选a的人+1，选b的人-1，

而若被相同的人选时，选a的人+1，选b的人-1，也恰能抵消为0

所以，每个点贡献独立，

点u赚的游戏币=子树点的个数sz[u]-它的深度d[u]（即祖先点的个数）-支付游戏币的个数w[u]

而双方都是为了花的少赚得多的最优策略，

所以奇偶选取，统计先手赚取的金额即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<int>e[N];
int n,fa,w[N],a[N],sz[N],my,you;
ll ans;
void dfs(int u,int d){a[u]=-w[u]-d;sz[u]=1;for(auto &v:e[u]){dfs(v,d+1);sz[u]+=sz[v];}a[u]+=sz[u]-1;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&w[i]);}for(int i=2;i<=n;++i){scanf("%d",&fa);e[fa].push_back(i);}dfs(1,0);sort(a+1,a+n+1,greater<int>());for(int i=1;i<=n;++i){if(i&1)ans+=a[i];}printf("%lld\n",ans);return 0;
}

I. 欺诈游戏（博弈&概率/纳什均衡）

 事实上，如果画一张表格，

以不同角色的视角，合并同类项，

把一方看做是变量时，其余所有看作是常量

对于走私者来说，收益形如，

此时，对于检察官来说，令n个系数都相同，

即走私者不管怎么选择，走私者都只能获得固定收益，

检察官达到了使对方利益最小化的目的（不存在比这大的可能性）

对于检察官来说，收益形如

此时，对于走私者来说，令n个系数都相同， 

即检察官不管怎么选择，走私者都只能获得固定收益，

走私者达到了自己利益最大化的目的（不存在比这小的可能性）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=998244353;
int n,p[N],w[N],sump,sumw,is,ip,inv[N];
int modpow(int x,int n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
void init(){inv[1]=1;for(int i=2;i<N;i++){inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;}
}
int main(){scanf("%d",&n);//assert(1<=n && n<=400000);init();w[0]=1;for(int i=0;i<=n;++i){w[i+1]=(sumw+1ll*(i+1)*w[i]%mod)%mod;w[i+1]=2ll*w[i+1]%mod;w[i+1]=1ll*w[i+1]*inv[i+1]%mod;sumw=(sumw+w[i])%mod;}/*p[0]=1;p[1]=modpow(2,mod-2,mod);sump=p[0];for(int i=1;i<=n;++i){p[i+1]=1ll*inv[2]*sump%mod;p[i+1]=(p[i+1]+1ll*(i+1)*inv[2]%mod*p[i]%mod)%mod;p[i+1]=1ll*inv[i]*p[i+1]%mod;sump=(sump+p[i])%mod;}*///ip=modpow(sump,mod-2,mod);is=modpow(sumw,mod-2,mod);//printf("1/8:%d 2/8:%d\n",modpow(8,mod-2,mod),modpow(4,mod-2,mod));//assert(sum!=0);//printf("sum:%d is:%d\n",sum,is);ip=inv[n+2];for(int i=0;i<=n;++i){if(i==0)p[i]=2ll*ip%mod;else p[i]=ip;printf("%d%c",p[i]," \n"[i==n]);}for(int i=0;i<=n;++i){w[i]=1ll*w[i]*is%mod;printf("%d%c",w[i]," \n"[i==n]);}return 0;
}