<span>Codeforces #685 (div 2) A - E1 题解</span>

A - Subtract or Divide

题目大意

给你一个数 \(n\) ，每次可以将这个数除去一个他的因子（不能是他本身）或减一，问把这个数变成 \(1\) 的最少操作数量。

解题思路

这题比较降智，其实有一个很简单的贪心思路。

如果 \(n\) 是偶数，那么就可以直接一次把这个数除成 \(2\)，再减一，共 \(2\) 次操作。

如果 \(n\) 是奇数，那么可以先减一变成偶数，再仿照偶数的操作，共 \(3\) 次操作。

显然这样一定会使操作次数最少，不过要特判下 \(1,2,3\) 的情况。

Code

int t,n;

signed main()
{
	t=read();
	while(t--)
	{
		n=read();
		if(n==1) printf("0\n");
		else if(n==2) printf("1\n");
		else if(n==3) printf("2\n");
		else printf("%lld\n",(n&1)+2);
	}
	return 0;
}

B - Non-Substring Subsequence

题目大意

给你一个 \(01\) 字符串，每次询问一个区间，问在这个字符串是否有和这个区间相等的子序列（子序列不能是一个连续的字符串）

解题思路

对于一个区间，显然如果 \(s_1 \sim s_{l-1}\) 中存在 \(s_l\) 或 \(s_{r+1} \sim s_n\) 中存在 \(s_r\)，那么显然存在满足条件的子序列。

<button class="accordion">证明

判断是否满足性质可以前缀和维护。

Code

const int N=105;
int t,n,q,pre[N][2],suc[N][2];
char s[N];

signed main()
{
	t=read();
	while(t--)
	{
		n=read();q=read();
		scanf("%s",s+1);
		memset(pre,0,sizeof(pre));
		memset(suc,0,sizeof(suc));
		for(int i=1;i<=n;++i)
		{
			pre[i][0]=pre[i-1][0]+(s[i]=='0');
			pre[i][1]=pre[i-1][1]+(s[i]=='1');
		}
		for(int i=n;i>=1;--i)
		{
			suc[i][0]=suc[i+1][0]+(s[i]=='0');
			suc[i][1]=suc[i+1][1]+(s[i]=='1');
		}
		while(q--)
		{
			int l=read(),r=read(),fl=0;
			if(pre[l-1][s[l]-'0']!=0) fl=1;
			if(suc[r+1][s[r]-'0']!=0) fl=1;
			printf("%s\n",fl?"YES":"NO");
		}
	}
	return 0;
}

C - String Equality

题目大意

给定两个字符串 \(A\) 和 \(B\)，每次可以交换 \(A\) 中的两个字符或把 \(A\) 中的连续 \(k\) 个字符全部变为下一个（\(a\rightarrow b\),\(y\rightarrow z\),\(z\) 不变）

问能否将 \(A\) 变成 \(B\)

解题思路

因为可以无限交换，所以所有位置要求全都无效。

所以第二个操作可以转化为将 \(A\) 中的任意 \(k\) 个相同字符都变为下一个，目标也变为让 \(A\) 所含的字符与 \(B\) 所含的字符一样。

因为字符只能从小到大变，所以可以从 \(a\) 开始，枚举 \(B\) 中有多少个该字符，如果 \(A\) 中的不够就肯定不行，如果够了多出来的就 \(k\) 个 \(k\) 个全部变成下一个字符，如果有字符剩余，那么同样不行。

Code

const int N=1e6+5;
int t,n,k,fl,s1[30],s2[30];
char s[N],e[N];

signed main()
{
	t=read();
	while(t--)
	{
		n=read();k=read();
		scanf("%s",s+1);
		scanf("%s",e+1);
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		for(int i=1;i<=n;++i)
			s1[s[i]-'a'+1]++,s2[e[i]-'a'+1]++;
		fl=1;
		for(int i=1;i<=26;++i)
		{
			if(s1[i]<s2[i]) QWQ
			s1[i]-=s2[i];
			if(i!=26)
			{
				s1[i+1]+=s1[i]/k*k;
				s1[i]%=k;
			}
			if(s1[i]!=0) QWQ;
		}
		if(fl) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

D - Circle Game

题目大意

两个人轮流操作，从原点开始，每次操作使 \(x\) 坐标或 \(y\) 坐标加 \(k\)，如果操作后与源点的欧几里得距离大于 \(d\) ，那么操作的这个人就输了。

两人都以最优策略，问谁会赢

解题思路

博弈论小白表示这么简单的博弈论也不会/kk

对于一个 \((x,y)\) ，如果它是必败点，那么 \((x-k,y),(x,y-k)\) 就是必胜点。

因此 \((x-k,y-k)\) 同是必败点。

所以如果 \((0,0)\) 是必败点，那么一定有 \((p \times x,p \times y)\) 是必败点。

随便枚举判断下就行了。

Code

int t,d,k,s1,s2,fl;

signed main()
{
	t=read();
	while(t--)
	{
		d=read();k=read();
		s1=0,s2=0,fl=0;
		for(int i=0;i*i*2<=d*d;i+=k)
		{
			if((i+k)*(i+k)+i*i>d*d)
				fl=1;
		}
		if(fl) printf("Utkarsh\n");
		else printf("Ashish\n");
	}                     
	return 0;
}

E1 - Bitwise Queries (Easy Version)

题目大意

有一个 \(n\) 个数的序列，每次可以询问任意两个数的 与 或 异或 的值，最多可以询问 \(n+2\) 次，将这个序列还原出来。

解题思路

如果知道了其中一个数的值，那么其他所有数都可以通过询问 \(n-1\) 次与它的异或得出，所以关键在于怎么求出一个确定的值。

假设有三个数 \(a,b,c\)，那么可以感性理解：

\(a \land b\) , \(b \land c\) , \(a \land c\) 就是二进制下两个数同是 \(1\) 的部分。

\(a \otimes b\) , \(a \otimes c\) 就是两个数二进制下两个数不同的部分。

\((a \land b) \lor (a \land c)\) 就是 \(a\) 与 \(b\) 或 \(c\) 共有部分，且肯定包含在 \(a\) 的二进制中。

\((a \otimes b) \lor (a \otimes c)\) 就是 \(a\) 与 \(b\) 和 \(c\) 不同部分的并，显然它也可以表示为 \(b \land c\) 和 \(a\) 中 \(b,c\) 都没有的部分 的并。

\(((a \otimes b) \lor (a \otimes c)) \otimes (b \land c)\) 就是 \(a\) 中 \(b,c\) 都没有的部分。

\(((a \land b) \lor (a \land c)) \lor (((a \otimes b) \lor (a \otimes c)) \otimes (b \land c))\) 就是 \(a\) 与 \(b\) 或 \(c\) 的共有部分 和 \(a\) 中 \(b,c\) 都没有的部分的并，也就是 \(a\)。

这样只要查询 \(a \land b\) , \(b \land c\) , \(a \land c\) , \(a \otimes b\) , \(a \otimes c\) 共 \(5\) 次就能知道其中的一个数，又知道这个数与另外两个数的异或，所以也能知道另外两个数，即知道了 \(3\) 个数。

那么剩下的 \(n-3\) 个数只要查询 \(n-3\) 次与 \(a\) 的异或就能求出来。

共 \(5+n-3=n+2\) 次查询。

Code

const int N=1e5+5;
int n,a[N];

signed main()
{
	n=read();
	printf("AND 1 2\n");fls;
	int p1=read();
	printf("AND 1 3\n");fls;
	int p2=read();
	printf("XOR 1 2\n");fls;
	int p3=read();
	printf("XOR 1 3\n");fls;
	int p4=read();
	printf("AND 2 3\n");fls;
	int p5=read();
	a[1]=((p1|p2)|((p3&p4)^p5));
	a[2]=(a[1]^p3);
	a[3]=(a[1]^p4);
	for(int i=4;i<=n;++i)
	{
		printf("XOR 1 %lld\n",i);fls;
		int tmp=read();
		a[i]=(a[1]^tmp);
	}
	fls;
	printf("! ");
	for(int i=1;i<=n;++i)
	{
		printf("%lld",a[i]);
		if(i!=n) printf(" ");
	}
	return 0;
}