A. Tricky Template

我们对每个位置 $i$ 来看,只要 $a_i == c_i \ or \ b_i == c_i$​ ,那么就会使其不成立, 如果是整个字符串呢，那么就是，那么就需要每个位置都成立才能使其不成立，于是遍历判断一下即可

$code:$

void solve() {
	int n;
	std::cin >> n;
	std::string a, b, c;
	std::cin >> a >> b >> c;
 
	int ok = 0;
	for(int i = 0; i < n; i ++ ) {
		if(a[i] != c[i] && b[i] != c[i]) {
			ok = 1;
		}
	}
	std::cout << (ok ? "YES" : "NO") << '\n';
}

B. Forming Triangles

首先题目给的 长度是 $2^{a_i}$ ,我们观察一下，发现能构成三角形的边长只有这种情况 $(2^n, 2^n, 2^k) (其中 k \le n)$ ，那么我们就直接计数即可，特判一下 $k == n$ 的情况，我们计算贡献，记录 $2^n$ 的个数为x, 小于 $2^n$ 的个数为 $s$，对于 $k == n: \tbinom{x}{3}$ , 对于 $k < n:\tbinom{x}{2} * s$，求个前缀和统计贡献即可

$code:$

void solve() {
	int n;
	std::cin >> n;
 
	std::map<int, int> mp;
	for(int i = 0; i < n; i ++ ) {
		int x;
		std::cin >> x;
		mp[x] ++;
	}
 	o
	i64 ans = 0, s = 0;
	for(auto [x, y] : mp) {
		if(y >= 3) {
			ans += 1LL * y * (y - 1) * (y - 2) / 3 / 2;
		}
		if(y >= 2) {
			 ans += 1LL * y * (y - 1) / 2 * s;
		}
		s += y;
	}
 
	std::cout << ans << '\n';
 
}

C. Closest Cities

我们分别记录从 $1$ 走到 $i$ 的代，以及从 $n$ 走到 $i$ 的代价，就是一个前缀和后缀，然后判断一下每个路径的取值，最后查询就减去即可

$code:$

void solve() {
	int n;
	std::cin >> n;
 
	std::vector<int> a(n);
	for(int i = 0; i < n; i ++ ) {
		std::cin >> a[i];
	}
 
	std::vector<i64> pre(n), suf(n);
	pre[1] = 1;
	for(int i = 1; i < n - 1; i ++ ) {
		pre[i + 1] = pre[i] + (a[i + 1] - a[i] < a[i] - a[i - 1] ? 1 : a[i + 1] - a[i]);
	}
	suf[n - 2] = 1;
	for(int i = n - 2; i >= 1; i -- ) {
		suf[i - 1] = suf[i] + (a[i] - a[i - 1] < a[i + 1] - a[i] ? 1 : a[i] - a[i - 1]);
	}
	
	int q;
	std::cin >> q;
	while(q -- ) {
		int x, y;
		std::cin >> x >> y;
		x --, y --;
		if(x < y) {
			std::cout << pre[y] - pre[x] << '\n';
		} else {
			std::cout << suf[y] - suf[x] << '\n';
		}
	}
 
}

D. Berserk Monsters

观察到如果一个怪兽被消灭，那么受影响的只有与之相邻的俩个怪兽，其余的都不会改变，链表模拟这个过程即可，设每次删除的怪兽为$x_i$ 那么 复杂度大致为 $2(x_1 + x_2+…+x_n) = 2n$ ，然后可以用 $set$ 去维护，多一个 $log(n)$ 的复杂度，总复杂度为 $O(nlogn)$

$code:$

void solve() {
	int n;
	std::cin >> n;
 
	std::vector<int> a(n + 2), d(n + 2), l(n + 2), r(n + 2), del(n + 2);
	for(int i = 1; i <= n; i ++ ) {
		std::cin >> a[i];
	}
	for(int i = 1; i <= n; i ++ ) {
		std::cin >> d[i];
	}
 
	std::queue<int> q, _q;
	for(int i = 1; i <= n; i ++ ) {
		r[i] = i + 1;
		l[i] = i - 1;
		q.push(i);
	}
	l[n + 1] = n;
	r[0] = 1;
	std::vector<int> ans;
	for(int i = 0; i < n; i ++ ) {
		std::queue<int> _q;
		
		while(!q.empty()) {
			int pos = q.front(); q.pop();
			int v = a[l[pos]] + a[r[pos]];
			if(v > d[pos]) {
				_q.push(pos);
			}
		}
		
		std::set<int> S;
		ans.push_back(_q.size());
		
		while(!_q.empty()) {
			auto u = _q.front(); _q.pop();
			del[u] = true;
			if(l[u] >= 1 && l[u] <= n) S.insert(l[u]);
			if(r[u] >= 1 && r[u] <= n) S.insert(r[u]);
			r[l[u]] = r[u];
			l[r[u]] = l[u];
		}
		for(auto x : S) {
			if(!del[x]) {
				q.push(x);
			}
		}
		
	}
 
	for(auto x : ans) {
		std::cout << x << ' ';
	}
	std::cout << '\n';
}