题解
2026暑期·第三场题解
admin LV 4 SU @ 2026-7-23 17:07:05

第三场题解

[TOC]

小黑子消除计划

解题思路

这题看着吓人，其实仔细观察可以发现，在任意一个如下的 $3*2$ 的区域中，对“356”、“456”、“134”三组点进行反转，最终结果是只翻转了1这个点，相当于我们可以任意修改点的颜色，因此本题直接输出0即可。

1 2
3 4
5 6

参考代码

print(0)

异或路径

解题思路

本题的路径长度最多为 $n+m-1$ ，直接枚举所有路径会超时。由于 $n,m\le 20$ ，可以使用折半搜索。

从左上角开始 DFS 到路径中间层，记录到达每个中间格子时的异或值出现次数；再从右下角反向 DFS 到同一层，设反向部分异或值为 t，若正向部分异或值为 t^k，两段拼起来后总异或值就是 k。注意正向搜索包含中间格子，反向搜索不包含中间格子，这样不会重复计算。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;

signed main(){
	int n, m, k; cin >> n >> m >> k;
	vector<vector<int>> g(n + 5, vector<int>(m + 5));
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			cin >> g[i][j];
	vector<vector<map<int, int>>> mp(n + 5, vector<map<int, int>>(m + 5));
	function<void(int, int, int)> dfs1 = [&](int x, int y, int t){
		if(x + y == (2 + n + m) / 2){
//			cout << x << ' ' << y << ' ' << t << endl;
			mp[x][y][t] ++;
			return;
		}
		if(x < n)	dfs1(x + 1, y , t ^ g[x + 1][y]);
		if(y < m)	dfs1(x, y + 1 , t ^ g[x][y + 1]);
	};
	dfs1(1, 1, g[1][1]);
	int res = 0;
	cout << endl;
	function<void(int, int, int)> dfs2 = [&](int x, int y, int t){
		if(x + y == (2 + n + m) / 2){
//			cout << x << ' ' << y << ' ' << t << ' ' << (k ^ t) << endl;
			res += mp[x][y][t ^ k];
			return;
		}
		t ^= g[x][y];
		if(x > 0)	dfs2(x - 1, y , t);
		if(y > 0)	dfs2(x, y - 1 , t);
	};
	dfs2(n, m, 0);
	cout << res << endl;
}

宗门之争

解题思路

对于一个节点，只要有连接比他大的节点，最终就一定会被删除，反之一定保留。

对于一条边 $(u,v)$ ，只有编号较小的点会被这条边影响，因此维护 s[x] 表示点 x 作为较小端点出现的边数。答案就是 s[x]=0 的点的数量。

加边时若 s[x] 从 0 变为正数，答案减一；删边时若 s[x] 变回 0，答案加一。每次操作只影响一条边的较小端点，所以可以 $O(1)$ 维护。

参考代码

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

int main(){
	int n, m; cin >> n >> m;
	vector<int> s(n + 5);
	int res = n;
	auto add = [&](int x){
		if(s[x] == 0)	res --;
		s[x] ++;
	};
	auto sub = [&](int x){
		s[x] --;
		if(s[x] == 0)	res ++;
	};
	for(int i = 0; i < m; i ++){
		int u, v; cin >> u >> v;
		add(min(u, v));
	}
	int q; cin >> q;
	for(int i = 0; i < q; i ++){
		int op; cin >> op;
		if(op == 1){
			int u, v; cin >> u >> v;
			add(min(u, v));
		}else if(op == 2){
			int u, v; cin >> u >> v;
			sub(min(u, v));
		}else{
			cout << res << endl;
		}
	}
}

0/1游戏

解题思路

全为1时先手全选即可获胜。

不全为1时，若第一个或最后一个为1，可以选除第一个（或最后一个）以外的，后手会拿到11，此时后手别无选择，先手获胜。

其余情况中，因为开头和结尾都是0，如果全选先手会直接输，不全则给到后手的一定有0，后手全选依旧可以获胜。

综上，开头或结尾有1时（全1也满足这个条件）先手获胜，反正后手获胜。

参考代码

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

using PII = pair<int, int>;

void sol(){
	int n; cin >> n;
	vector<int> a(n);
	int s = 0;
	for(int i = 0; i < n; i ++)	cin >> a[i], s += a[i];
	if(a[0] == 1 || a[n - 1] == 1)
		cout << "Albert_Li" << endl;
	else
		cout << "Tcs" << endl;
}

int main(){
	int t; cin >> t;
	while(t --)
		sol();
}

连锁反应

解题思路

显而易见，横着的骨牌只对列有影响，竖着的骨牌只对行有影响。

不难发现，只要每行每列涉及到的骨牌格子的数量都是偶数，就一定有解。

参考代码

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

void sol(){
	int n, m; cin >> n >> m;
	vector<string> g(n);
	for(int i = 0; i < n; i ++)	cin >> g[i];
	for(int i = 0; i < n; i ++){
		int t = 0;
		for(int j = 0; j < m; j ++)
			if(g[i][j] == 'U')
				t ++;
		if(t % 2){
			cout << -1 << endl;
			return ;
		}
		int s = 0;
		for(int j = 0; j < m; j ++) if(g[i][j] == 'U'){
			if(s < t / 2){
				g[i][j] = 'W';
				g[i + 1][j] = 'B';
			}else{
				g[i][j] = 'B';
				g[i + 1][j] = 'W';
			}
			s ++;
		}
	}
	for(int j = 0; j < m; j ++){
		int t = 0;
		for(int i = 0; i < n; i ++)
			if(g[i][j] == 'L')
				t ++;
		if(t % 2){
			cout << -1 << endl;
			return ;
		}
		int s = 0;
		for(int i = 0; i < n; i ++) if(g[i][j] == 'L'){
			if(s < t / 2){
				g[i][j] = 'W';
				g[i][j + 1] = 'B';
			}else{
				g[i][j] = 'B';
				g[i][j + 1] = 'W';
			}
			s ++;
		}
	}
	for(int i = 0; i < n; i ++)
		cout << g[i] << endl;
}

int main(){
	int t; cin >> t;
	while(t --)
		sol();
}

地下城

解题思路

将地下城按进入门槛排序。对于通关后会改变能力值的地下城，优先处理：把当前能力小于门槛的人移到备用队列，选择能力最小但能进入的人去打，打完后把能力更新为 max(当前能力, 奖励值) 再放回。

奖励值为 0 的地下城不会提升能力，先暂存起来。等所有能产生收益的地下城处理完后，再用剩下的人按门槛从小到大贪心匹配这些地下城即可。

参考代码

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

using PII = pair<int, int>;

void sol(){
	int n, m; cin >> n >> m;
	priority_queue<int, vector<int>, greater<int>> qu;
	for(int i = 0; i < n; i ++){
		int t; cin >> t;
		qu.push(t);
	}
	vector<PII> a(m);
	for(int i = 0; i < m; i ++)	cin >> a[i].first;
	for(int i = 0; i < m; i ++)	cin >> a[i].second;
	sort(a.begin(), a.end());
	queue<int> qu1, qu2;
	int res = 0;
	for(int i = 0; i < m; i ++){
		if(a[i].second == 0){
			qu1.push(a[i].first);
			continue;
		}
		while(qu.size() && qu.top() < a[i].first){
			qu2.push(qu.top());
			qu.pop();
		}
		if(qu.size() == 0)	break;
		res ++;
		int t = qu.top(); qu.pop();
		qu.push(max(t, a[i].second));
	}
	while(qu.size()){
		qu2.push(qu.top());
		qu.pop();
	}
	while(qu1.size()){
		while(qu2.size() && qu2.front() < qu1.front())	qu2.pop();
		if(qu2.empty()) break;
		res ++;
		qu1.pop(); qu2.pop();
	}
	cout << res << endl;
}

int main(){
	int t; cin >> t;
	while(t --)
		sol();
}

GCD？G 题没有 GCD 怎么说得过去！

解题思路

选择数组中的最小值作为锚点。由于它不大于任何其他元素，用它参与构造操作一定更容易满足限制。

代码中找到最小值所在位置 p，只对与 p 奇偶性不同的位置进行操作，输出操作 (i,p,1e9+7,a[p])。这样可以用一个足够大的质数和最小值统一构造，减少需要处理的位置数量。

参考代码

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

void sol(){
	int n; cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i ++)	cin >> a[i];
	int p = 0;
	for(int i = 1; i < n; i ++)
		if(a[i] < a[p])
			p = i;
	vector<int> res;
	for(int i = 0; i < n; i ++)
		if(i % 2 != p % 2)
			res.push_back(i);
	cout << res.size() << endl;
	for(auto it : res)
		cout << it + 1 << ' ' << p + 1 << ' ' << (int)1e9 + 7 << ' ' << a[p] << endl;
}

int main(){
	int t; cin >> t;
	while(t --)
		sol();
}

移除

解题思路

排序后考虑相邻元素。如果存在相邻差值大于 1，那么中间缺口无法通过移除操作弥补，答案为 NO；否则可以从小到大依次移除，答案为 YES。

参考代码

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

void sol(){
	int n; cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i ++)	cin >> a[i];
	sort(a.begin(), a.end());
	for(int i = 1; i < n; i ++)
		if(a[i] - a[i - 1] > 1){
			cout << "NO" << endl;
			return;
		}
	cout << "YES" << endl;
}

int main(){
	int t; cin >> t;
	while(t --)
		sol();
}

巨大的树

解题思路

每个点的值只从l[u] 和 r[u]中取值一定可以达到最优解。

那么本题就变为了一个模板的树上DP。

令 dp[u][0] 表示 u 选 l[u] 时，子树内能得到的最大贡献；dp[u][1] 表示 u 选 r[u] 时的最大贡献。

对每个儿子 v，如果 u 选了 l[u]，那么 v 可以选 l[v] 或 r[v]，取两种贡献最大值；u 选 r[u] 时同理。DFS 合并所有儿子即可。

参考代码

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

#define int long long
using PII = pair<int, int>;

vector<int> l, r;
vector<vector<int>> g;

PII dfs(int u, int fa) {
    PII res = {0, 0};

    for (auto v : g[u]) {
        if (v == fa) continue;

        PII t = dfs(v, u);

        res.first += max(
            abs(l[u] - l[v]) + t.first,
            abs(l[u] - r[v]) + t.second
        );

        res.second += max(
            abs(r[u] - l[v]) + t.first,
            abs(r[u] - r[v]) + t.second
        );
    }

    return res;
}

void sol() {
    int n;
    cin >> n;

    g.assign(n + 5, vector<int>());
    l.assign(n + 5, 0);
    r.assign(n + 5, 0);

    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    PII res = dfs(1, 0);

    cout << max(res.first, res.second) << endl;
}

signed main() {
    int t;
    cin >> t;

    while (t--) {
        sol();
    }

    return 0;
}

排队买饭

解题思路

就这点数据范围，大力出奇迹即可。

每一秒同时发生所有相邻的 BG -> GB 交换。模拟时从左到右扫描，如果发现 BG，就交换并让下标多跳一格，避免同一个人一秒内被交换多次。

参考代码

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

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, t; cin >> n >> t;
	string s; cin >> s;
	while(t --){
		for(int i = 1; i < n; i ++) if(s[i - 1] == 'B' && s[i] == 'G'){
			swap(s[i - 1], s[i]);
			i ++;
		}
	}
	cout << s << endl;
}

DP？

解题思路

~~一般标题里有的算法都不是这题考的~~。

不难发现，选择的左端点一定是在第一个p处。

5000的数据范围是可以 $n^2$ 的，直接暴力枚举右端点把最小的就可以了。

参考代码

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

signed main(){
	int n; cin >> n;
	string s; cin >> s;
	int p = -1;
	for(int i = 0; i < n; i ++)
		if(s[i] == 'p'){
			p = i;
			break;
		}
	if(p == -1){
		cout << s << endl;
		return 0;
	}
	vector<int> a;
	for(int i = p; i < n; i ++) a.push_back(i);
	auto ge = [&](int x, int y){
		if(x - y < p){
			return s[p + y] == 'p';
		}else{
			return s[x - y] != 'p';
		}
	};
	for(int i = 0; i < n - p; i ++){
		vector<int> b;
		int t = 1;
		for(auto it : a){
			int g = ge(it, i);
			if(g == 0)	b.push_back(it), t = 0;
		}
		if(t == 0)
			a = b;
	}
	for(int i = 0; i < p; i ++) cout << s[i];
	for(int i = p; i < n; i ++) cout << "dp"[ge(a[0], i - p)];
	
}

简单环

解题思路

一个连通块是简单环，当且仅当其中每个点的度数都是 2，并且点数至少为 3。DFS 遍历每个连通块，统计点数；如果遇到度数不为 2 的点，就把该连通块标记为非法。最后统计合法连通块数量即可。

参考代码

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

signed main(){
	int n, m; cin >> n >> m;
	vector<vector<int>> g(n + 5);
	for(int i = 0; i < m; i ++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int res = 0;
	vector<int> vis(n + 5);
	int s;
	function<void(int)> dfs = [&](int u){
		if(vis[u])	return ;
		if(g[u].size() != 2) s = - n;
		vis[u] = 1, s ++;
		for(int v : g[u]) dfs(v);
	};
	for(int i = 1; i <= n; i ++) if(!vis[i]){
		s = 0; dfs(i);
		if(s >= 3)	res ++;
	}
	cout << res << endl;
}

失去的

不要被交互题吓跑了哦。

解题思路

我们只需要确认5个数字，最后一个必然是剩下的那个。

这6个数字任选两个乘出来的结果都是不一样的。

因此我们可以知道选择了哪两个数字，只是不知道哪个是哪个。

综上，依次询问 $12，23，34，45$ ，第一次询问中出现且第二次询问中没出现的数字就是第一个数，同理就可以得到前五个数，最后一个数就是剩下的那个。

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

int fun(int x){
	if(x == 1)	return 4;
	if(x == 2)	return 8;
	if(x == 4)	return 15;
	if(x == 8)	return 16;
	if(x == 16)	return 23;
	if(x == 32)	return 42;
}

int q(int x, int y){
	cout << "? " << x << ' ' << y << endl;
	int res; cin >> res;
	return res;
}

signed main(){
	int a[] = {4, 8, 15, 16, 23, 42};
	int b[] = {1, 2, 4, 8, 16, 32};
	map<int, int> mp;
	for(int i = 0; i < 6; i ++)
		for(int j = i + 1; j < 6; j ++)
			mp[a[i] * a[j]] = b[i] | b[j];
	int c[] = {q(1, 2), q(2, 3), q(3, 4), q(4, 5)};
	int res[6];
	res[0] = fun(mp[c[0]] ^ (mp[c[0]] & mp[c[1]]));
	res[1] = fun(mp[c[0]] & mp[c[1]]);
	res[2] = fun(mp[c[1]] & mp[c[2]]);
	res[3] = fun(mp[c[2]] & mp[c[3]]);
	res[4] = fun(mp[c[3]] ^ (mp[c[2]] & mp[c[3]]));
	res[5] = fun(63 ^ (mp[c[0]] | mp[c[1]] | mp[c[2]] | mp[c[3]] | mp[c[4]]));
	cout << "! " << res[0] << ' ' << res[1] << ' ' << res[2] << ' ' << res[3] << ' ' << res[4] << ' ' << res[5] << endl;
}

目前还没有评论...

2026暑期·第三场题解

第三场题解

小黑子消除计划

解题思路

参考代码

异或路径

解题思路

参考代码

宗门之争

解题思路

参考代码

0/1游戏

解题思路

参考代码

连锁反应

解题思路

参考代码

地下城

解题思路

参考代码

GCD？G 题没有 GCD 怎么说得过去！

解题思路

参考代码

移除

解题思路

参考代码

巨大的树

解题思路

参考代码

排队买饭

解题思路

参考代码

DP？

解题思路

参考代码

简单环

解题思路

参考代码

失去的

解题思路

0 条评论

状态

开发

支持

关于

还没有账户？

登录