这些都是近来我 VP CF 遇到的奇奇妙妙的题。
构造
这一类题通常需要大胆猜结论/经验积累。
CF1514B AND 0, Sum Big
首先因为与运算和为 ,所以每一位上都至少有一个数这一位为 。
然后因为元素的和要尽量大,所以肯定不存在两个数同一位为 。
那么每一位都需要让 中的恰好一个在这一位为 ,所以答案即为 。
CF1630A And Matching
首先来看三个性质:
- ,因为 和 的二进制是“错开”的;
- ,因为 的二进制全是 ;
- ,显然。
接下来分类讨论:
- 若 :
可以先构造出 和 ,然后对于每个 且 且 的 构造出 。
注意特判 ,这时不需要构造 。
- 若
这时容易发现让其中一对与为 的办法行不通了,所以我们要另辟蹊径,让两对的与加起来为 。
显然 ,,那么先构造这两对即可。
接下来发现 ,, 也就是说 和 不能组成 了,那么让它们单独组,构造 。
接下来构造 即可。
注意到若 则 、、、、、 会重叠,这时是无解的。
CF1659D Reverse Sort Sum
不难发现,由于每个 对 都有且仅有 的贡献,所以 中 的个数即为 。
接下来,我们很容易发现 当且仅当 ,因为 时 一定为 。
有了这个性质的启示,不难想到可以通过减掉 对 的贡献来实现缩小问题的规模,令 变为 。实际上实现起来也并不难,因为我们已经取得了 中 的个数 , 一定只会对 有 的贡献,那么用差分来实现快速区间减法即可。
CF1658D2 388535 (Hard Version)
首先肯定有一个 满足 ,即它本来是 。那么我们枚举每个 ,判断它原来是不是 即可。
接下来思考判断的方法。不难发现,由于 原来是不重复的一个排列,所以异或后的 也是不重复的一个排列,所以只要 满足 就说明 原来是 。
这个东西用 trie 维护即可。
CF1592C Bakry and Partitioning
从每一部分的异或和相同出发,设分割后每一部分的异或和都为 ,所有 的异或和为 。不难发现要么 即最后是偶数个 异或起来,要么 即最后是奇数个 异或起来。
-
若 ,我们割断任意一条边都一定合法。因为割出来的两部分只有异或和相同它们异或起来的结果 才为 。
-
若 ,那么割断两条边,分割出三个异或和为 的连通块显然是最优的。所以考虑找到两个异或和都为 的连通块,剩下那一块异或和就自然为 。因为肯定有一个满足条件的连通块是一棵子树,减掉它的贡献后又会有一个满足条件的连通块是一棵子树,所以跑一次 ,求出每个节点子树去掉异或和为的 子树后的异或和 即可。最后若 就说明有解。
部分代码如下:
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
用 和 交替着填,实在不行用 即可。
CF1592D Hemose in ICPC
首先由于 里的数越多,结果就越小,所以最大的 一定是一条边的边权。
那么我们先询问所有节点求出最大的 ,然后二分所有的边。
考虑如何二分,显然需要把树“拍扁”,用类似 序的东西来解决。具体的,考虑节点 和它的所有儿子 ,显然 都有一条边,那么先往序列里加入 ,再在 完每个 后都加入 即可。
CF1634D Finding Zero

考虑从 个可能的下标 中去掉一些不可能的下标。
显然一次询问的结果是三个数的极差。记 为询问四个下标里分别除去 的结果,即 为询问 的结果。那么显然 就是 的极差。
不难发现,若 ,那么 一定不可能为 。因为去掉 后三个数的极差一定不是这四个数的极差。
这样每排除一次至少可以去掉至少两个不可能的下标,总共需要的次数上限就是 ,足以通过此题。
特别的,若剩下三个下标未排除,拿一个排除过的下标和它们组队即可。
杂题
最后给两道匕匕车交女少白勺杂题。
CF1632D New Year Concert
不难发现,当区间 的右端点 固定不动,左端点 减小时, 是单调不增的,而 则是单调递增的,这造成了它们最多只会有一个交点。也就是说,对于一个固定的 ,最多有一个 满足 。
那么用倍增实现 预处理 查询 ,然后枚举 ,每次找满足条件的 ,如果有那么答案加一并且把 改为 即可。
部分代码如下:
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
并查集拆点模板题,建议先看一下我的博客。
每个人拆两个点 和 ,分别表示这个人是好人和坏人的情况,统计答案的时候对每个集合的“帮主”是好人/坏人的情况下的好人的数量取最大值,加起来即可。
CF1685B Linguistics
贪心。
题意显然可以转化为把 个 、 个 、 个 和 个 不重叠地放进字符串 中,使得对应位相等。
首先若放的 、 的个数和 中 、 的个数不同,那么就是不行的。接下来考虑让所有放单个 和 的操作都挪到最后进行,那么问题就转化为判断能否把 个 和 个 都放进 里面。
考虑一段形如 这样 相间的极长子串,设它的长度为 ,那么分类讨论:
- 若 是奇数,那么这一段可以放 个 或 ;
- 若 是偶数,那么:
- 若这一段以 结尾,即形如 ,那么可以放 个 或 ,或者可以放 个 ;
- 若这一段以 结尾,即形如 ,那么可以放 个 或 ,或者可以放 个 ;
不难发现,当 为奇数时这一段对 和 都是公平的,即它们放的上限都是 ,并且对放多少个 和多少个 没有限制,只要它们数量加起来不超过 就可以了。
所以可以令 即奇数段最多可以放的 和 的数量。
若 为偶数,那么这一段对 和 是不公平的,即它们放的上限一个多,一个少。为了减少位置的浪费,不妨先钦定这一段都放上限多的那种字符串,再用两个数组 和 存偏心 或者 即能放更多 或 的偶数段中两种字符串放置的上限。
最后若每一段偶数段都放上限多的字符串时 或 还是大于 ,那么就让偏心另一种字符串的偶数段分一些位置放这种字符串即可。不难发现由于没分之前偶数段总共能放 个字符串,分了之后只能放 个,所以分的段数肯定是越少越好。那么按段的长度从大到小分即可。
代码如下:
// 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;
}