视频题解

---

A

只要 $y-x\neq1$，那么 $y-x$ 一定能分解质因数写成 $p_1^{a_1}\times p_2^{a_2}...\times p_k^{a_k}$ 其中 $p_1,p_2...p_k$ 均为质数(唯一分解定理)，则随意选择一个 $p_i$ 即可满足条件

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long x,y,t;
	cin>>t;
	while (t--) {
		cin>>x>>y;
		if (y-x>1)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}

B

- 20pts:

可以搜索枚举所有的出栈方案

- 40pts:

入栈时栈顶元素是否弹出就是所有出栈的情况。要保证最后字符串字典序最小，对于当前栈顶 $top$，如果后续入栈的字符串还有比 $top$ 更小的，那么此时的 $top$ 则不能出栈，要等待后续更小的入栈再出栈。

即对栈顶 $top$ 判断后续是否还有更小的字符串，若没有，则可以出栈。朴素的判断的过程使用双重循环实现，$O(n^2)$

- 100pts:

对栈顶 $top$ 判断后续是否还有更小的字符串，使用后缀数组进行预处理，即使用数组 $p[i]$ 记录 $i\sim n$ 范围内最小的字符串位置，$O(n)$

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

const int N = 1e6 + 5;
string s[N], suf[N];

bool cmp(const string &s,const string &t){
	return s + t < t + s;
}

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
    	cin >> s[i];
	}
	suf[n] = s[n];
	for(int i = n - 1; i >= 1; i--){
		if(cmp(s[i], suf[i+1])) suf[i] = s[i];
		else suf[i] = suf[i+1];
	}
	stack<int>stk;
	int id = 1;
	while(id <= n || !stk.empty()){
		if(stk.empty()){
			stk.push(id);
			id++;
			continue;
		}
		int cur = stk.top();
		string cs = s[cur];
		if(id > n){
			cout << cur << ' ';
			stk.pop();
			continue;
		}
		string add = suf[id];
		if(cmp(cs, add) || cs + add == add + cs){
			//cs在前更优  或者 一样 
			cout << cur << ' ';
			stk.pop();
		}else{
			stk.push(id);
			id++;
		}
	}
    return 0;
}

C

- 30pts:

暴力搜索即可

- 100pts:

对于最后所求：$max(|H(A)-L(B)|,|H(B)-L(A)|)$，其中 $|H(A)-L(B)|=|\sum r-H(B)-L(B)|=|\sum r-(H(B)+L(B))|$；类似的，$|H(B)-L(A)|=|H(B)-(\sum l-L(B))|=|H(B)+L(B)-\sum l|$。

即为求 $max(|\sum r-(H(B)+L(B))|, |H(B)+L(B)-\sum l|)$ 的最小值。

其中 $\sum r,\sum l$ 均已知，枚举可行的 $H(B)+L(B)$。又因为 $\sum r\le 50\times 10000$，可使用动态规划，处理出所有可行的 $H(B)+L(B)$ 的情况。

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

int main() {
    int n;
    cin >> n;
    
    vector<int> l(n), r(n);
    int suml = 0, sumr = 0;
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
        suml += l[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> r[i];
        sumr += r[i];
    }

    int total = suml + sumr;
    vector<int> dp(total + 1, 0);
    dp[0] = 1;
    
    for (int i = 0; i < n; ++i) 
        // 逆序遍历防止重复选择
        for (int j = total; j >= 0; --j) 
            if (dp[j])  dp[j + l[i] + r[i]] = 1;


    int ans = 1e9;
    for (int i = 0; i <= total; ++i) {
        if (dp[i]) {
            int diff1 = abs(suml - i);          
            int diff2 = abs(sumr - i); 
            ans = min(ans, max(diff1, diff2));
        }
    }

    cout << ans << endl;
    return 0;
}

D

- 20pts:

枚举 $2$ 种颜色，再枚举地图上的某个起点，做 bfs/dfs，$O(n\times m\times a_{ij}^2)$

- 100pts:

预处理出四方向同色的所有联通块，再枚举相邻的联通块 $2$ 种颜色，使用并查集，将相邻且颜色符合条件的联通块逐一连接并求其大小。$O(n\times m \times log(n\times m))$

#include <bits/stdc++.h>

using namespace std;

const int MaxN = (int)2e3 + 10;
const int MOD = (int)1e9 + 7;
const int INF = 1e9;

int m, n;
int a[MaxN][MaxN], ptr;
int visited[MaxN][MaxN];
int sizes[MaxN * MaxN];
int who[MaxN * MaxN], sz[MaxN * MaxN];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int getWho(int v)
{
	return v == who[v] ? v : who[v] = getWho(who[v]);
}

int main()
{
	//	ios::sync_with_stdio(false); cin.tie(NULL);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (visited[i][j] != 0)
			{
				continue;
			}
			queue<pair<int, int>> q;
			q.push(make_pair(i, j));
			visited[i][j] = ++ptr;
			int qt = 1;
			while (!q.empty())
			{
				int x = q.front().first, y = q.front().second;
				q.pop();
				for (int k = 0; k < 4; ++k)
				{
					int nx = x + dx[k], ny = y + dy[k];
					if (!visited[nx][ny] && a[nx][ny] == a[x][y])
					{
						visited[nx][ny] = ptr;
						q.push(make_pair(nx, ny));
						qt++;
					}
				}
			}
			sizes[ptr] = qt;
		}
	}
	map<pair<int, int>, vector<pair<int, int>>> ed;
	int ans = 0;
	for (int i = 1; i <= ptr; ++i)
	{
		who[i] = i;
		sz[i] = sizes[i];
		ans = max(ans, sz[i]);
	}
	for (int x = 1; x <= n; ++x)
	{
		for (int y = 1; y <= m; ++y)
		{
			for (int k = 0; k < 4; ++k)
			{
				int nx = x + dx[k], ny = y + dy[k];
				if (a[nx][ny] <= a[x][y])
				{
					continue;
				}
				ed[make_pair(a[x][y], a[nx][ny])].push_back(make_pair(visited[x][y], visited[nx][ny]));
			}
		}
	}
	for (auto &vec : ed)
	{
		vector<int> changed;
		for (auto &it : vec.second)
		{
			int x = it.first, y = it.second;
			changed.push_back(x);
			changed.push_back(y);
			int xx = getWho(x), yy = getWho(y);
			if (xx == yy) continue;
			if (sz[xx] > sz[yy]) swap(xx, yy);
			who[xx] = yy;
			sz[yy] += sz[xx];
			ans = max(ans, sz[yy]);
		}
		for (auto &it : changed)
		{
			sz[it] = sizes[it];
			who[it] = it;
		}
	}
	printf("%d\n", ans);
	return 0;
}