Codeforces Round 749 (Div. 1 + Div. 2)

Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1)

B - Omkar and Heavenly Tree

题意

要求构造出一个含有 $n$ 个节点的树，满足 $m$ 个条件，每个条件包含三个节点 $a, b, c$ （保证互不相等），要求 $a$ 到 $c$ 的最短路径上不出现 $b$ 节点。

数据范围：

$1\leqslant m < n\leqslant 10^5$ 。

思路

注意 $m < n$ ，这说明必有一个节点不会出现在条件的 $b$ 上，那么这个节点就不会被任何一个条件限制。

将这个节点作为根节点，和其他所有节点连接一条边，就完事了。。。

（主要是题目竟然还提示了，不论给出什么条件，都一定会有解 It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.）

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		vi vis(n+1);
		for (int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			vis[b] = 1;
		}
		for (int i = 0; i < n; i++) {
			if (vis[i+1] == 0) {
				for (int j = 0; j < n; j++) {
					if (i != j) {
						cout << i + 1 << ' ' << j + 1 << '\n';
					}
				}
				break;
			}
		}
	}
	return 0;
}

C - Omkar and Determination

题意

给出一个 $n$ 行 $m$ 列只含有.和X的网格图，每一个.代表空位置，X代表有障碍物的位置，从每个空位置出发，只能向左或上移动到空位置上，如果能移动到第一行或者第一列，则称该位置的状态是exitable的，否则是non-exitable的，对于障碍物位置一定是non-exitable的。

有q次询问，每次询问给出区间 $[l,r]$ ，代表原图中第 $l$ 列到第 $r$ 列所形成的子图，如果仅通过该子图每个位置的状态就能判断出每个位置是.还是X，则输出YES，否则输出NO。

数据范围：

$1\leqslant n, m\leqslant 10^6, nm\leqslant 10^6, q\leqslant 2\cdot 10^5$ 。

思路

解题的关键在于仔细读题，如果看到了只能向左或上前进，那么不难发现，如果一个.的左边和上边都是X，那么这两列一定是NO。

进一步，如果区间 $[l,r]$ 包含了上述的这两列，那么这整个区间也就是NO了。注意：如果 $l=r$ ，那么一定是YES（自证不难）。

于是问题转换为判断区间中是否包含错误区间，这个可以用前缀和完成，令错误区间第二列为1，求出区间和，如果大于0，则包含，反之不包含。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<string> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vi sum(m);
	for (int j = 1; j < m; j++) {
		for (int i = 1; i < n; i++) {
			if (a[i-1][j] == 'X' && a[i][j-1] == 'X') {
				sum[j] = 1;
				break;
			}
		}
		sum[j] += sum[j-1];
	}
	int Q;
	cin >> Q;
	while (Q--) {
		int a, b;
		cin >> a >> b;
		cout << (sum[b-1] - sum[a-1] ? "NO" : "YES") << '\n';
	}
	return 0;
}

D - Omkar and the Meaning of Life

交互题

题意

要求通过不超过 $2n$ 次交互，求出一个长度为 $n$ 的排列，每次交互如下：

令目标排列为 $p_1p_2\cdots p_n$ （你要求的），交互序列（长度为 $n$ ） $a_1a_2\cdots a_n,\ (a_i\in[1, n])$ （你输出的，用于交互的，不要求是排列，但注意 $a_i$ 有范围要求）

如果存在 $i, j$ 使得 $a_i+p_i = a_j+p_j$ ，则程序会返回你最小的 $i$ ，比如目标序列为 $23514$ ，交互序列为 $13121$ ，那么就有 $a_1+p_1=a_4+p_4=3,a_2+p_2=a_3+p_3=6$ ，那么程序就会返回 $1$ 。

如果不存在这样的 $i, j$ 那么程序返回 $0$ 。

数据范围：

$2\leqslant n\leqslant 100$ 。

思路

我的lj方法（2n次交互）

将交互序列，从左到右逐个设置为 $1$ 其他都是 $2$ ，从而找到目标排列中的 $1$ ，如果当前 $1$ 的位置在 $i$ ，若当前返回值 $j$ 不是 $i$ ，那么说明 $p_j+1 = p_i$ ，如果返回值为 $0$ 那么当前位置就是 $p_i = 1$ 。

通过 $1$ 再去逐个寻找 $2,3,4,\cdots,n$ ，假如当前已经寻找到了 $k$ ，如果 $k+1$ 在 $k$ 的右侧，那么上面的过程已经可以判断出 $k+1$ 的位置了，否则 $k+1$ 一定在 $k$ 的左侧，于是令当前值为 $2$ 其他值为 $1$ ，这样返回值就一定是 $k+1$ 的位置了，因为 $k+1$ 的位置一定小于 $k$ 的位置。

不难发现如果目标序列是 $n,n-1,\cdots, 2, 1$ 那么就会有 $2n$ 次交互。。。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
int n;
int chk(int x, int fg) {
	cout << "? ";
	for (int i = 1; i <= n; i++) {
		if (i != x) cout << 2 - fg << ' ';
		else cout << 1 + fg << ' ';
	}
	cout << '\n';
	cout.flush();
	int res;
	cin >> res;
	return res;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	vi fa(n+1);
	int p = 0;
	for (int i = 1; i <= n; i++) {
		int tmp = chk(i, 0);
		if (!tmp) p = i;
		else if (tmp != i) fa[tmp] = i;
	}
	vi ans(n+1);
	ans[p] = 1;
	for (int i = 2; i <= n; i++) {
		if (!fa[p]) p = chk(p, 1);
		else p = fa[p];
		ans[p] = i;
	}
	cout << "! ";
	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
	cout << '\n';
	return 0;
}

dalao的方法（n次交互）

题解中评论的方法tql

先确定下 $p_n$ 的值，方法是通过设置 $a_n = 2,3,\cdots$ ，其他值为 $1$ ，如果返回值为 $0$ ，则说明 $p_n = n+2-a_n$ 。

当确定下了 $p_n$ 后，之前 $a_n-1$ 次交互的返回值 $j$ 都可以确定下 $p_j = p_n + a_n -1$ ，不难发现 $p_j > p_n$ 。

最后，对于每个还没有确定的位置 $p_i$ ，我们知道 $p_i < p_n$ ，于是对于每一个 $i$ 我们都设置 $a_i = 2, 3, \cdots$ ，已经确定下来的位置（除了最后一个位置）都设置为 $n$ ， $a_n = 1$ ，这样每次的返回值 $j$ 都可以确定一个值 $p_j = p_n - a_i + 1$ 。

这样可以保证交互次数正好是 $n$ 次，因为每次都必定能确定下来一个值。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vi a(n+2), ans(n+1);
	for (int i = 2; i <= n; i++) {
		cout << "? ";
		for (int j = 1; j <= n; j++) {
			if (j != n) cout << 1 << ' ';
			else cout << i << '\n';
		}
		cout.flush();
		cin >> a[i];
		if (a[i] == 0 || i == n) {
			if (i == n && a[i]) ++i;
			ans[n] = n + 2 - i;
			for (int j = 2; j < i; j++) {
				ans[a[j]] = ans[n] + j - 1;
			}
			break;
		}
	}
	for (int i = 1; i < ans[n]; i++) {
		cout << "? ";
		for (int j = 1; j <= n; j++) {
			if (ans[j]) {
				if (j != n) cout << n << ' ';
				else cout << 1 << ' ';
			}
			else cout << i+1 << ' ';
		}
		cout << '\n';
		cout.flush();
		int x;
		cin >> x;
		ans[x] = ans[n] - i;
	}
	cout << "! ";
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << ' ';
	}
	return 0;
}

E - Moment of Bloom

题意

给出一个含有 $n$ 个节点 $m$ 条边的无向图（保证是连通图，且没有自环和重边），给出 $q$ 个条件，每个条件包含两个端点 $u, v$ ，你需要给出一条简单路径，两个端点分别是 $u, v$ ，然后将该路径经过的边权值都加1，请问是否存在一种方案，使得在 $q$ 次条件后，每条边的边权值都是偶数。

如果存在，则输出YES，然后对于每一个询问输出该简单路径所经过的节点。

否则，输出NO，然后输出至少还需要添加多少个条件，才能有满足题意的方案。

数据范围：

$nq\leqslant 3\times 10^5, n-1\leqslant m\leqslant\min\left(\dfrac{n(n-1)}{2},3\cdot 10^5\right)$

思路

这种奇偶性问题的题目，要抓住 $\text{奇}\times\text{奇}=\text{偶}, \text{奇}\times\text{偶}=\text{偶}, \text{偶}\times\text{偶} = \text{偶}$ ，所以当奇偶相乘时，奇数出现的次数相对偶数较少，于是考虑将奇数作为条件限制，这样配合题目条件就可以有较强的限制了。

考虑，如果存在一个节点 $u$ ，使得 $u$ 在条件中的出现次数为奇数，那么无论怎么规划路径，一定存在 $u$ 的一条相邻边，它的边权为奇数。（原因：先考虑以 $u$ 为端点的边，无论怎么规划路径， $u$ 都一定存在奇数个边权为奇数的相邻边 $\text{奇}\times\text{奇}=\text{奇}$ ，那么如果有其他简单路径经过节点 $u$ ，都无法使得 $u$ 的相邻边的边权全部变为偶数）

下面证明如果所有节点出现次数都是偶数，则存在一种构造方法求解，对原图重新做生成树，对于每次询问 $u, v$ ，返回生成树上 $u, v$ 的路径，这种方法最终生成的一定是一组解。（可以自己画画图理解，证明还有点复杂）

总复杂度 $O(nq)$ 。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
vi vis;
vii e, e1;
void build(int u) {
	vis[u] = 1;
	for (auto v : e[u]) {
		if (vis[v]) continue;
		e1[u].pb(v);
		e1[v].pb(u);
		build(v);
	}
}
bool print(int u, int en, int num) {
	vis[u] = 1;
	if (u == en) {
		cout << num << '\n';
		cout << u << ' ';
		return 1;
	}
	for (auto v : e1[u]) {
		if (vis[v]) continue;
		if (print(v, en, num+1)) {
			cout << u << ' ';
			return 1;
		}
	}
	return 0;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vis = vi(n+1);
	e = e1 = vii(n+1);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		e[u].pb(v);
		e[v].pb(u);
	}
	int Q;
	cin >> Q;
	vp query(Q);
	vi cnt(n+1);
	for (int i = 0; i < Q; i++) {
		int u, v;
		cin >> u >> v;
		cnt[u]++, cnt[v]++;
		query[i] = mkp(u, v);
	}
	int odd = 0;
	for (int i = 1; i <= n; i++) {
		if (cnt[i] & 1) {
			odd++;
		}
	}
	if (odd) {
		cout << "NO" << '\n' << (odd >> 1) << '\n';
		return 0;
	}
	cout << "YES" << '\n';
	build(1);
	for (auto q : query) {
		fill(vis.begin(), vis.end(), 0);
		int u = q.first, v = q.second;
		print(v, u, 1);
		cout << '\n';
	}
	return 0;
}

coding > cf

#图论 #构造题 #交互题 #贪心题

Codeforces Round 749 (Div. 1 + Div. 2)

https://wty-yy.github.io/posts/49235/

作者

wty

发布于

2021年10月22日

许可协议

曲线及其长度第一型曲线积分上一篇

多元积分变量代换及应用下一篇