2022 暑假杂题选讲

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

构造

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

CF1514B AND 0, Sum Big

首先因为与运算和为 00,所以每一位上都至少有一个数这一位为 00

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

那么每一位都需要让 a1na_{1\sim n} 中的恰好一个在这一位为 00,所以答案即为 nkn^k

CF1630A And Matching

首先来看三个性质:

  • i&(n1i)=0i\&(n-1-i)=0,因为 iin1in-1-i 的二进制是“错开”的;
  • i&(n1)=ii\&(n-1)=i,因为 n1n-1 的二进制全是 11
  • i&0=0i\&0=0,显然。

接下来分类讨论:

  • k=n1k\not=n-1

可以先构造出 k&(n1)=kk\&(n-1)=k(n1k)&0=0(n-1-k)\&0=0,然后对于每个 1in11\le i\le n-1i=ki\not=ki=n1ki\not=n-1-kii 构造出 i&(n1i)=0i\&(n-1-i)=0

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

  • k=n1k=n-1

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

显然 (n1)&(n2)=n2(n-1)\&(n-2)=n-21&(n3)=11\&(n-3)=1,那么先构造这两对即可。

接下来发现 n1(n1)=0n-1-(n-1)=0n1(n3)=2n-1-(n-3)=2n1(n2)=1n-1-(n-2)=1 也就是说 0022 不能组成 i&(n1i)=0i\&(n-1-i)=0 了,那么让它们单独组,构造 0&2=00\&2=0

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

注意到n4n\le 4n1n-1n2n-2n3n-3001122 会重叠,这时是无解的

CF1659D Reverse Sort Sum

不难发现,由于每个 11C\sum C 都有且仅有 nn 的贡献,所以 AA11 的个数即为 Cn\dfrac{\sum C}{n}

接下来,我们很容易发现 An=1A_n=1 当且仅当 Cn=nC_n=n,因为 An=1A_n=1Bi,nB_{i,n} 一定为 11

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

CF1658D2 388535 (Hard Version)

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

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

这个东西用 trie 维护即可。

CF1592C Bakry and Partitioning

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

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

  • sum=ksum=k,那么割断两条边,分割出三个异或和为 kk 的连通块显然是最优的。所以考虑找到两个异或和都为 kk 的连通块,剩下那一块异或和就自然为 kk。因为肯定有一个满足条件的连通块是一棵子树,减掉它的贡献后又会有一个满足条件的连通块是一棵子树,所以跑一次 dfsdfs求出每个节点子树去掉异或和为的 kk 子树后的异或和 dpu=xorv 是 u 的儿子[dpv=k]dpvdp_u=\operatorname{xor}_{v\text{ 是 }u\text{ 的儿子}}[dp_v\not=k]dp_v 即可。最后若 u[dpu=k]2\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

1122 交替着填,实在不行用 33 即可。

CF1592D Hemose in ICPC

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

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

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

CF1634D Finding Zero

img

考虑从 44 个可能的下标 b1,b2,b3,b4b_1,b_2,b_3,b_4 中去掉一些不可能的下标。

显然一次询问的结果是三个数的极差。记 q1,q2,q3,q4q_1,q_2,q_3,q_4 为询问四个下标里分别除去 b1,b2,b3,b4b_1,b_2,b_3,b_4 的结果,即 q1q_1 为询问 b2,b3,b4b_2,b_3,b_4 的结果。那么显然 m=max(q1,q2,q3,q4)m=\max(q_1,q_2,q_3,q_4) 就是 ab1,ab2,ab3,ab4a_{b_1},a_{b_2},a_{b_3},a_{b_4} 的极差

不难发现,qi=mq_i=m,那么 bib_i 一定不可能为 00。因为去掉 00 后三个数的极差一定不是这四个数的极差。

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

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

杂题

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

CF1632D New Year Concert

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

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

部分代码如下:

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

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

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

CF1685B Linguistics

贪心。

题意显然可以转化为aaA\texttt{A}bbB\texttt{B}ccAB\texttt{A}\texttt{B}ddBA\texttt{B}\texttt{A} 不重叠地放进字符串 ss 中,使得对应位相等

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

考虑一段形如 ABABABAB\texttt{A}\texttt{B}\texttt{A}\texttt{B}\texttt{A}\texttt{B}\texttt{A}\texttt{B} 这样 AB\texttt{A}\texttt{B} 相间的极长子串,设它的长度为 cntcnt,那么分类讨论:

  • cntcnt 是奇数,那么这一段可以cnt2\lfloor\frac{cnt}{2}\rfloorAB\texttt{A}\texttt{B}BA\texttt{B}\texttt{A}
  • cntcnt 是偶数,那么:
    • 若这一段以 B\texttt{B} 结尾,即形如 ABAB\texttt{A}\texttt{B}\texttt{A}\texttt{B},那么可以cnt21\lfloor\frac{cnt}{2}\rfloor-1AB\texttt{A}\texttt{B}BA\texttt{B}\texttt{A},或者可以放 cnt2\lfloor\frac{cnt}{2}\rfloorAB\texttt{A}\texttt{B}
    • 若这一段以 A\texttt{A} 结尾,即形如 BABA\texttt{B}\texttt{A}\texttt{B}\texttt{A},那么可以cnt21\lfloor\frac{cnt}{2}\rfloor-1AB\texttt{A}\texttt{B}BA\texttt{B}\texttt{A},或者可以放 cnt2\lfloor\frac{cnt}{2}\rfloorBA\texttt{B}\texttt{A}

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

所以可以令 bot=cntmod2=1cnt2bot=\sum\limits_{cnt\operatorname{mod}2=1}\lfloor\frac{cnt}{2}\rfloor奇数段最多可以放的 AB\texttt{A}\texttt{B}BA\texttt{B}\texttt{A} 的数量

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

最后若每一段偶数段都放上限多的字符串时 ccdd 还是大于 00,那么就让偏心另一种字符串的偶数段分一些位置放这种字符串即可。不难发现由于没分之前偶数段总共能放 cnt2\lfloor\frac{cnt}{2}\rfloor 个字符串,分了之后只能放 cnt21\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;
}