[Codeforces]近期比赛交互题选讲

• 自从 2020.1.1 到现在，CF 一共 (4) 场 Div. 1 contest

• 除了第一场之外，每场 contest 的比赛公告都有一句话：There will be an interactive problem in the round.（或类似的形式）

• 第一场公告没有这句话，但还是有交互题

• （交互题或成 CF Round(Div. 1) 必出？？？）

• 这里就在这 (4) 场 Div. 1 contest 中选 (3) 场的交互题出来讲

• （至于为什么有一道题没拿出来讲，那是因为一看到难度 3500 不是很想去做）

• 这 (3) 题按照所在 Round 的时间顺序讲

1286C Madhouse Easy Version Hard Version

Statement

• 有一个长度为 (n)，字符集为小写英文字母的字符串

• 每次询问给定 (lle r)，可以得到该字符串的子串 ([l,r]) 的所有子串，但这些子串是乱序给出的，每个子串里的字符也是乱序的

• 需要用不超过 (3) 次询问得到这个字符串

• 对于 Easy Version，需要满足所有询问得到的子串个数之和不超过 ((n+1)^2)

• 对于 Hard Version，需要满足所有询问得到的子串个数之和不超过 (0.777(n+1)^2)

• (1le nle 100)

Solution

• 可以发现这题的关键在于两个：

• （1）把一个子串内的所有字符乱序给出相当于给出了这个子串内所有字符的出现次数

• （2）对于同一个询问得到的两个子串，只有按照它们的长度才能把它们区分开

• 先考虑 Easy Version，考虑 ([1,n]) 的所有长度为 (i) 的子串和 ([2,n]) 的所有长度为 (i) 的子串

• 易得 ([1,n]) 只比 ([2,n]) 多了一个子串 ([1,i])

• 所以询问一次 ([1,n]) 一次 ([2,n])

• 对于每个 (1le ile n)，求出 ([1,n]) 和 ([2,n]) 所有长度为 (i) 的子串各个字符出现次数的和

• 然后作差，就能得出 ([1,i]) 各个字符出现的次数

• 最后再对于每个 (i)，让 ([1,i]) 与 ([1,i-1]) 作差即可得到 (i) 位置上的字符

• 询问次数为 (2)，子串个数为 (inom{n+1}2+inom{n}2=n^2<(n+1)^2)

• 对于 Hard Version，考虑 ([1,n]) 还可以询问出什么

• 还是考虑所有长度为 (i) 的子串。不过这里尝试计算每个字符的贡献

• 可以发现当 (ilelceilfrac n2 ceil) 时，原串一个位置 (j)，贡献了 (min(j,n-j+1,i)) 次，画成图大概是一个梯形

• 而长度变为 (i-1) 时 (j) 的贡献会变化当且仅当 (min(j,n-j+1)ge i)，也就是 (jin[i,n-i+1])

• 于是长度为 (i) 的所有子串之和减去长度为 (i-1) 的所有子串之和即为子串 ([i,n-i+1])，可以直观理解成两个梯形的面积相减

• 然后再把这些形如 ([i,n-i+1]) 的子串进行差分，就能得到对于所有的 (1le ilelceilfrac n2 ceil)，原串的第 (i) 位和第 (n-i+1) 位上的字符是什么（但不能得到哪个字符对应哪个位置，且特殊地如果 (n) 为奇数且 (i=lceilfrac n2 ceil) 则直接得到第 (i) 位的字符）

• 于是这时候只需知道前一半（([1,lfloorfrac n2 floor])）的字符串就能知道后一半

• 对于前一半字符串跑一遍 Easy Version 即可

• 询问数为 (3)，子串个数不超过 (inom{n+1}2+(frac n2)^2<0.75(n+1)^2)

Code

• 和上面的做法略有不同

#include <bits/stdc++.h>

const int N = 105;

int n, m, sum[N][26], tot[N], cw[N][2], cur[26];
char s[N], ans[N];

int main()
{
	std::cin >> n;
	printf("? %d %d
", 1, n); fflush(stdout);
	for (int i = 1; i <= n * (n + 1) / 2; i++)
	{
		scanf("%s", s + 1);
		int len = strlen(s + 1);
		for (int j = 1; j <= len; j++)
			sum[len][s[j] - 'a']++;
	}
	m = n >> 1;
	for (int i = 1; i <= m - ((n & 1) ^ 1); i++)
	{
		for (int c = 0; c < 26; c++) cur[c] = sum[i + 1][c];
		for (int j = 1; j < i; j++) cur[cw[j][0]] += i - j + 1,
			cur[cw[j][1]] += i - j + 1;
		for (int c = 0; c < 26; c++) cur[c] = sum[1][c] * (i + 1) - cur[c];
		for (int c = 0; c < 26; c++) while (cur[c]--) cw[i][tot[i]++] = c;
	}
	for (int c = 0; c < 26; c++) cur[c] = sum[1][c];
	for (int i = 1; i <= m - ((n & 1) ^ 1); i++) cur[cw[i][0]]--, cur[cw[i][1]]--;
	for (int c = 0; c < 26; c++) while (cur[c]--)
		cw[m + (n & 1)][tot[m + (n & 1)]++] = c;
	if (n & 1) ans[m + 1] = cw[m + 1][0] + 'a';
	if (n == 1)
	{
		printf("! ");
		for (int i = 1; i <= n; i++) putchar(s[1]);
		return puts(""), 0;
	}
	printf("? %d %d
", 1, m); fflush(stdout);
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= m * (m + 1) / 2; i++)
	{
		scanf("%s", s + 1);
		int len = strlen(s + 1);
		for (int j = 1; j <= len; j++)
			sum[len][s[j] - 'a']++;
	}
	if (m > 1)
	{
		printf("? %d %d
", 2, m); fflush(stdout);
		for (int i = 1; i <= m * (m - 1) / 2; i++)
		{
			scanf("%s", s + 1);
			int len = strlen(s + 1);
			for (int j = 1; j <= len; j++)
				sum[len][s[j] - 'a']--;
		}
	}
	for (int i = m; i >= 1; i--)
	{
		for (int c = 0; c < 26; c++) sum[i][c] -= sum[i - 1][c];
		for (int c = 0; c < 26; c++) if (sum[i][c]) ans[i] = c + 'a';
		ans[n - i + 1] = ans[i] == cw[i][0] + 'a' ? cw[i][1] + 'a'
			: cw[i][0] + 'a';
	}
	printf("! ");
	for (int i = 1; i <= n; i++) putchar(ans[i]);
	return puts(""), 0;
}

Easy Version 1291F Hard Version 1290D Coffee Varieties

Statement

• 有一个长度为 (n) 的序列 (a) 和一个长度为 (k) 的队列 (S)，初始 (S) 为空

• 操作有两种：

• （1）给定一个 (i)，可以得到 (S) 里是否有和 (a_i) 相同的元素，并把 (a_i) 压入队列末尾，然后如果队列大小超过了 (k) 则弹队首

• （2）清空队列，可以使用不超过 (30000) 次

• (1le kle nle 1024) 且 (k) 和 (n) 都是 (2) 的整数次幂，保证 (frac{3n^2}{2k}le15000)

• 对于 Easy Version，要求操作（1）的次数不超过 (frac{2n^2}k)

• 对于 Hard Version，要求操作（1）的次数不超过 (frac{3n^2}{2k})（实际存在不超过 (frac{n^2}k) 的做法）

Solution

• 容易想到对于每个 (i)，求出 (is_i) 是否不存在 (j<i) 使得 (a_j=a_i)，这样答案就是 (sum is_i)

• 考虑分块。块大小为 (max(frac k2,1))，一开始 (is) 全部为 (1)

• 枚举两块 (j<i)，尝试用第 (j) 块的元素去更新第 (i) 块的 (is)，每次都要先清空队列

• 依次把第 (j) 块和第 (i) 块内所有元素都加进去，期间如果加入一个元素时返回了 Yes 就将其 (is) 变成 (0)

• 易得对于每个元素 (i)，(i) 的左边与之同一块和不同块的元素都能与之进行检查，能保证正确性

• 这样的总操作次数上限为 (n+inom{frac{2n}k}2frac k2=frac{2n^2}k)，可过 Easy Version

• 如何优化？考虑如果我们依次要用第 (1) 块去更新第 (2) 块的 (is)，第 (2) 块去更新第 (3) 块的 (is)，…，那么这实际上不用对于所有 (frac nk-1) 次更新都用 (k) 次操作来实现

• 因为把前两块内的元素都加入之后，队列内还留着第 (2) 块内的元素，清空再加回来是没有必要的，可以继续用它来更新第 (3) 块的 (is)。有可能第 (3) 块会被第 (1) 块部分更新，但这不影响答案（只需保证每种数最终只剩第一个 (is=1)）

• 于是考虑一个 (frac {2n}k) 阶有向图，对于 (i<j) 由 (i) 向 (j) 连边，如果能把这个图的所有边组成若干条路径，那么对每条路径跑一遍上面的过程，由于对一条路径进行一遍过程的复杂度为 (点数 imes frac k2)，所以可做到 ((inom{frac {2n}k}2+路径数) imesfrac k2) 的操作次数

• 但是很遗憾，这个有向图看上去没有什么路径条数比较少的拆分方案

• 于是我们放弃 (is) 数组原来的定义，考虑一个新的做法（暴力）：每次还是枚举 (i,j)，但是用第 (i) 块去更新第 (j) 块还是用 (j) 去更新 (i) 是任意的

• 可以证明如果所有的无序对 ((i,j)) 都被枚举到，那么每种数会且只会剩下一个 (is=1)，正确性得到保证，不过这里要注意：如果用第 (j) 块更新第 (i) 块，那么必须只能把这两块内原来 (is=1) 的元素加入，否则可能某个数值的 (is) 会被全部变成 (0)，正确性无法保证

• 于是有向图就变成了无向图。但这里有另一个问题：对一条路径跑一遍过程的时候，对于路径上第 (i) 个点，该块内的元素即使在这个过程中 (is) 从 (1) 变成了 (0)，还是会被加入这个队列，这样用第 (i) 个点更新第 (i+1) 个点时无法保证上面所说的正确性

• 但如果这是一条简单路径（不经过重复的点），就可以说明这个正确性一定能保证。而如果这条路径走了一个环，且存在一个 (x) 使得环上每个点对应块内都有一个值 (x) 的 (is=1)，那么走完一圈这些 (is) 都会变成 (0)，即无法保证正确性

• 于是我们必须保证这个 (frac{2n}k) 阶完全图拆出的每一条路径都是简单路径

• 随机化 DFS 可以得到比较优的方案，期望复杂度 (frac{1.2n^2}k)，可以通过 Hard Version（摘自原题解）

• 但对于一个 (n)（偶数）个点的无向完全图，将其拆分成 (frac n2) 条经过所有点的链有一个经典构造方法：

• 点从 (0) 开始标号，枚举 (0le i<frac n2)，走这条路径：(i ightarrow i-1 ightarrow i+1 ightarrow i-2 ightarrow i+2 ightarrowdots)（其中每个点的编号对 (n) 取模）

• 可以证明每条边都从某个方向被走了一遍

• 总操作次数不超过 ((inom{frac{2n}k}2+frac nk) imesfrac k2=frac{n^2}k)

• 此外，这题也可以设块大小为 (k)，使用 (3k) 的操作次数用一块更新另一块，就不需要进行图论转化，具体可以看 jiangly 的代码

Code

#include <bits/stdc++.h>

const int N = 1030;

bool query(int x)
{
	char c;
	printf("? %d
", x); fflush(stdout);
	while ((c = getchar()) != 'N' && c != 'Y');
	return c == 'Y';
}

int n, k, m, ans;
bool res[N];

int main()
{
	std::cin >> n >> k;
	if (k > 1) k /= 2; m = n / k;
	memset(res, true, sizeof(res));
	if (m == 1)
	{
		for (int i = 1; i <= n; i++) if (!query(i)) ans++;
		return printf("! %d
", ans), 0;
	}
	for (int i = 0; i < m / 2; i++)
	{
		puts("R"); fflush(stdout);
		for (int j = 0; j < m; j++)
		{
			int x = (i + (j & 1 ? -1 : 1) * (j + 1 >> 1) + m) % m;
			for (int s = 1; s <= k; s++)
				if (res[x * k + s] && query(x * k + s)) res[x * k + s] = 0;
		}
	}
	for (int i = 1; i <= n; i++) ans += res[i];
	return printf("! %d
", ans), 0;
}

1299E So Mean Link

Statement

• 给定一个 (n)（偶数）元排列 (p)

• 每次询问给定一个下标集合，可以得到 (p) 该下标集合上所有数的平均数是不是整数

• 还原这个排列

• 由于 ({p_1,p_2,dots,p_n}) 和 ({n+1-p_1,n+1-p_2,dots,n+1-p_n}) 无法区分，故这题保证 (p_1lefrac n2)

• (2le nle 800)

• 操作次数限制为 (18n)

Solution

• 这是一道数学题，比较有意思

• 先询问所有大小为 (n-1) 的集合

• 由于 (frac{n(n+1)}2=frac n2(n-1)+nequiv 1(mod n-1))

• 所以询问 ([n]-{i}) 出来的结果为 Yes 当且仅当 (p_i=1) 或 (n)

• 由于 ({p_1,p_2,dots,p_n}) 和 ({n+1-p_1,n+1-p_2,dots,n+1-p_n}) 无法区分，所以对于 ([n]-{i}) 询问出来为 Yes 的两个位置，哪个是 (1) 哪个是 (n) 可以随便定，最后算出答案如果 (p_1>frac n2) 则把所有 (p_i) 变成 (n+1-p_i) 即可

• 类似地也可以找出 (2) 和 (n-1) 的位置

• 即在全集中去掉 (1) 和 (n) 所在的位置之后，枚举 (i) 表示再去掉第 (i) 个位置并查询该集合，如果查出来是 Yes 则该位置为 (2) 或 (n-1)，同样地会有恰好 (2) 个这样的位置

• 但是这时候由于 (1) 和 (n) 已经定下来了，所以这时 (2) 和 (n-1) 的位置不能随便确定

• 所以在此之前要先做一些处理

• 可以询问出 (1) 和 (n) 定下来了之后每个位置上数的奇偶性：把每个未定的位置和 (1) 所在的位置放到一起组成一个大小为 (2) 的集合进行查询，Yes 为奇，No 为偶

• 有了每个位置的奇偶性，由于 (2) 和 (n-1) 的奇偶性不相同，它们的位置可以确定下来

• 照这样可以询问出 (3,n-2,4,n-3,dots) 的位置，进行 (frac n2) 次即可确定整个排列，但这样的复杂度是 (O(n^2)) 的，无法通过此题

• 考虑只对 (nle 8) 进行以上暴力，对于 (n>8)，只用其求出 (1,2,3,4,n-3,n-2,n-1,n) 这 (8) 个数所在的位置

• 对于剩下位置上的数，考虑中国剩余定理 CRT：取模数 (3,5,7,8)，把剩下的每个位置上的数对这 (4) 个模数取模后的结果求出来，再用 CRT 即可还原排列

• 以下设 (q_i) 表示询问数 (i) 所在的位置

• 求第 (i) 个数模 (3) 的结果：

• 询问 ({q_1,q_2,i})，如果为 Yes 则为 (0)；否则再询问 ({q_2,q_3,i})，如果为 Yes 则为 (1)；否则为 (2)

• 这样看上去是 (2n) 的，但存在 (frac 13) 的数只需询问一次，故操作次数 (frac 53n)

• 模 (5)：

• 依次询问 ({q_1,q_2,q_3,q_n,i})，({q_1,q_2,q_3,q_{n-1},i})，({q_1,q_2,q_3,q_{n-2},i})，({q_1,q_2,q_3,q_{n-3},i})，根据哪个询问结果为 Yes 来确定答案

• 操作数 ((1+2+3) imesfrac n5+4 imesfrac 25n=frac{14}5n)

• 模 (7)：

• ({q_1,q_2,q_3,q_{n-3},q_{n-2},q_{n-1},i}{q_1,q_2,q_4,q_{n-3},q_{n-2},q_{n-1},i})

• ({q_1,q_2,q_4,q_{n-3},q_{n-2},q_n,i}{q_1,q_3,q_4,q_{n-3},q_{n-2},q_n,i})

• ({q_1,q_3,q_4,q_{n-3},q_{n-1},q_n,i}{q_2,q_3,q_4,q_{n-3},q_{n-1},q_n,i})

• 可以证明上面 (6) 个集合中，前 (6) 个下标对应数的和在模 (7) 意义下两两不同

• 操作数 ((1+2+3+4+5) imesfrac n7+6 imesfrac 27n=frac{27}7n)

• 模 (8)：

• 利用已经得到的 (8) 个数的位置，用前面类似的做法无法直接得到模 (8) 的结果

• 由于 (8=2^3)，先考虑模 (4) 怎么求

• 由于之前已经知道了每个数的奇偶性，故设原来模 (2) 为 (x)，我们只需求出模 (4) 是 (x) 还是 (x+2)

• 可以用一次询问解决，奇数则询问 ({q_2,q_3,q_4,i})，偶数 ({q_1,q_2,q_3,i})，如果返回 Yes 就为 (x+2)，否则为 (x)

• 这样我们得到了模 (4) 的结果，模 (8) 也一样，模 (4) 为 (x) 则求出模 (8) 是 (x) 还是 (x+4)

• 同样可以用一次询问解决，考虑 ({q_1,q_2,q_3,q_4,q_{n-3},q_{n-2},q_{n-1},q_n}) 这个下标集合

• 这个下标集合对应数的和必然是 (8) 的倍数，故把 (q_{(x-1)mod 4+1}) 替换成 (i) 之后这个下标集合对应数的和一定是 (4) 的倍数

• 查询替换后的集合即可

• 操作数 (2n)

• 总操作次数为 ((4+1+frac 53+frac{14}5+frac{27}7+2)n=15.32n)，可以通过此题

Code

• 注意询问最好使用数组存下来，否则对拍和调试会十分麻烦

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline void Swap(T &a, T &b) {T t = a; a = b; b = t;}

const int N = 805;

int n, ans[N], pos[N];
bool vis[N], odd[N];

void jjd(int T)
{
	int x; bool vi = 0;
	for (int i = 1; i <= n; i++) if (!vis[i])
	{
		printf("? %d ", n - (T - 1) * 2 - 1);
		for (int j = 1; j <= n; j++) if (!vis[j] && i != j)
			printf("%d ", j);
		puts(""); fflush(stdout);
		if (read(x), x)
		{
			if (!vi) vi = 1, ans[pos[T] = i] = T;
			else ans[pos[n - T + 1] = i] = n - T + 1;
		}
	}
	vis[pos[T]] = vis[pos[n - T + 1]] = 1;
}

void output()
{
	if (ans[1] > n / 2) for (int i = 1; i <= n; i++)
		ans[i] = n + 1 - ans[i];
	printf("! ");
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	puts("");
}

int q3(int u)
{
	int x;
	printf("? 3 %d %d %d
", pos[1], pos[2], u); fflush(stdout);
	if (read(x), x) return 0;
	printf("? 3 %d %d %d
", pos[2], pos[3], u); fflush(stdout);
	if (read(x), x) return 1;
	return 2;
}

int q5(int u)
{
	int x, mi = (1019 - n) % 5;
	printf("? 5 %d %d %d %d %d
", pos[1], pos[2], pos[3], pos[n], u);
	fflush(stdout); if (read(x), x) return mi;
	printf("? 5 %d %d %d %d %d
", pos[1], pos[2], pos[3], pos[n - 1], u);
	fflush(stdout); if (read(x), x) return (mi + 1) % 5;
	printf("? 5 %d %d %d %d %d
", pos[1], pos[2], pos[3], pos[n - 2], u);
	fflush(stdout); if (read(x), x) return (mi + 2) % 5;
	printf("? 5 %d %d %d %d %d
", pos[1], pos[2], pos[3], pos[n - 3], u);
	fflush(stdout); if (read(x), x) return (mi + 3) % 5;
	return (mi + 4) % 5;
}

int orz(int x, int y, int u)
{
	printf("? 7 "); int tmp;
	for (int i = 1; i <= 4; i++) if (i != x) printf("%d ", pos[i]);
	for (int i = n - 3; i <= n; i++) if (i != y) printf("%d ", pos[i]);
	printf("%d
", u); fflush(stdout);
	return read(tmp), tmp;
}

int q7(int u)
{
	int x, mi = (3500 - 3 * n) % 7;
	if (orz(4, n, u)) return mi;
	if (orz(3, n, u)) return (mi + 6) % 7;
	if (orz(3, n - 1, u)) return (mi + 5) % 7;
	if (orz(2, n - 1, u)) return (mi + 4) % 7;
	if (orz(2, n - 2, u)) return (mi + 3) % 7;
	if (orz(1, n - 2, u)) return (mi + 2) % 7;
	return (mi + 1) % 7;
}

int q8(int u)
{
	int res = odd[u], x;
	if (res) printf("? 4 %d %d %d %d
", pos[2], pos[3], pos[4], u);
	else printf("? 4 %d %d %d %d
", pos[1], pos[2], pos[3], u);
	fflush(stdout); if (read(x), x) res += 2;
	printf("? 8 ");
	for (int i = 1; i <= 4; i++) if (i % 4 != res) printf("%d ", pos[i]);
	for (int i = 1; i <= 4; i++) printf("%d ", pos[n - i + 1]);
	printf("%d
", u); fflush(stdout); if (!res) res = 4;
	if (read(x), x) res += 4;
	return res % 8;
}

int main()
{
	int x;
	read(n);
	jjd(1);
	for (int i = 1; i <= n; i++) if (!vis[i])
	{
		printf("? 2 %d %d
", pos[1], i); fflush(stdout);
		if (read(x), x) odd[i] = 1;
	}
	for (int i = 2; i <= 4 && i <= n / 2; i++)
	{
		jjd(i);
		if (odd[pos[i]] ^ (i & 1)) Swap(pos[i], pos[n - i + 1]),
			Swap(ans[pos[i]], ans[pos[n - i + 1]]);
	}
	if (n <= 8) return output(), 0;
	for (int i = 1; i <= n; i++) if (!vis[i])
		ans[i] = (q3(i) * 280 + q5(i) * 336 + q7(i) * 120 + q8(i) * 105) % 840;
	return output(), 0;
}