Codeforces Round #625 (Div. 2, based on Technocup 2020 Final Round)

比赛链接：

https://codeforces.com/contest/1321

C. Remove Adjacent

题目大意：

给定一个字符串，当相邻的两个字符之间差值小于 1 的时候，可以删除他们中的任何一个，问最多能删除多少个字符。

思路：

最优的策略肯定是删除最大的先，所以从大到小枚举每一个字符，判断每一个字符能不能删除，能删除就删掉，然后从头开始重新判断。

代码：

#include 
using namespace std;
int n;
string s;
int main(){
	cin >> n >> s;
	for (char ch = 'z'; ch >= 'a'; ch -- ){
		for (int i = 0; i < s.size(); i ++ ){
			if (ch == s[i]){
				if (i > 0 && abs(s[i] - s[i - 1]) == 1){
					s.erase(s.begin() + i);
					i = -1;
				}
				else if (i < n - 1 && abs(s[i] - s[i + 1]) == 1){
					s.erase(s.begin() + i);
					i = -1;
				}
			}
		}
	}
	cout << n - s.size() << "\n";
	return 0;
}

D. Navigation System

题目大意：

给定一张有向图，图上任意两点之间保证可以到达，现在从 \(s\) 到 \(t\)，导航系统会给定一条最短路径，如果不按这个最短路径走，那么导航系统会重新规划最优的路径。现在已知从 \(s\) 到 \(t\) 的一个路径，问导航系统最少和最多重新规划几次路线。

思路：

首先通过 \(bfs\) 求出每个点到终点的最短路径，将边的方向反一下去 \(bfs\) 就行。
当到的下一个点的距离大于当前点 - 1 时，说明不是最短路径，那么一定要重新规划路线。
当到的下一个点的距离等于当前点 - 1 时，如果有好几条最短路径，可以重新规划路径。

代码：

#include 
using namespace std;
const int N = 2e5 + 10;
int n, m, k;
vector  g[N], G[N], p(N), d(N);
void bfs (){
	queue  q;
	q.push(p[k]);
	while (q.size()){
		int u = q.front();
		q.pop();
		for (auto v : g[u]){
			if (v == p[k]) continue;
			if (d[v]) continue;
			d[v] = d[u] + 1;
			q.push(v);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i ++ ){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		g[v].push_back(u);
	}
	cin >> k;
	for (int i = 1; i <= k; i ++ ){
		cin >> p[i];
	}
	bfs();
	int mn = 0, mx = 0;
	for (int i = 1; i < k; i ++ ){
		if (d[p[i + 1]] > d[p[i]] - 1){
			mn ++ ;
			mx ++ ;
		}
		else {
			int ok = 0;
			for (auto j : G[p[i]]){
				if (d[j] == d[p[i]] - 1 && j != p[i + 1]){
					ok = 1;
					break;
				}
			}
			mx += ok;
		}
	}
	cout << mn << " " << mx << "\n";
	return 0;
}