这些都是近来我 VP CF 遇到的奇奇妙妙的题。

构造

这一类题通常需要大胆猜结论/经验积累。

CF1514B AND 0, Sum Big

首先因为与运算和为 $0$，所以每一位上都至少有一个数这一位为 $0$。

然后因为元素的和要尽量大，所以肯定不存在两个数同一位为 $0$。

那么每一位都需要让 $a_{1\sim n}$ 中的恰好一个在这一位为 $0$，所以答案即为 $n^k$。

CF1630A And Matching

首先来看三个性质：

• $i\&(n-1-i)=0$，因为 $i$ 和 $n-1-i$ 的二进制是“错开”的；
• $i\&(n-1)=i$，因为 $n-1$ 的二进制全是 $1$；
• $i\&0=0$，显然。

接下来分类讨论：

• 若 $k\not=n-1$：

可以先构造出 $k\&(n-1)=k$ 和 $(n-1-k)\&0=0$，然后对于每个 $1\le i\le n-1$ 且 $i\not=k$ 且 $i\not=n-1-k$ 的 $i$ 构造出 $i\&(n-1-i)=0$。

注意特判 $k=0$，这时不需要构造 $(n-1-k)\&0=0$。

• 若 $k=n-1$

这时容易发现让其中一对与为 $k$ 的办法行不通了，所以我们要另辟蹊径，让两对的与加起来为 $k$。

显然 $(n-1)\&(n-2)=n-2$，$1\&(n-3)=1$，那么先构造这两对即可。

接下来发现 $n-1-(n-1)=0$，$n-1-(n-3)=2$，$n-1-(n-2)=1$ 也就是说 $0$ 和 $2$ 不能组成 $i\&(n-1-i)=0$ 了，那么让它们单独组，构造 $0\&2=0$。

接下来构造 $i\&(n-1-i)=0$ 即可。

注意到若 $n\le 4$ 则 $n-1$、$n-2$、$n-3$、$0$、$1$、$2$ 会重叠，这时是无解的。

CF1659D Reverse Sort Sum

不难发现，由于每个 $1$ 对 $\sum C$ 都有且仅有 $n$ 的贡献，所以 $A$ 中 $1$ 的个数即为 $\dfrac{\sum C}{n}$。

接下来，我们很容易发现 $A_n=1$ 当且仅当 $C_n=n$，因为 $A_n=1$ 时 $B_{i,n}$ 一定为 $1$。

有了这个性质的启示，不难想到可以通过减掉 $B_n$ 对 $C$ 的贡献来实现缩小问题的规模，令 $n$ 变为 $n-1$。实际上实现起来也并不难，因为我们已经取得了 $A$ 中 $1$ 的个数 $m$，$B_n$ 一定只会对 $[n-m+1,n]$ 有 $1$ 的贡献，那么用差分来实现快速区间减法即可。

CF1658D2 388535 (Hard Version)

首先肯定有一个 $a_i$ 满足 $a_i\operatorname{xor} l=x$，即它本来是 $l$。那么我们枚举每个 $a_i$，判断它原来是不是 $l$ 即可。

接下来思考判断的方法。不难发现，由于 $a_i$ 原来是不重复的一个排列，所以异或后的 $a_i$ 也是不重复的一个排列，所以只要 $a_i$ 满足 $r=\max\operatorname{xor}(a_i\operatorname{xor} l)$ 就说明 $a_i$ 原来是 $l$。

这个东西用 trie 维护即可。

CF1592C Bakry and Partitioning

从每一部分的异或和相同出发，设分割后每一部分的异或和都为 $k$，所有 $a_i$ 的异或和为 $sum$。不难发现要么 $sum=0$ 即最后是偶数个 $k$ 异或起来，要么 $sum=k$ 即最后是奇数个 $k$ 异或起来。

• 若 $sum=0$，我们割断任意一条边都一定合法。因为割出来的两部分只有异或和相同它们异或起来的结果 $sum$ 才为 $0$。

• 若 $sum=k$，那么割断两条边，分割出三个异或和为 $k$ 的连通块显然是最优的。所以考虑找到两个异或和都为 $k$ 的连通块，剩下那一块异或和就自然为 $k$。因为肯定有一个满足条件的连通块是一棵子树，减掉它的贡献后又会有一个满足条件的连通块是一棵子树，所以跑一次 $dfs$，求出每个节点子树去掉异或和为的 $k$ 子树后的异或和 $dp_u=\operatorname{xor}_{v\text{ 是 }u\text{ 的儿子}}[dp_v\not=k]dp_v$ 即可。最后若 $\sum\limits_{u} [dp_u=k]\ge2$ 就说明有解。

部分代码如下：

void dfs(int u,int fa,long long val)
{
	dp[u]=a[u];
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)
		{
			continue;
		}
		dfs(v,u,val);
		if(dp[v]!=val)
		{
			dp[u]^=dp[v];
		}
	}
}

inline void slove()
{
	esum=0;
	scanf("%d%d",&n,&k);
	long long sm=0;
	for(int i=1;i<=n;i++)
	{
		h[i]=0;
		dp[i]=0;
		scanf("%lld",&a[i]);
		sm^=a[i];
	}
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	if(sm==0)
	{
		puts("YES");
		return;
	}
	if(k==2)
	{
		puts("NO");
		return;
	}
	dfs(1,0,sm);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cnt+=dp[i]==sm;
	}
	puts(cnt>=2?"YES":"NO");
}

交互

这一类题通常需要程序和交互库互动，思维难度较高。

CF1503B 3-Coloring

用 $1$ 和 $2$ 交替着填，实在不行用 $3$ 即可。

CF1592D Hemose in ICPC

首先由于 $\gcd$ 里的数越多，结果就越小，所以最大的 $Dist$ 一定是一条边的边权。

那么我们先询问所有节点求出最大的 $Dist=val$，然后二分所有的边。

考虑如何二分，显然需要把树“拍扁”，用类似 $dfs$ 序的东西来解决。具体的，考虑节点 $u$ 和它的所有儿子 ${v_i}$，显然 $u\to v_i$ 都有一条边，那么先往序列里加入 $u$，再在 $dfs$ 完每个 $v_i$ 后都加入 $u$ 即可。

CF1634D Finding Zero

考虑从 $4$ 个可能的下标 $b_1,b_2,b_3,b_4$ 中去掉一些不可能的下标。

显然一次询问的结果是三个数的极差。记 $q_1,q_2,q_3,q_4$ 为询问四个下标里分别除去 $b_1,b_2,b_3,b_4$ 的结果，即 $q_1$ 为询问 $b_2,b_3,b_4$ 的结果。那么显然 $m=\max(q_1,q_2,q_3,q_4)$ 就是 $a_{b_1},a_{b_2},a_{b_3},a_{b_4}$ 的极差。

不难发现，若 $q_i=m$，那么 $b_i$ 一定不可能为 $0$。因为去掉 $0$ 后三个数的极差一定不是这四个数的极差。

这样每排除一次至少可以去掉至少两个不可能的下标，总共需要的次数上限就是 $\dfrac{4n}{2}=2n$，足以通过此题。

特别的，若剩下三个下标未排除，拿一个排除过的下标和它们组队即可。

杂题

最后给两道匕匕车交女少白勺杂题。

CF1632D New Year Concert

不难发现，当区间 $[l,r]$ 的右端点 $r$ 固定不动，左端点 $l$ 减小时，$\gcd(a_l,a_{l+1},a_{l+2},\dots,a_r)$ 是单调不增的，而 $r-l+1$ 则是单调递增的，这造成了它们最多只会有一个交点。也就是说，对于一个固定的 $r$，最多有一个 $l$ 满足 $\gcd(a_l,a_{l+1},a_{l+2},\dots,a_r)=r-l+1$。

那么用倍增实现 $O(n\log n\log v)$ 预处理 $O(1)$ 查询 $\gcd$，然后枚举 $r$，每次找满足条件的 $l$，如果有那么答案加一并且把 $a_l$ 改为 $1$ 即可。

部分代码如下：

int ans=0,lb=1;
for(int i=1;i<=n;i++)
{
	while(lb<i&&que(lb,i)<i-lb+1)
	{
		lb++;
	}
	if(que(lb,i)==i-lb+1)
	{
		ans++;
		lb=i+1;
	}
	printf("%d ",ans);
}
printf("\n");

CF1594D The Number of Imposters

并查集拆点模板题，建议先看一下我的博客。

每个人拆两个点 $i$ 和 $i+n$，分别表示这个人是好人和坏人的情况，统计答案的时候对每个集合的“帮主”是好人/坏人的情况下的好人的数量取最大值，加起来即可。

CF1685B Linguistics

贪心。

题意显然可以转化为把 $a$ 个 $\texttt{A}$、$b$ 个 $\texttt{B}$、$c$ 个 $\texttt{A}\texttt{B}$ 和 $d$ 个 $\texttt{B}\texttt{A}$ 不重叠地放进字符串 $s$ 中，使得对应位相等。

首先若放的 $\texttt{\texttt{A}}$、$\texttt{B}$ 的个数和 $s$ 中 $\texttt{A}$、$\texttt{B}$ 的个数不同，那么就是不行的。接下来考虑让所有放单个 $\texttt{A}$ 和 $\texttt{B}$ 的操作都挪到最后进行，那么问题就转化为判断能否把 $c$ 个 $\texttt{A}\texttt{B}$ 和 $d$ 个 $\texttt{B}\texttt{A}$ 都放进 $s$ 里面。

考虑一段形如 $\texttt{A}\texttt{B}\texttt{A}\texttt{B}\texttt{A}\texttt{B}\texttt{A}\texttt{B}$ 这样 $\texttt{A}\texttt{B}$ 相间的极长子串，设它的长度为 $cnt$，那么分类讨论：

• 若 $cnt$ 是奇数，那么这一段可以放 $\lfloor\frac{cnt}{2}\rfloor$ 个 $\texttt{A}\texttt{B}$ 或 $\texttt{B}\texttt{A}$；
• 若 $cnt$ 是偶数，那么：
  • 若这一段以 $\texttt{B}$ 结尾，即形如 $\texttt{A}\texttt{B}\texttt{A}\texttt{B}$，那么可以放 $\lfloor\frac{cnt}{2}\rfloor-1$ 个 $\texttt{A}\texttt{B}$ 或 $\texttt{B}\texttt{A}$，或者可以放 $\lfloor\frac{cnt}{2}\rfloor$ 个 $\texttt{A}\texttt{B}$；
  • 若这一段以 $\texttt{A}$ 结尾，即形如 $\texttt{B}\texttt{A}\texttt{B}\texttt{A}$，那么可以放 $\lfloor\frac{cnt}{2}\rfloor-1$ 个 $\texttt{A}\texttt{B}$ 或 $\texttt{B}\texttt{A}$，或者可以放 $\lfloor\frac{cnt}{2}\rfloor$ 个 $\texttt{B}\texttt{A}$；

不难发现，当 $cnt$ 为奇数时这一段对 $\texttt{A}\texttt{B}$ 和 $\texttt{B}\texttt{A}$ 都是公平的，即它们放的上限都是 $\lfloor\frac{cnt}{2}\rfloor$，并且对放多少个 $\texttt{A}\texttt{B}$ 和多少个 $\texttt{B}\texttt{A}$ 没有限制，只要它们数量加起来不超过 $\lfloor\frac{cnt}{2}\rfloor$ 就可以了。

所以可以令 $bot=\sum\limits_{cnt\operatorname{mod}2=1}\lfloor\frac{cnt}{2}\rfloor$ 即奇数段最多可以放的 $\texttt{A}\texttt{B}$ 和 $\texttt{B}\texttt{A}$ 的数量。

若 $cnt$ 为偶数，那么这一段对 $\texttt{A}\texttt{B}$ 和 $\texttt{B}\texttt{A}$ 是不公平的，即它们放的上限一个多，一个少。为了减少位置的浪费，不妨先钦定这一段都放上限多的那种字符串，再用两个数组 $vala$ 和 $valb$ 存偏心 $\texttt{A}\texttt{B}$ 或者 $\texttt{B}\texttt{A}$ 即能放更多 $\texttt{A}\texttt{B}$ 或 $\texttt{B}\texttt{A}$ 的偶数段中两种字符串放置的上限。

最后若每一段偶数段都放上限多的字符串时 $c$ 或 $d$ 还是大于 $0$，那么就让偏心另一种字符串的偶数段分一些位置放这种字符串即可。不难发现由于没分之前偶数段总共能放 $\lfloor\frac{cnt}{2}\rfloor$ 个字符串，分了之后只能放 $\lfloor\frac{cnt}{2}\rfloor-1$ 个，所以分的段数肯定是越少越好。那么按段的长度从大到小分即可。

代码如下：

// Problem: D. Linguistics
// Contest: Codeforces Round #794 (Div. 2)
// URL: https://codeforces.com/contest/1686/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

const int S=1919810;

struct node
{
	int x,y;
}vala[S],valb[S];

int n,a,b,c,d;
char str[S];

inline bool cmp(node x,node y)
{
	return x.y>y.y;
}

inline void slove()
{
	cin>>a>>b>>c>>d>>(str+1);
	n=strlen(str+1);
	int cnta=0,cntb=0;
	for(int i=1;i<=n;i++)
	{
		cnta+=str[i]=='A';
		cntb+=str[i]=='B';
	}
	if(cnta-c-d!=a||cntb-c-d!=b) // A 或 B 的数量不符合的情况
	{
		cout<<"NO"<<endl;
		return;
	}
	int m1=0,m2=0,bot=0;
	str[n+1]=str[n];
	for(int i=1,cnt=0;i<=n+1;i++)
	{
		if(str[i]!=str[i-1])
		{
			cnt++;
		}
		else
		{
			if(cnt>1)
			{
				if(cnt&1) // 公平的奇数段
				{
					bot+=cnt/2;
				}
				else
				{
					if(str[i-1]=='B')
					{
						vala[++m1]=(node){cnt/2,cnt/2-1}; // 偏心 AB
						c-=cnt/2;
					}
					else
					{
						valb[++m2]=(node){cnt/2,cnt/2-1}; // 偏心 BA
						d-=cnt/2;
					}
				}
			}
			cnt=1;
		}
	}
	if(d>0)
	{
		sort(vala+1,vala+m1+1,cmp);
		for(int i=1;i<=m1;i++)
		{
			if(c+vala[i].x<=0)
			{
				c+=vala[i].x;
				d-=vala[i].y;
			}
			else
			{
				int lft=vala[i].x+c;
				if(lft>vala[i].y)
				{
					continue;
				}
				d-=vala[i].y-lft;
				c=0;
			}
		}
	}
	else
	{
		sort(valb+1,valb+m2+1,cmp);
		for(int i=1;i<=m2;i++)
		{
			if(d+valb[i].x<=0)
			{
				d+=valb[i].x;
				c-=valb[i].y;
			}
			else
			{
				int lft=valb[i].x+d;
				if(lft>valb[i].y)
				{
					continue;
				}
				c-=valb[i].y-lft;
				d=0;
			}
		}
	}
	c=max(c,0);
	d=max(d,0);
	cout<<(c+d<=bot?"YES":"NO")<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	int _=1;
	cin>>_;
	while(_--)
	{
		slove();
	}
	return 0;
}