A. TreeScript
题意：给你一棵树，和根节点，让你建出这棵树。每个节点在被创建的时候要知道它的父亲节点的地址和寄存器来存放地址。问最少需要多少个寄存器才能建出这颗树？
思路：以样例为例：
一开始根节点1建立需要一个寄存器，然后我们考虑建立7号点，它也需要一个(因为当且1号点的寄存器还不能被覆盖因为2和5还没建立)，然后考虑建立5，5可以覆盖7的寄存器，然后再去建立2，2可以覆盖5的寄存器。然后1的直接儿子都建立完了，再建立3的时候可以去覆盖1的寄存器，然后4可以覆盖3的，5可以覆盖2的。
最终最少需要2个寄存器。
我们发现：
- 我们从小的子树开始建立更优
- 只有当根的直接儿子建立完之后根的寄存器才能被覆盖
- 以为根，它需要的寄存器数量的建立其次大子树所需要的寄存器+根节点所需要的和最大子树所需要的寄存器数量取个max
以为根的子树建立所需的寄存器数量
初始化
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
42
43
44
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<int>e[N];
int f[N];
void dfs(int u)
{
f[u] = 1;
int fi = 0,se = 0;
for(auto v : e[u])
{
dfs(v);
if(f[v]>fi)fi = f[v];
else if(f[v]<=fi&&f[v]>se)se = f[v];
}
f[u] = max(fi,se+1);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n; cin>>n;
for(int i = 0;i <= n; i++)
f[i] = 0,e[i].clear();
for(int i = 1;i <= n; i++)
{
int p; cin>>p;
if(p == 0) continue;
e[p].push_back(i);
}
dfs(1);
cout<<f[1]<<"\n";
}
return 0;
}
|
H. Another Goose Goose Duck Problem
题意：每秒有一只鸭子要来，杀一只鸭子有秒的冷却时间。问杀掉只鸭子至少要多少时间？
思路：如果，那么答案就是(因为冷却时间比来的时间短，只要来了我就能杀)。
那么对于的情况呢？(看是的几倍),答案就是$btk$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
ll l,r,b,k; cin>>l>>r>>b>>k;
if(l<=b)cout<<b*k<<"\n";
else{
int t = l/b + (l%b!=0);
cout<<t*b*k<<"\n";
}
return 0;
}
|
K. Maximum GCD
题意：给你个数~，你可以选择一个数和另一个数,然后把变成。问你经过若干次操作之后最大的可以是多少？
思路：因为我们知道取模的一个性质，对于一个数它经过取模操作(不能模本身)可以变成。
我们考虑取模之后只能变成它本身的一个数。那么我们考虑变成最小的那个数。什么时候可以变呢？当且仅当这个数除以2之后小于等于最小的数。否则的话答案一定是最小的数除以2了。
形象的来说就是：
假设最小值是,那么如果序列中没有中的数，那么所有数都可以变成。
否则的话，就存在有的数不能变到了，那么最后的答案就是。为什么呢？因为一个数可以变成，那么最小值除以2即一定小于等于，那么肯定符合题意啦。
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>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n; cin>>n;
int mn = 1e9;
for(int i = 1;i <= n; i++)
cin>>a[i],mn = min(mn,a[i]);
bool ok = true;
for(int i = 1;i <= n; i++)
{
if(a[i]==mn)continue;
if(a[i]/2<mn){
ok = false;
break;
}
}
if(ok)cout<<mn<<"\n";
else cout<<mn/2<<"\n";
return 0;
}
|
