2020 Multi-University Training Contest 9

8.18 自闭但是成绩还可以的杭电9

1001-Tree

题意

给定一棵根节点为 $1$ 、顶点数为 $n$ 的树,在树上只能从父节点到达子节点。问加上一条边后最大可达的点对数。

思路

很气,为啥不是贪心啊(因为小转菜啊)

最优解一定是某个叶节点连回根。在叶节点到根的这条链上每个点都有 $n-sz$ 的贡献,其中 $sz$ 指的是这个节点的子树大小。

直接暴力 $dfs$ 回去找最大值。

代码

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
#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$ 的物品。问先手胜负情况。

思路

对着威佐夫博弈嗯猜(猜着猜着样例过了这你不冲?)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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();
}