Codeforces Round #787 (Div. 3)部分题解

题意：
给定一个字符串 s s s 和一个操作次数 k k k，在 k k k 次操作内将字符串转换为字典序最小的字符串，每次操作可以将字符串中所有相同的字符 c c c 减 1 1 1，如 ′ b ′ 'b' ′b′ 变成 ′ a ′ 'a' ′a′.
题解：
对于字符串 s s s，先判断是否可以在 k k k 次操作内将 s s s 变为全为 ′ a ′ 'a' ′a′ 的字符串，如果能则输出全 ′ a ′ 'a' ′a′。否则，从前到后找到能在 k k k 次操作内变为全 ′ a ′ 'a' ′a′ 的字符，将所有小于等于该字符的字符变为 ′ a ′ 'a' ′a′，然后将剩下的操作数全用在当前指针指向的字符 y y y，使之变为 x x x，再将所有在 [ x , y ] [x,y] [x,y] 的字符变为 x x x，输出字符串。
代码：

void solve()
{
	int n,m;
	cin >> n >> m;
	string str;
	cin >> str;
	char ch = 'a';
	for(int i = 0;i < n;i ++) ch = max(ch,str[i]);
	if(ch-'a' <= m)
	{
		for(int i = 0;i < n;i ++) cout << 'a';
	}
	else
	{
		char maxx = 'a';
		int idx = 0;
		for(int i = 0;i < n;i ++)
		{
			if(str[i]-'a' > m)
			{
				break;
			}
			else
			{
				maxx = max(maxx,str[i]);
				idx = i;
			}
		}
		m -= maxx-'a';
		for(int i = 0;i < idx;i ++) cout << 'a';
		char maxp = 'a',ch = 'a';
		int flag = 0;
		for(int i = idx;i < n;i ++)
		{
			if(str[i] <= maxx) cout << 'a';
			else
			{
				if(flag)
				{
					if(str[i] <= maxp && str[i] >= ch) cout << ch;
					else cout << str[i];
					continue;
				}
				maxp = str[i];
				ch = max('a',(char)(str[i]-m));
				cout << ch;
				flag = 1;
			}
		}
	}
	cout << endl;
}

题意：
计算条件节点到根的距离和。
题解：
将题意理解清楚，将题干要求转换为把 x x x 到 y y y 路径上的点当成根，然后计算每一个条件节点到根的距离和，利用 s o n son son 数组统计子树是否含有条件顶点，用 p a t h path path 数组统计 x x x 到 y y y 路径上的顶点。
代码：

void dfs1(int u,int fa)
{
	for(int t : v[u])
	{
		if(t == fa) continue;
		dfs1(t,u);
		son[u] += son[t];
		path[u] |= path[t];
	}
}
 
int dfs2(int u,int fa)
{
	int res = 0;
	for(int t : v[u])
	{
		if(t == fa) continue;
		if(!path[t] && son[t]) res += 1+dfs2(t,u)+1;
	}
	return res;
}
 
void solve()
{
	int n,k,x,y;
	cin >> n >> k >> x >> y;
	// init
	for(int i = 1;i <= n;i ++) path[i] = 0,son[i] = 0,v[i].clear();
	for(int i = 1;i <= k;i ++)
	{
		int x;cin >> x;
		son[x] = 1;
	}
	for(int i = 1;i <= n-1;i ++)
	{
		int a,b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	path[y] = 1;
	dfs1(x,0);
	int ans = 0;
	for(int i = 1;i <= n;i ++)
	{
		if(path[i]) ans += dfs2(i,i);
	}
	cout << ans+count(path+1,path+n+1,1)-1 << endl;
}

2022/5/10