概述
又名：暑假集训6
得分：\(40+20+20+10=90\)
rk 11
赛时
打得比较懵，很多部分分想了很久才打出来。
题解
T1 接力游戏
题意
给序列 \(a,b\)，每个序列包含两个属性 \(w,v\)，从序列中任意选择元素，求在保证两序列各自选择元素中 \(w\) 之和相等的情况下，最大的 \(v\) 和。
思路
背包问题，想了个优化，发现会增加一个 \(\log\)，正解的玄学优化是排序用前缀和卡一下上下界。
代码
点击查看代码
int n,m;
struct node{
int w,v;
bool operator<(const node&rhs)const{
return w<rhs.w;
}
}a[1005],b[1005];
int suma[1005],sumb[1005];
ll f[maxn],g[maxn];
ll ans;
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i){
a[i].w=read(),a[i].v=read();
}
for(int i=1;i<=m;++i){
b[i].w=read(),b[i].v=read();
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
for(int i=1;i<=n;++i) suma[i]=suma[i-1]+a[i].w;
for(int i=1;i<=m;++i) sumb[i]=sumb[i-1]+b[i].w;
memset(f,-0x3f,sizeof(f));
memset(g,-0x3f,sizeof(g));
f[0]=g[0]=0;
for(int i=1;i<=n;++i){
for(int j=suma[i];j>=a[i].w;--j){
if(f[j-a[i].w]==-0x3f3f3f3f3f3f3f3f) continue;
f[j]=max(f[j],f[j-a[i].w]+a[i].v);
}
}
for(int i=1;i<=m;++i){
for(int j=sumb[i];j>=b[i].w;--j){
if(g[j-b[i].w]==-0x3f3f3f3f3f3f3f3f) continue;
g[j]=max(g[j],g[j-b[i].w]+b[i].v);
}
}
for(int i=1;i<=min(suma[n],sumb[m]);++i){
ans=max(ans,f[i]+g[i]);
}
printf("%lld\n",ans);
return 0;
}
T2 树上竞技
题意
给定一棵 \(n\) 个节点的树，从中随机选择 \(m\) 个，找到一个节点使的这个节点到所选择的节点的最短路径之和最小，求所有选择方案对应的最小值之和。
思路
赛时推出来这样的节点只有一个，没有突破计算答案来源的瓶颈。
考虑一条边 \(e\)，其两端点 \(u,v\) 两侧选择的节点个数 \(i\) 与 \(m-i\)，两侧可选择的节点个数 \(siz\) 与 \(n-siz\)，那么有：
大致意思是在保证这条边会被经过的前提下，其贡献就是选取方案以及较小一侧的选取点个数（最优的点一定在较大一侧）。
考虑到这个 \(\min\) 不好处理，设 $k=\left\lfloor\dfrac{m-1}{2}\right\rfloor$，于是换成：
特别对于 \(2\mid m\) 的情况，还有：
\[\dbinom{siz}{\tfrac{m}{2}}\dbinom{n-siz}{\tfrac{m}{2}}\times \dfrac{m}{2} \]考虑上面式子怎么优化（先不管系数），可以把 \(i\) 去掉，得到：
\[\sum_{i=1}^{k}\dbinom{siz-1}{i-1}\dbinom{n-siz}{m-i}\times siz \]设其为 \(siz\times g(siz)\)，考虑如何转移。
然后是神秘的组合意义，将其理解成在 \(n-1\) 个元素中，总共选取 \(m-1\) 个，限制在前 \(siz-1\) 位置中至多选取 \(k-1\) 个，那么当且仅当目前依然在前 \(siz-1\) 位置中选取 \(k-1\) 个，又在 \(siz\) 位置选取了 \(1\) 个，\(g(siz)\) 对于 \(g(siz+1)\) 是不合法的，这个不合法的方案数就是：
于是就可以递推了。
代码
点击查看代码
int n,m;
vector<int> E[maxn];
inline int q_pow(int x,int p){
int res=1;
while(p){
if(p&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
p>>=1;
}
return res;
}
int fac[maxn],inv[maxn];
inline int C(int N,int M){
return 1ll*fac[N]*inv[M]%mod*inv[N-M]%mod;
}
int g[maxn];
int siz[maxn];
ll ans;
void dfs(int u,int f){
siz[u]=1;
for(int v:E[u]){
if(v==f) continue;
dfs(v,u);
siz[u]+=siz[v];
}
ans=(ans+g[siz[u]]+g[n-siz[u]])%mod;
if(m%2==0) ans=(ans+1ll*C(siz[u],m/2)*C(n-siz[u],m/2)%mod*m/2%mod)%mod;
}
int main(){
freopen("meeting.in","r",stdin);
freopen("meeting.out","w",stdout);
n=read(),m=read();
for(int v=2;v<=n;++v){
int u=read();
E[u].push_back(v);
E[v].push_back(u);
}
fac[0]=inv[0]=1;
for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=q_pow(fac[n],mod-2);
for(int i=n-1;i>=1;--i) inv[i]=1ll*inv[i+1]*(i+1)%mod;
int k=(m-1)/2;
if(k>=1) g[1]=C(n-1,m-1);
for(int i=1;i<n;++i) g[i+1]=(g[i]-1ll*C(i-1,k-1)*C(n-1-i,m-1-(k-1)-1)%mod+mod)%mod;
for(int i=1;i<=n;++i) g[i]=1ll*g[i]*i%mod;
dfs(1,0);
printf("%lld\n",ans);
return 0;
}
T3 虚构推理
题意
给定 \(n\) 个表盘，求出一个表盘使得其与这些表盘的时针夹角或分针夹角的最大值最小，求出这个最小值。
思路
可以暴力。
先求出每个表盘的分针与时针度数，排序后枚举表盘（这里秒要枚举到小数，不然精度不够，考场上一直卡在这里），二分可以找到与当前表盘时针/分针夹角最大的两个表盘，其夹角的最大值就是当前表盘的答案。
代码
点击查看代码
int n;
char ch[10];
db degh[maxn],degm[maxn];
inline db get_deg(db d1,db d2){
return min(fabs(d1-d2),360.0-fabs(d1-d2));
}
inline db chk_h(db dh){
int lpos,rpos;
if(dh<=180.0) rpos=lower_bound(degh+1,degh+n+1,dh+180.0)-degh,lpos=rpos-1;
else rpos=lower_bound(degh+1,degh+n+1,dh-180.0)-degh,lpos=rpos-1;
if(rpos>n) rpos=1;
if(lpos<1) lpos=n;
return max(get_deg(dh,degh[lpos]),get_deg(dh,degh[rpos]));
}
inline db chk_m(db dm){
int lpos,rpos;
if(dm<=180.0) rpos=lower_bound(degm+1,degm+n+1,dm+180.0)-degm,lpos=rpos-1;
else rpos=lower_bound(degm+1,degm+n+1,dm-180.0)-degm,lpos=rpos-1;
if(rpos>n) rpos=1;
if(lpos<1) lpos=n;
return max(get_deg(dm,degm[lpos]),get_deg(dm,degm[rpos]));
}
db ans=1000.0;
int main(){
freopen("unreal.in","r",stdin);
freopen("unreal.out","w",stdout);
n=read();
for(int i=1;i<=n;++i){
scanf("%s",ch+1);
int h=(ch[1]-'0')*10+(ch[2]-'0'),m=(ch[4]-'0')*10+(ch[5]-'0'),s=(ch[7]-'0')*10+(ch[8]-'0');
//printf("%d %d %d\n",h,m,s);
degh[i]=1.0*((h%12)*3600+m*60+s)/43200*360,degm[i]=1.0*(m*60+s)/3600*360;
}
sort(degh+1,degh+n+1);
sort(degm+1,degm+n+1);
degh[0]=degh[n+1]=-1.0,degm[0]=degm[n+1]=-1.0;
for(int h=0;h<12;++h){
for(int m=0;m<60;++m){
for(db s=0;s<60;s+=0.1){
db dh=1.0*(h*3600+m*60+s)/43200*360,dm=1.0*(m*60+s)/3600*360;
ans=min(ans,max(chk_h(dh),chk_m(dm)));
}
}
}
printf("%.5lf\n",ans);
return 0;
}
T4 记忆碎片
题意
给一个 \(n\) 个点的完全图以及最小生成树的边权，求出满足这样的完全图个数。
思路
好厉害的题。
首先对 \(n\) 做整数拆分，拆成若干个联通块，两两合并。
枚举每一条边，若是树边则合并两个联通块，反之则在其中随意连边，这个过程可以用 \(\text{dp}\) 实现，具体是 设 \(dp(i,j)\) 表示前 \(i\) 条边在第 \(j\) 个拆分方案中的方案数。
一些优化（可以但没有也行）：
- 非树边可以用下降幂优化去掉一个 \(n\)。
- 使用 \(\text{bfs}\) 预处理拆分可以连边，然后在图上转移
- 使用
bitset
代码
点击查看代码
int n;
int tot;
vector<int> S[40005],tmp;
map<vector<int>,int> mp;
int cnt_edge[40005];
bool mark[1605];
void dfs(int l,int r){
if(!r){
S[++tot]=tmp;
mp[S[tot]]=tot;
for(int i:S[tot]){
cnt_edge[tot]+=i*(i-1)/2;
}
return;
}
if(l>r) return;
for(int i=l;i<=r;++i){
tmp.push_back(i);
dfs(i,r-i);
tmp.pop_back();
}
}
ll dp[1605][40005];
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
for(int i=1;i<n;++i) mark[read()]=1;
dfs(1,n);
dp[0][1]=1;
for(int i=1;i<=n*(n-1)/2;++i){
for(int j=1;j<=tot;++j){
if(!dp[i-1][j]) continue;
if(mark[i]){
//树边合并
for(int x=0;x<S[j].size();++x){
for(int y=x+1;y<S[j].size();++y){
tmp.clear();
tmp.push_back(S[j][x]+S[j][y]);
for(int z=0;z<S[j].size();++z){
if(z!=x&&z!=y) tmp.push_back(S[j][z]);
}
sort(tmp.begin(),tmp.end());
int nxt=mp[tmp];
dp[i][nxt]=(dp[i][nxt]+dp[i-1][j]*S[j][x]%mod*S[j][y]%mod)%mod;
}
}
}
else{
//非树边随便连一条
dp[i][j]=(dp[i][j]+dp[i-1][j]*(cnt_edge[j]-(i-1))%mod)%mod;
}
}
}
printf("%lld\n",dp[n*(n-1)/2][tot]);
return 0;
}