The 2022 ICPC Asia Regionals Online Contest (I)

C Delete the Tree

题意：想要删掉一棵树，你可以做以下两种操作：

删除：删除一个点以及和它连的边
收缩：选择一个点\(x\)它直接连有\(2\)个点\(u,v\)，我们可以把\(x\)删了，在把\(u,v\)连起来

问你：最少执行删除操作多少次？

思路：要删除次数最少，那我们先尽可能的去收缩。思考一下，一棵树最终会收缩成什么样子？

我们可以把叶子节点的链一直往上收缩，直到收缩不了为止。

反过来考虑，哪些是一定需要删除操作的？只有当是一条链的情况可以收缩，那么，对于一个点，它的度数最多是\(2\)，大于\(2\)的部分要删去(只保留它自己往父亲和往儿子连的两条边)。这样的话，树就可以开始收缩了，最终收缩完以后最后一定还要删\(2\)个点(不能再收缩了)。

当然不要忘记特判\(n=1\)的情况，这种情况直接输出\(1\)就ok了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int d[N];
ll ans = 0;

/*
1
6
1 2
1 3
1 4
1 5
1 6
*/
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 = 1;i<=n;i++)
		// 	cout<<d[i]<<" ";
		// cout<<endl;
		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

题意：一个数\(x\)被认为是好的，当且仅当其二进制末尾\(0\)的个数对于\(1\)的个数。

给你\(l,r\)，让你在\([l,r]\)区间内找出好数，没有就输出\(-1\)。

思路：我们分类讨论：

当\(1\)的个数大于\(0\)的个数，那么我们想要\(0\)的个数变多。如何变多？让它进位。所以我们对当前数加上一个它的\(lowbit\)
当\(1\)的个数小于\(0\)的个数，那么我们要要\(1\)的个数变多。对当前数\(+1\)。
如果一样，那就输出

注意以上操作还要保证数在\([l,r]\)之间。

#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

题意：告诉你几个\(C--\)语法，问你调用了库函数多少次。

思路：

法一：栈模拟。

我们对字符串做以下转化：

\(repeat->(\)
\(librart->1+\)
\(arithemtic->0+\)
数字\(->*\)数字
\(for->)\)

转化完以后，我们删去没有用的\(+\)号，之后开始做栈模拟计算结果即可。

#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();
				//cout<<"x = "<<x<<endl;
				if(isdigit(x[0]))
				{
					
					res += stoi(x);
				}
				tmp.pop();
			}
			if(tmp.top()=="(")
			tmp.pop();
			//cout<<"res = "<<res<<endl;
			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;
}

法二：\(dfs\)

#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;
}