ABC这样的基础题就没有写的必要了罢……
D - Minimum Steiner Tree
根据树的性质，树上两节点之间有且只有一条通路，因而，从某个“重要点”到所有其他重要点的路径和途径的点，便是不能删去的部分
我们可以选择任意一个重要点进行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
29
30
31
32
33
34
35
36
37
38
39
40
41
vector<ll> v[200010];
ll vk[200010],N[200010];
int dfs(ll now){
N[now]=1;
int imp=0;
if(vk[now])imp=1;
for(int i=0;i<v[now].size();i++){
if(N[v[now][i]]==0){
imp=max(dfs(v[now][i]),imp);
}
}
if(imp) vk[now]=1;
//cout<<now<<endl;
return imp;
}
void solve() {
ll k,n;
cin>>n>>k;
for(int i=1;i<n;i++){
ll a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
ll st=0;
for(int i=0;i<k;i++){
cin>>st;
vk[st]=1;
}
dfs(st);
ll ans=0;
for(int i=1;i<=n;i++){
ans+=vk[i];
}
cout<<ans;
}
F - Dividing Game
纯纯的Nim板子，唯一需要点脑子的地方就是思考每一个数最多能取多少次。
能取多少次实际上就是这个数非本身的质因数的数量，仅此
以及这题每个样例只有一个输出就离谱，决定了即使你随机输出也有一定过题的可能性……更难绷的是他让我一堆假做法都只错一两个测试点，给我一种思路没错改改bug就能过的错觉……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
ll n,nim=0;
cin>>n;
for(int i=0;i<n;i++){
ll a;
cin>>a;
ll opr=0;
for(int j=2;j*j<=a;j++){
while(a%j==0){
opr++;
a/=j;
}
}
if(a!=1)opr++;
nim^=opr;
}
if(nim)cout<<"Anna";
else cout<<"Bruno";
}
