The 2022 ICPC Asia Regionals Online Contest (I)
C Delete the Tree
题意：想要删掉一棵树，你可以做以下两种操作：
- 删除：删除一个点以及和它连的边
- 收缩：选择一个点它直接连有个点，我们可以把删了，在把连起来
问你：最少执行删除操作多少次？
思路：要删除次数最少，那我们先尽可能的去收缩。思考一下，一棵树最终会收缩成什么样子？
我们可以把叶子节点的链一直往上收缩，直到收缩不了为止。
反过来考虑，哪些是一定需要删除操作的？只有当是一条链的情况可以收缩，那么，对于一个点，它的度数最多是，大于的部分要删去(只保留它自己往父亲和往儿子连的两条边)。这样的话，树就可以开始收缩了，最终收缩完以后最后一定还要删个点(不能再收缩了)。
当然不要忘记特判的情况，这种情况直接输出就ok了。
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
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int d[N];
ll ans = 0;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n==1)
{
cout<<1<<"\n";
continue;
}
ans = 0;
for(int i = 1;i<=n;i++)
d[i] = 0;
for(int i = 1;i<n;i++)
{
int x,y;
cin>>x>>y;
d[x]++,d[y]++;
}
for(int i = 2;i<=n;i++)
{
ans += max(0,d[i]-2);
}
ans += 2;
ans += max(d[1] - 2, 0);
cout<<ans<<endl;
}
return 0;
}
|
D Find the Number
题意：一个数被认为是好的，当且仅当其二进制末尾的个数对于的个数。
给你，让你在区间内找出好数，没有就输出。
思路：我们分类讨论：
- 当的个数大于的个数，那么我们想要的个数变多。如何变多？让它进位。所以我们对当前数加上一个它的
- 当的个数小于的个数，那么我们要要的个数变多。对当前数。
- 如果一样，那就输出
注意以上操作还要保证数在之间。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int lowbit(int x)
{
return x&(-x);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)
{
int l,r;
cin>>l>>r;
bool ok = false;
while(l<=r)
{
int cnt0 = __builtin_ctz(l);
int cnt1 = __builtin_popcount(l);
if(cnt0==cnt1)
{
ok = true;
break;
}
if(cnt0<cnt1)
l += lowbit(l);
else l += 1;
}
if(ok)cout<<l<<"\n";
else cout<<-1<<"\n";
}
return 0;
}
|
H Step Debugging
题意：告诉你几个语法，问你调用了库函数多少次。
思路：
法一：栈模拟。
我们对字符串做以下转化：
- 数字数字
转化完以后，我们删去没有用的号，之后开始做栈模拟计算结果即可。
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
string s[N],t[N],a[N];
int n,m,len;
const int mod = 20220911;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
while(1)
{
string t;
cin>>t;
if(t=="fin")break;
s[++n] = t;
}
for(int i = 1;i<=n;i++)
{
if(s[i]=="repeat")t[++len]="(";
if(s[i]=="library")t[++len] ="1",t[++len] = "+";
if(s[i]=="arithmetic")t[++len] ="0",t[++len] = "+";
if(isdigit(s[i][0]))t[++len] = "*",t[++len]=s[i],t[++len] = "+";
if(s[i]=="for")t[++len] = ")";
}
for(int i = 1;i<=len;i++)
{
if(t[i]=="+")
{
if(i+1<=len&&t[i+1]!=")")a[++m] = t[i];
else{
continue;
}
}
else if(isdigit(t[i][0])&&t[i-1]==")"){
a[++m] = "+",a[++m] = t[i];
}
else a[++m] = t[i];
};
stack<string>tmp;
stack<int>ans;
int i = 1;
ll ret = 0;
while(i<=m)
{
if(a[i]=="*")
{
ll res = ans.top()%mod;
ans.pop();
res = res*stoi(a[i+1])%mod;
tmp.push(to_string(res));
i++;
}
else if(a[i]!=")")
tmp.push(a[i]);
else
{
int res = 0;
while(tmp.top()!="(")
{
string x = tmp.top();
if(isdigit(x[0]))
{
res += stoi(x);
}
tmp.pop();
}
if(tmp.top()=="(")
tmp.pop();
ans.push(res);
}
i++;
}
while(!tmp.empty())
{
string x = tmp.top();
if(isdigit(x[0]))
ret += stoi(tmp.top()),ret %= mod;
tmp.pop();
}
cout<<ret%mod<<endl;
return 0;
}
|
法二：
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
| #include<bits/stdc++.h>
using namespace std;
const int mod=20220911;
string s;
int res;
int dfs()
{
string s;
int res=0;
while(cin>>s,s!="for")
{
if(s=="library")
{
res++;
}
else if(s=="repeat")
{
res+=dfs();
}
}
int num;
cin>>num;
cin>>s;
return num*res%mod;
}
int main()
{
cin>>s;
while(cin>>s,s!="fin")
{
if(s=="library")
res++;
else if(s=="repeat")
res+=dfs();
}
cout<<res%mod<<"\n";
return 0;
}
|
A 01 Sequence
