Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客

Codeforces Round 770

Wings  收录于  类别 ACM
     约 4131 字  预计阅读 9 分钟    次阅读     条评论  

准备复健, 没敢打比赛怕掉分, 先做做题练练手.

好题, 可惜 AlphaCode 咕了.

Terminator is ready to take part in Codeforces Round #770 (Div. 2)
Terminator is ready to take part in Codeforces Round #770 (Div. 2)
这个出题人太可爱了叭
Codeforces Round #770 (Div. 2) is ready to resist the rise of machines

题解

给一个长度为 $n$ 的字符串 $s$, 对他进行 $k$ 次操作, 每次操作为其中之一:

  • $s \leftarrow s + rev(s)$
  • $s \leftarrow rev(s) + s$ 其中, $rev(s)$ 表示将字符串翻转. 问最后能得到多少个不同的字符串.

$1 \le n \le 100$, $0 \le k \le 1000$

很容易发现, 如果 $s$ 回文, 那么两种操作得到的字符串是一样的. 然而, 两种操作本身就在构造回文. 所以, 在 $k > 0$ 的情况下, $s$ 本身回文时, 答案就是 $1$, 否则答案是 $2$. 注意有 $k = 0$, 特判一下.

复杂度 $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int T, n, k;
char str[MAXN];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%s", &n, &k, str);
		bool flag = 0;
		for (int i = 0; str[i]; i++)
			flag |= str[i] != str[n-i-1];
		flag ^= 1;
		puts(!k ? "1" : flag ? "1" : "2");
	}
	return 0;
}

一个数 $d$ 和一个长度为 $n$ 的数列 $a$, 按顺序进行如下操作之一:

  • $d \leftarrow d + a_i$
  • $d \leftarrow d \oplus a_i$ 最后会得到一个数 $y$. 现给出 $x$ 和 $y$, 问 $d = x$ 时还是 $d = x + 3$ 时能够得到 $y$. 数据保证有且仅有一者能.

$1 \le n \le 10^5$, $0 \le x \le 10^9$, $0 \le y \le 10^{15}$

说实话, 我人看傻了. 首先这个异或和加就没办法结合, 然后 $x$ 和 $x+3$ 也不知道是为啥, 还有一个 “数据保证…”, 就更不知道怎么办了. 当时写的时候没动纸笔, 光想了挺久也没想出来, 就跳过了, 先做 C 去了.

后来猜测奇偶性, 对着样例没看出来. 打了个表, 枚举了所有可能的操作, 丢 $x$ 和 $x+3$ 去跑了跑, 结果还真是, $x$ 跑出来的所有结果奇偶性相同, $x+3$ 的也是, 并且和 $x$ 的相反.

突然就想通了. 异或是不进位加法, 虽然这导致其无法与加法结合, 但是, 如果只看二进制下的最低位, 那么加法虽然进位了, 但是我们不看, 于是就等同于异或. 所以他们对最低位的贡献是完全一样的, 表现在整个结果上, 就是奇偶性相同. 而 $x + 3$ 正好与 $x$ 奇偶性相反.

复杂度 $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int T, n;
LL x, y, a[MAXN];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%lld%lld", &n, &x, &y);
		for (int i = 1; i <= n; i++)
			scanf("%d", a + i);
		for (int i = 1; i <= n; i++)
			x ^= a[i];
		puts((y^x) & 1 ? "Bob" : "Alice");
	}
	return 0;
}

翻了翻评论, 很多人都说 $x + 3$ 太有迷惑性了, 如果是 $x + 1$ 可能会好想很多. (后面还有人说是为了迷惑 AI.) 然后出题人在下面说了一句, 本来还想用 $x^2 - 1$ 的…

将整数 $1 \sim nk$ 填入 $n \times k$ 的矩阵, 使得每一行, 任意子串的平均值为整数. 构造或判断无解

$1 \le n, k \le 500$

先找怎样的序列能够使得任意子串平均值都是整数. 发现 $1, 3, 5, 7 \dots$ 可以. 然后就想, 我把每个数都加 $1$, 这样任意的平均值也会加 $1$. 于是就可以这样构造:

$$\begin{array}{cccc} 1 & 3 & 5 & 7 \\ 2 & 4 & 6 & 8 \\ 9 & 11 & 13 & 15 \\ 10 & 12 & 14 & 16 \end{array} $$

发现两行能够填连续的 $2k$ 个数字. 而且只有这种情况能够让填入的数字"密度"最大(从不超过 $nk$ 的角度去考虑填的数字).

想了想貌似没其他做法了. 就写了发交了.

复杂度 $O(nk)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int T, n, m, out[MAXN][MAXN];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		if (m == 1) {
			puts("YES");
			for (int i = 1; i <= n; i++)
				printf("%d\n", i);
		}
		else if (n & 1)
			puts("NO");
		else {
			puts("YES");
			int cur = 1;
			for (int i = 1; i <= n; i += 2)
				for (int j = 1; j <= m; j++) {
					out[i][j] = cur++;
					out[i+1][j] = cur++;
				}
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= m; j++)
					printf("%d%c", out[i][j], " \n"[j == m]);
		}
	}
	return 0;
}

交互. 一个长度为 $n$ 的序列 $a_i$, 其中有且仅有一个数为 $0$. 可以做如下询问, 选三个不同位置的数, 得到他们的极差($\max{a_i, a_j, a_k} - \min{a_i, a_j, a_k}$). 要求用不超过 $2n - 2$ 次询问, 确定两个可能是 $0$ 的位置.

看到这个 $2n - 2$, 就想着是不是扫两遍了. 于是先固定 $i, j$, 假如是 $1, 2$. 然后 $k$ 去扫. 发现如果 $i, j$ 不是最大值或者最小值, 极差最大的那个 $k$, 一定离 “线段 $i, j$” 最远. 这样扫完以后, 再用移动另一个, 比如说 $j$, 再找一个极差最大的位置, 此时, 如果原来的 $i, j$ 不是最大值或者最小值, 那么 $j, k$ 一定是最大的和最小的.

这样很容易发现, 最大值和最小值是对等的. 所以我们回答的, 其实是"最长的线段".

那么问题就来了, 如果第一次选取的 $i, j$ 存在最大值或者最小值, 该怎么办. 不过也很好分析, 只需要模拟一遍情况即可.

  1. 如果 $i$, $j$ 都是最值, 那么移动 $j$ 后, 所有的极差都不会比移动前大.

  2. 如果 $j$ 是最值, $i$ 不是最值, 那么第一遍扫到的 $k$ 一定是另一个最值. 然后 $j$ 移动掉了, 这时候的所有极差都不会比移动前大.

  3. 如果 $i$ 是最值, $j$ 不是最值, 那么第一遍扫到的 $k$ 一定是另一个最值. 然后 $j$ 移动, 最值不变.

第三条很好区分, 第一条和第二条暂时无法区分. 不过我们只用了 $2n - 5$ 次询问, 还可以继续询问, 以区分他们.

区分一和二, 就是判断 $i$ 是不是最值. 那么我们只需要移动 $i$, 看看极差会不会变小. 如果无论怎么移动, 极差都会变小, 那么 $i$ 一定是最值; 如果有一个相等的, 那么 $i$ 可能会是最大值, 而不可能是最小值(因为最小值只有一个, 而最大值可能有多个), 所以我们不选 $i$. 如果 $i$ 不是最值, 那么移动后极差只会不变. 综上, 我们只需要移动一次, 如果极差变小了, 那么 $i$ 就是最值; 如果没变, 那么 $i$ 一定不是最小值. 这样就能够确定 $i$ 要不要选了.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

int T, n;

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

void confirm(int x, int y) {
	cout << "! " << x << ' ' << y << endl;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n;
		int i = 1, j = 2, k;
		int mx = 0;
		for (int kk = 3; kk <= n; kk++) {
			int res = query(i, j, kk);
			if (res > mx)
				mx = res, k = kk;
		}
		int cnt1 = 0, cnt2 = 0;
		for (int jj = 3; jj <= n; jj++) if (jj != k) {
			int res = query(i, jj, k);
			if (res > mx)
				mx = res, j = jj, cnt1++;
			else if (res == mx)
				cnt2++;
		}
		if (cnt1 == 0) {
			if (cnt2 == n-3)
				confirm(i, k);
			else {
				int flag = 0;
				for (int ii = 2; ii <= n; ii++) if (ii != j && ii != k) {
					int res = query(ii, j, k);
					if (res < mx)
						flag = 1;
					break;
				}
				confirm(j, flag ? i : k);
			}
		}
		else
			confirm(j, k);
	}
	return 0;
}

给出 $m$ 个长度为 $n_i$ 的序列 $a_{ij}$, 其中 $2 \mid n_i$. 要求对每一个序列, 把一半放进可重集 $L$ 中, 另一半放进可重集 $R$ 中. 最后 $m$ 序列个都放完, 能不能得到 $L = R$. 若能, 给出方案.

$1 \le m \le 10^5$, $2 \le n_i \le 10^5, 2 \mid n_i$, $\sum n_i \le 10^5$, $1 \le a_{ij} \le 10^9$

想不到, 这题神仙题.

直觉告诉我, 只要没有奇数, 就都能做.

直觉告诉我是图论, 因为我想到了二分图黑白染色上去. 但是我并不能构造出, 选了一个就不能选另一个的图. 这个数据范围也不可能是网络流.

偷看题解.

题解直接说一堆偶数, 然后就欧拉回路也是偶数. 这也太难了吧. 应该不是这么一个思考逻辑. 可能有些题是这样的吧, 发现了性质, 然后看到某些图有这样的性质.

如果找不到这样的图, 可以先尝试乱连边建图, 看看能得到什么.

建图的方法其实要总结也是有的, 二分图黑白染色是 “互斥型” 建图, 而我们这里要用到的是 “支配型” 建图. 建图方法之前网络流总结过, 可以拿来借鉴, 用在其他图论问题中.

支配型的意思是, 如果你属于我, 我就和你连边. 我们把数字先离散化, 如果第 $i$ 个序列, 有 $x$ 这个数, 那么就连一条边. 为了直观, 可以把序列放在左边, 数放在右边. 如果有好几个 $x$, 也连好几条边. 然后可以发现, 左边点的度数, 就是 $n_i$, 右边 $x$ 的度数, 就是它在所有序列中出现的次数. 如果沿着边去走, 会发现, 左边点的 “入度” 等于 “出度”. 这恰好可以把他支配的数分成两份. 而对于右边的数来说, 也是一样的. 于是, 我们只需要遍历一下, 确定 “边的方向”, 就构造出来了. 非常平凡, 不用证明都知道是对的. 于是这里就有了欧拉回路了. 如果一个数出现的次数是奇数, 那么不存在欧拉回路. 这也和上面的猜想对应了.

复杂度 $O(\sum n_i + m)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

const int MAXN = 2e5 + 10;
const int MAXV = 3e5 + 10;
const int MAXE = MAXN;

struct Edge { int to, next; bool vis;} edges[MAXE<<1];
int mm = 0, head[MAXV];
void addEdge(int u, int v) {
	edges[mm] = {v, head[u], 0};
	head[u] = mm++;
}

int T, m, n, idx, cnt[MAXN];
bool vis[MAXE];
map<int, int> id;
char ans[MAXN];
VI ns;

void dfs(int u) {
	for (int &i = head[u]; ~i; i = edges[i].next)
		if (!edges[i].vis) {
			ans[i/2 + 1] = "LR"[i&1];
			edges[i].vis = 1;
			edges[i^1].vis = 1;
			dfs(edges[i].to);
		}
}

int main() {
	memset(head, -1, sizeof(head));
	scanf("%d", &m);
	idx = m;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &n);
		ns.emplace_back(n);
		for (int j = 1; j <= n; j++) {
			int x;
			scanf("%d", &x);
			cnt[(x = id[x] ? id[x] : id[x] = ++idx) - m]++;
			addEdge(i, x), addEdge(x, i);
		}
	}
	for (int i = 1; i <= id.size(); i++)
		if (cnt[i] & 1) {
			puts("NO");
			return 0;
		}
	int v = m + id.size();
	for (int i = 1; i <= id.size() + m; i++)
		dfs(i);
	puts("YES");
	int cc = 0;
	for (auto n : ns) {
		for (int i = 1; i <= n; i++)
			printf("%c", ans[++cc]);
		puts("");
	}
	return 0;
}

注意这个链式前项星的写法 dfs 时要加当前弧优化, 否则复杂度是 $O((\sum n_i)^2 + m)$ 的. 是的我这里没看出来, T 到怀疑人生.

给出两个长度为 $n$ 的序列 $A, B$, $q$ 次操作, 每次选 $A$ 或者 $B$, 给区间 $[l, r]$ 加上从头开始的斐波那契数列, 并回答 $A, B$ 在模 $P$ 意义下是否相等($P$ 不变).

$1 \le n, q \le 3 \cdot 10^5$, $1 \le P \le 10^9 + 7$

想不到, 神仙题.

提示里是说把区间加斐波那契换成区间加常数, 能不能不用数据结构做.

首先把他变成维护一个序列, 判断序列是否全为 $0$.

啊确实可以, 差分一下, 统计非 $0$ 位置的个数即可. 因为差分序列全为 $0$ 当且仅当原序列全为 $0$.

然后怎么搞斐波那契呢? 我还是傻傻的对斐波那契差分, 想找他有啥性质.

这里就能够体现我多菜了. 不会思考.

我们为什么区间加的时候要差分呢? 因为这样需要维护的数就变少了. 应该从这个角度去考虑, 如何对序列操作, 使得区间加斐波那契, 需要维护的数变少.

众所周知, 斐波那契公式为 $F_i = F_{i-1} + F_{i-2}$. 变形可以得到 $F_i - F_{i-1} - F_{i-2} \equiv 0$. 就像区间加那样, $c - c \equiv 0$. 于是我们可以对序列做 “斐波那契差分”, 也就是, 令 $D_1 = C_1$, $D_2 = C_2 - C_1$, $D_i = C_i - C_{i-1} - C_{i-2}, i > 2$. 这样, 如果我加一个斐波那契, 那么对 $D$ 来说, 手推一下可以得到, 在 $D_i$ 的位置加 $1$, 在 $D_{i+k+1}$ 的位置减 $F_{k+2}$, 在 $D_{i+k+2}$ 的位置减 $F_{k+1}$. 差分完后, 再 “斐波那契前缀和”, 令 $C_i = C_{i-1} + C_{i-2} + D_i$ 即可得到原序列. 同样的, $D$ 全 $0$ 当且仅当 $C$ 全 $0$ 也成立.

妙啊, 果然我学习不懂原理, 只会抓表面, 变一下就用不来了. 我太菜了.

复杂度 $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

int P;
int pls(LL a, LL b) {
	a += a < 0 ? P : 0, b += b < 0 ? P : 0;
	return a + b >= P ? a + b - P : a + b;
}
int mult(LL a, LL b) {
	a += a < 0 ? P : 0, b += b < 0 ? P : 0;
	return a * b >= P ? a * b % P : a * b;
}

int T, n, q, a[MAXN], b[MAXN], F[MAXN], cnt;

void check(int p, int d) {
	if (p > n)
		return;
	int now = pls(a[p], d);
	if (a[p] && !now)
		cnt--;
	else if (!a[p] && now)
		cnt++;
	a[p] = now;
}

void update(int l, int r, int sign) {
	check(l, sign);
	check(r+1, mult(-1, mult(sign, F[r-l+2])));
	check(r+2, mult(-1, mult(sign, F[r-l+1])));
}

int main() {
	scanf("%d%d%d", &n, &q, &P);
	F[1] = F[2] = 1;
	for (int i = 3; i <= n; i++)
		F[i] = pls(F[i-1], F[i-2]);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i++)
		scanf("%d", b + i);
	for (int i = 1; i <= n; i++)
		a[i] = pls(a[i], -b[i]);
	for (int i = n; i >= 2; i--)
		a[i] = pls(a[i], -pls(a[i-1], a[i-2]));
	for (int i = 1; i <= n; i++)
		if (a[i])
			cnt++;
	while (q--) {
		char op[5];
		int l, r;
		scanf("%s%d%d", op, &l, &r);
		update(l, r, op[0] == 'A' ? 1 : -1);
		puts(cnt ? "NO" : "YES");
	}
	return 0;
}
更新于 2022-02-15
 思维
返回 | 主页