Codeforces Round 682 (Div. 2)

http://codeforces.com/contest/1438

C. Engineer Artem

 

题意：给定一个矩阵，对每个数可以+1一次或者不动，要构造出每个数和相邻的四个数都不同。

构造

当遇到需要两个数不同时，可以考虑变成一奇一偶。

而一次+1操作恰好可以改变奇偶性。

把矩阵变成奇偶交错的情况。

#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int T;
int n, m;
int a[110][110];
int main() {
	scanf("%d", &T);
	while (T--) {
		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 (i & 1) {
					if ((a[i][j] & 1) != (j & 1))a[i][j]++;
				}
				else {
					if ((a[i][j] & 1) == (j & 1))a[i][j]++;
				}
				printf("%d%c", a[i][j], " \n"[j == m]);
			}
		}
	}
	return 0;
}

 

D. Powerful Ksenia

 

题意：给定一个数列，不超过 n 次操作，每次操作选择三个位置，都变成 $a_i \oplus a_j \oplus a_k$，要求构造出数列中所有数都相同。

构造

首先能看出的规律是，如果 $a_i=a_j$，则一次操作会把 $a_i,a_j$ 都变成 $a_k$。

所以，如果能构造出 $1,1,2,2,3,3,4,4,5$ 这样的数列，可以选择 $(1,1,5),(2,2,5),(3,3,5),\cdots$，这样使得每个数都变成 $5$。

当数列长度 $n$ 为奇数时，对于数列 $1,2,3,4,5,6,7$，操作 $(1,2,3),(3,4,5),(5,6,7)$，则可以变成 $1,1,2,2,3,3,3$ 然后就可以用上面的方法了。（这里 $1,2,3,\cdots$ 不是真正的数，只是为了区分表示不同的数字）

当数列长度 $n$ 为偶数时。继续找规律。我们发现每次操作使得三个数都变成 $a_i \oplus a_j \oplus a_k$，新的异或和仍然是 $a_i \oplus a_j \oplus a_k$，所以操作不会改变数列的异或和。而最终每个数都相等，且长度又是偶数，所以异或和为 $0$，也就是说如果数列能够构造出答案，那么数列的异或和必须为 $0$。那么我们直接忽略最后一个数，按照 $n$ 为奇数时的方法，把数列前 $n-1$ 个数都变成相同的数，而整个数列异或和又必须为 $0$，则最后一个数必须要等于前面 $n-1$ 个数，否则必定无法构造出答案。

#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	if (n & 1) {
		puts("YES");
		printf("%d\n", (n - 3) / 2+1 + (n - 1) / 2);
		for (int i = 0; 2 * i + 3 <= n; i++) {
			printf("%d %d %d\n", 2 * i + 1, 2 * i + 2, 2 * i + 3);
		}
		for (int i = 1; i < n; i += 2) {
			printf("%d %d %d\n", i, i + 1, n);
		}
	}
	else {
		for (int i = 1; i <= n; i++)a[i] ^= a[i - 1];
		if (a[n])puts("NO");
		else {
			puts("YES");
			n--;
			printf("%d\n", (n - 3) / 2+1 + (n - 1) / 2);
			for (int i = 0; 2 * i + 3 <= n; i++) {
				printf("%d %d %d\n", 2 * i + 1, 2 * i + 2, 2 * i + 3);
			}
			for (int i = 1; i < n; i += 2) {
				printf("%d %d %d\n", i, i + 1, n);
			}
		}
	}
	return 0;
}

 

E. Yurii Can Do Everything

 

题意：定义一个子串 $a[l...r]$ 为好子串当且仅当 $(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$。给定数列，问有几个好的连续子串。

暴力+复杂度

枚举左端点，对于每个左端点，暴力枚举右端点，判断是否符合条件，设 $k=\log_2 a_l$，当 $a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1}\ge 2^{k+1}$ 时停止枚举右端点。

再翻转整个数组，再做一次上述操作，同时去重。

由于异或不会使得最高位变得更高，所以满足条件的区间必定有 $a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1}< 2^{\max(\log a_l,\log a_r)+1}$，所以上述操作能检测到所有好串。

复杂度证明：

对于一个固定的 $k$，设以第 $k$ 位为最高位的所有数为 $a_{b_1},a_{b_2},\cdots,a_{b_t}$，假设现在以 $a_{b_1}$ 为左端点，那么右端点最多枚举到 $a_{b_3}$，因为 $a_{b_2},a_{b_2}\ge 2^k \implies a_{b_2}+a_{b_3}\ge 2^{k+1}$，所以最多把整个数列枚举 $2$ 次。

而有 $\log a_i$ 个 $k$，所以复杂度为 $O(n\log a_i)$。

#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
ll a[N];
int gt(ll x) {
	int res = -1;
	while (x) {
		x >>= 1;
		res++;
	}
	return res;
}
ll ans;
unordered_map<int, int>mp[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	for (int i = 1; i <= n - 2; i++) {
		int k = gt(a[i]);
		ll sum = a[i + 1];
		for (int j = i + 2; j <= n && sum < (1ll << (k + 1)); j++) {
			if (sum == (a[i] ^ a[j])) {
				ans++;
				mp[i][j] = 1;
			}
			sum += a[j];
		}
	}
	reverse(a + 1, a + n + 1);
	for (int i = 1; i <= n - 2; i++) {
		int k = gt(a[i]);
		ll sum = a[i + 1];
		for (int j = i + 2; j <= n && sum < (1ll << (k + 1)); j++) {
			if (sum == (a[i] ^ a[j]) && !mp[n + 1 - j].count(n + 1 - i)) {
				ans++;
			}
			sum += a[j];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. Olha and Igor

 

题意：交互题。有一棵完全二叉树，每次询问回答，当以 $w$ 为根时， $u,v$ 的LCA，$u,v,w$ 都不同。问这棵完全二叉树的根。

随机

对于点 $x$，若 $u,v,w$ 分别在 $x$ 的三棵子树中，则以 $w$ 为根时， $u,v$ 的 LCA 为 $x$。

假设叶子节点深度为 1，向上深度递增，则 $(u,v,w)$ 分别在 $x$ 的三棵子树中的情况数为 $(2^{dep-1}-1)^2\cdot (2^n-2^{dep})$，三部分和为定值，则越接近，乘积越大，所以当 $2^{dep-1}=2^h-2^{dep}$ 时乘积最大，这表明 $x$ 越接近根越好，（根不行，因为根只有两棵子树）。

这样找到被回答次数最多的两个节点，就是根的两个儿子 $u,v$。

再枚举所有其他节点 $w$，如果它们三个点的LCA为 $w$ ，则 $w$ 就是根。

#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define random(a,b) uniform_int_distribution<int> ((a), (b))(mt)
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int h, n;
int ask(int u, int v, int w) {
	cout << "? " << u << " " << v << " " << w << endl;
	int x;
	cin >> x;
	return x;
}
int cnt[N];
priority_queue<pair<int, int> >q;
int main() {
	cin.tie(0); cout.tie(0);
	cin >> h;
	n = (1 << h) - 1;
	for (int i = 0; i < 420; i++) {
		int u = random(1, n), v = random(1, n);
		while (u == v)v = random(1, n);
		int w = random(1, n);
		while (w == u || w == v)w = random(1, n);
		cnt[ask(u, v, w)]++;
	}
	for (int i = 1; i <= n; i++)q.push({ cnt[i],i });
	int a = q.top().second; q.pop();
	int b = q.top().second;
	for (int i = 1; i <= n; i++) {
		if (i != a && i != b) {
			if (ask(a, b, i) == i) {
				cout << "! " << i << endl;
				return 0;
			}
		}
	}
	return 0;
}