自动搬运

查看原文

来自洛谷，原作者为

	liangbob 我们生活在大地上，但我们的梦想超越天空。

搬运于2025-08-24 23:10:02，当前版本为作者最后更新于2024-11-23 10:35:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢出题人 Tian36309 写下了此篇题解的初版，并对修改版提出了宝贵的修改意见。

[IAMOI R1] 智力检测 题解

定义 I 定义“用 $v$ 取 $a_u$”代表对 $u_i=u$，$v_i=v$ 进行题目所述的操作

定义 II 定义“$a_u$ 被取”表示对于某个 $v$，用 $v$ 取了 $a_u$

命题 I 取数时，$a_u$ 不可能被重复取。

• 证明显然，反证法。考虑到如果取重复的 $a_u$ 会取到 $-\infty$，你后面无论怎么取，都无法取回一个非负数。同时题目保证 $x$ 是个非负数，矛盾，所以不能重复取。

命题 II 如果 $x < 2^{k-1}$ 或者 $x \ge 2^k$，那么本次询问无解。

• 根据命题 I，可以知道 $a_u$ 不能重复取，这意味着每个操作的 $a_u$ 和 $a_{u-1}$ 均非负，也就是说，经过多次操作之后，$a_k$ 必然只增不减，那么 $x<2^{k-1}$ 自然也就无解了。

• 继续根据命题 I，可以继续知道 $a_u$ 不能重复取，注意到最极限的情况显然是通过反复操作把 $2^0$，$2^1$，$2^2$，……，$2^k$ 取一次，也就是说 $a_k \le 2^k-1$，这显然不到 $2^k$，于是 $x\ge 2^k$ 无解。

以下的分析令 $x \gets x - 2^{k-1}$。（这一位二进制数不用取，因此不考虑）

命题 III 可以通过若干次操作使 $a_k = x$，当且仅当如果 $x$ 二进制下不包含连续奇数个 $1$。

• 由于 $a$ 数组的特殊性质，我们把 $a$ 数组转换成二进制后发现，第一次取 $a_u$ 和 $a_{u-1}$ 就相当于把 $a_v$ 的第 $u$ 位和第 $u-1$ 位改为 $1$，而下一次操作中选的数如果是 $a_v$ 则这次操作后那一个数的第 $u-1,u,v,v-1$ 位都将变为 $1$。

• 由于 $u_i<v_i<v_{i-1}$，因此上述性质成立。

• 由于每次操作都是将两位改为 $1$，因此如果 $x$ 二进制下包含连续奇数个 $1$，那么必然无法操作得到。

那么我们就有了第一个思路：

• 对于每一次询问，将 $x$ 进行二进制拆分，如果发现存在连续奇数个 $1$ 输出 $0$，否则输出 $1$。

• 单次询问 $O(\log x)$，常数比较好的话可以获得 $90$ 分。（卡一卡没准可以拿满分）

命题 IV 对于每一个合法的答案（即不出现连续奇数个 $1$，后同），其一定是 $3$ 的倍数。

证明平凡，因为相邻两个 $1$ 可以理解为 $x+2x$，而这个数很明显是 $3$ 的倍数。

命题 V 对于每一个合法的答案，用它除以 $3$ 后进行二进制拆分，一定不会出现连续的 $1$。

• 观察到，除以 $3$ 相当于在除以 $(11)_2$，试一下就会发现，二进制下连续偶数个 $1$ 除以 $(11)_2$ 就等于 $(1010101\ldots)_2$。
• 而若一个不包含连续 $1$ 的二进制数乘 $3$，结果中一定只包含连续的偶数个 $1$（相当于将其右移一位再相加）。
• 综上，得证。

命题 VI 符合是 $3$ 的倍数和除以 $3$ 后进行二进制拆分，不会出现连续的 $1$ 的数必然是合法的答案。

• 显然，所有不含连续的 $1$ 的二进制数乘三都是合法答案。

那么，我们只需要判断如下两个条件即可：

• $x$ 是 $3$ 的倍数
• $x$ 除以 $3$ 后二进制下不含有连续的 $1$。

对于第二个条件，可以通过 $\lfloor\dfrac{x}{3}\rfloor$ 按位与 $\lfloor\dfrac{2x}{3}\rfloor$ 来判断。显然如果没有连续的 $1$，上述式子的结果是 $0$。

时间复杂度 $O(T)$。

#include<bits/stdc++.h>
using namespace std;
long long T,k,sum,mi[100];
inline long long read()
{
	char c=getchar();long long x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}
int main(){
	T = read();
	mi[1] = 1;
	for(int i=2;i<=62;i++)mi[i] = mi[i-1]*2;
	while(T--){
		k = read();
		sum = read();
		if(sum >= mi[k+1] or sum < mi[k]){
			printf("0");
			continue;
		}
		sum -= mi[k];
		if(sum % 3 == 0 and (((sum/3) & (sum/3*2)) == 0))printf("1");
		else printf("0");
	}
	return 0;
}