2020 Multi-University Training Contest 9
2020 Multi-University Training Contest 9
wenzhuan
发布于 2022-08-15 12:46:09
发布于 2022-08-15 12:46:09
8.18 自闭但是成绩还可以的杭电9
1001-Tree
题意
给定一棵根节点为 1 、顶点数为 n 的树，在树上只能从父节点到达子节点。问加上一条边后最大可达的点对数。
思路
很气，为啥不是贪心啊（因为小转菜啊）
最优解一定是某个叶节点连回根。在叶节点到根的这条链上每个点都有 n-sz 的贡献，其中 sz 指的是这个节点的子树大小。
直接暴力 dfs 回去找最大值。
代码
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
ll ans,qaq,sz[maxn];
vector<int>vv[maxn];
void dfs(int x){
for(int y:vv[x]) dfs(y),sz[x]+=sz[y];
ans+=sz[x];
}
void dfss(int n,int x,ll t){
t+=n-sz[x]; qaq=max(qaq,t);
for(int y:vv[x]) dfss(n,y,t);
}
int solve(){
ans=0; qaq=0; vv[1].clear(); sz[1]=1;
int n,x; sc(n); rep(i,2,n+1){
vv[i].clear(); sz[i]=1; sc(x);
vv[x].push_back(i);
} dfs(1); dfss(n,1,0); ans+=qaq;
return pf("%lld\n",ans);
}
int main(){
int _; sc(_); while(_--) solve();
}1003-Slime and Stones
题意
两堆物品 a 、b 两人轮流取物，一次只能在一堆取任意数量物品（大于 0 ）或是两堆取相差不超过 k 的物品。问先手胜负情况。
思路
对着威佐夫博弈嗯猜（猜着猜着样例过了这你不冲？）
代码
#include<bits/stdc++.h>
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long ll;
int solve(){
ll a,b,k; scl(a); scl(b); scl(k);
if(a>b) swap(a,b);
ll r=(b-a)%(k+1); if(r) return puts("1");
long double t=(1.0-k+sqrt(1ll*(k+1)*(k+1)+4.0))/2.0;
ll q=(b-a)/(k+1); q=(ll)q*t;
return puts(q==a?"0":"1");
}
int main(){
ll _; scl(_); while(_--) solve();
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录