A 水盐平衡

比较 和 的相对大小，判断输出即可。

时间复杂度：

B 水平考试

等价于两个集合 判断 中是否存在 中所不包含的元素。

• 若存在则输出 0；
• 否则输出 10。

时间复杂度：

C 数组段数

考虑前缀和，设 ，求解出 （其中 是艾弗森括号）。

那么答案就是 。

时间复杂度：

D 剪纸游戏

对于每个连通块，只需要判断其是否为矩形即可。

维护每个连通块的大小和横纵坐标的最大及最小值，那么只需要检查坐标标记的矩形大小是否等于连通块大小即可。

上述信息均可以通过 bfs 或 dfs 维护出来。

时间复杂度：

E 可口蛋糕

首先枚举左端点，然后根据 的限制求解出右端点的最小值（双指针递推），记为 。

那么此时问题转变为：以 为左端点的最大子段和（通过倒序 dp 预处理即可）。

时间复杂度：

F 喜欢序列

首先考虑原数组可以被分成若干段连续的序列，通过基本不等式可以证明为了使价值最大，每一段都不应该再分割。

考虑差分，做完差分后根据差分数组整个序列可以被分成若干段（差分为 1）。

注意到问题本质上成为了动态维护的 C 题。

由于现在维护的是差分数组，所以原区间修改转变成两次单点修改。

一次单点修改的影响本质上是从序列被分割出的段中提取出一个点，修改完这个点后再考虑其是否能连接回原本的段中，这一步可以用 set<pair<int, int> > 这个结构来维护，具体操作分类讨论即可。

时间复杂度：

代码展示

A

#include <bits/stdc++.h>
using namespace std;

void solved() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if(a * d > b * c) cout << "S";
	else cout << "Y";
	cout << endl;
}
signed main() {
	int ttx;  cin >> ttx;  while(ttx --)
	solved();
	return 0;
}

B

#include <bits/stdc++.h>
using namespace std;

void solved() {
	string s, f;  cin >> s >> f;
	bool ans = true;
	for(char x: s) {
		bool ck = false;
		for(char y: f) if(x == y) ck = true;
		if(!ck) ans = false;
	}
	if(ans) cout << 10 << endl;
	else cout << 0 << endl;
}
signed main() {
	int ttx;  cin >> ttx;  while(ttx --)
	solved();
	return 0;
}

C

#include <iostream>
using namespace std;

const int N = 1000001;
int a[N], sum[N];

int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + (a[i] != a[i - 1]);
	}
	int l, r;
	while(m --) {
		cin >> l >> r;
		cout << sum[r] - sum[l - 1] + (a[l] == a[l - 1]) << endl;
	}
	return 0;
}

D

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, I_MAX = b; i <= I_MAX; i ++)
typedef pair<int, int> pii;

const int N = 1009;

char s[N][N];
int n, m;

int xx[] = {0, 1, 0, -1, 0};
bool bfs(int x, int y) {
	queue<pii> qu;
	qu.push({x, y});  s[x][y] = '*';
	int mn[2] = {x, y};
	int mx[2] = {x, y};
	int sum = 0;
	while(!qu.empty()) {
		x = qu.front().first, y = qu.front().second;
		qu.pop();  sum ++;
		mn[0] = min(mn[0], x);
		mn[1] = min(mn[1], y);
		mx[0] = max(mx[0], x);
		mx[1] = max(mx[1], y);
		_for(i, 1, 4) {
			int fx = x + xx[i], fy = y + xx[i - 1];
			if(fx < 1 || fx > n || fy < 1 || fy > m) continue;
			if(s[fx][fy] == '*') continue;
			s[fx][fy] = '*';
			qu.push({fx, fy});
		}
	}
	return sum == (mx[0] - mn[0] + 1) * (mx[1] - mn[1] + 1);
}
void solved() {
	cin >> n >> m;
	_for(i, 1, n) cin >> s[i] + 1;
	int ans = 0;
	_for(i, 1, n) _for(j, 1, m)
		if(s[i][j] == '.') ans += bfs(i, j);
	cout << ans;
}
signed main() {
	solved();
	return 0;
}

E

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, I_MAX = b; i <= I_MAX; i ++)
#define _rep(i, a, b) for(int i = a, I_MIN = b; i >= I_MIN; i --)
typedef long long ll;
const int M = 1000009;

int w[M], d[M];
ll s[M];

void solved() {
	int n, m;  cin >> n >> m;
	_for(i, 1, n) cin >> w[i];
	_for(i, 1, n) cin >> d[i];
	_rep(i, n, 1) s[i] = max(s[i + 1], 0ll) + d[i];
	int r = 0;  ll ans = -1e18, sum = 0, f = 0;
	_for(i, 1, n) {
		while(r <= n && sum < m) {
			r ++;
			sum += w[r];
			f += d[r];
		}
		if(r > n) break;
		ans = max(ans, f + s[r] - d[r]);
		sum -= w[i];
		f -= d[i];
	}
	cout << ans;
}
signed main() {
	solved();
	return 0;
}

F

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, I_MAX = b; i <= I_MAX; i ++)
typedef long long ll;
typedef pair<int, int> pii;
#define _rep(i, a, b) for(int i = a, I_MIN = b; i >= I_MIN; i --)
const int N = 200009, Mx = 998244353;

ll a[N], ans;
set<pii> se;
int n;

ll pw(ll x) { return x * x; }
void del(pii pi) {
	ans -= pw(pi.second - pi.first + 1);
	se.erase(pi);
}
void add(int l, int r) {
	ans += pw(r - l + 1);
	se.insert({l, r});
}
void modify(int p, int w) {
	if(w == 0 || p > n) return ;
	pii pi = *(-- se.lower_bound({p, Mx}));
	del(pi);
	a[p] += w;
	if(pi.first == p) {
		if(a[p] == 1) {
			pii fpi = *(-- se.lower_bound({p, p}));
			del(fpi);
			add(fpi.first, pi.second);
		} else {
			add(pi.first, pi.second);
		}
	} else {
		add(pi.first, p - 1);
		add(p, pi.second);
	}
}
void solved() {
	int m;  cin >> n >> m;
	_for(i, 1, n) cin >> a[i];
	a[0] = 1e18;
	_rep(i, n, 1) a[i] -= a[i - 1];
	int pre = 1;
	_for(i, 2, n + 1) {
		if(a[i] == 1) continue;
		add(pre, i - 1);
		pre = i;
	}
	while(m --) {
		int l, r, w;  cin >> l >> r >> w;
		modify(l, w);
		modify(r + 1, -w);
		cout << ans << endl;
	}
}
signed main() {
	solved();
	return 0;
}