牛客挑战赛 66 解题报告
A
模拟题意,求出 即可。
时间复杂度 。
B
考虑所有叶子节点,设数量为 。
若 ,我们可以令一半为白色,另一半为黑色。另外还要使所有非叶子节点都不作贡献,这是容易构造的。
反之,我们令 的叶子为白色, 的叶子为黑色。那么,我们还需使一个非叶子节点的子树全为白色。
考虑只调整『所有儿子都是叶子的』非叶子节点,如果存在一个这样的点,且其的儿子个数 ,我们就可以构造出一组解;如果不存在,说明无解也是容易的。
时间复杂度 。
C
首先要进行一些简单的计算:点数为 ,初始边数为 ,删了 条边,则最后剩下 条边。再注意到题目给出的一些性质,我们可以发现最后的图是一棵树。
接下来就是一个简单的树上背包了,对被选的点进行 dp。可能要注意代码实现的一些细节。
时间复杂度 。
D
首先有一个建模,源点向所有 连边,所有 向汇点连边,如果 与 满足题目给出的条件,则在他们间连边。我们可以根据是否满流判断是否有解,再根据残量网络构造出一组合法的解。
这样做的时间复杂度是 的。
打表观察,我们会发现一个有意思的结论:在 中,当 时无解。(有没有 MO 老哥会证明)
存在答案的上界是因为随着 的增大,素数越来越稀疏。而出题人实现的网络流在 时,可以在两倍时限内通过此题。
E
几个观察:
-
某个
2 l r
如果满足 ,那么没用。 -
某个
2 l r
满足 ,那么其本身一定是一个等差数列。 -
如果两个
2 l r
的交 ,那么可以合并。 -
如果两个
2 l r
的交 且均满足 ,那么可以合并。 -
如果存在
1 l r
,使得 ,那么无解。 -
如果『合并后的』某个
2 l r
包含了某个1 l r
,那么无解。
除此之外,我们可以断言一定有解。
可以分类讨论,对所有优美区间以右端点升序排序,对于 可以分别给出不同的构造,使得所有不被任何优美区间包含的区间均无解。
嘴上说说容易,但是写起来细节多到精神污染,这里给出题人的 std:
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 1000100
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,m,x[N];
struct Range{int l,r; IL bool operator <(const Range &a)const{return r>a.r||r==a.r&&l<a.l;}}last;
std::vector<Range>legal,illegal,vec;
IL bool contain(reg Range p,reg Range q){return p.l<=q.l&&q.r<=p.r;}
std::mt19937 rnd((unsigned long long)(new char));
const int mod=1e9,B=2e8,md=5e7;
int D;
IL int Abs(reg int x){return x<0?-x:x;}
IL int sign(reg int x){return x<0?-1:1;}
main()
{
n=read(),m=read();
for(reg int op,l,r;m--;)op=read(),l=read(),r=read(),(op==1?illegal:legal).push_back({l,r});
for(reg auto x:illegal)if(x.r-x.l<2)return puts("NO"),0;
std::sort(legal.begin(),legal.end()),std::sort(illegal.begin(),illegal.end());
for(reg auto x:legal)
{
if(contain(last,x))continue;
if(x.r-x.l<3){vec.push_back(x); continue;}
if(x.r-2>=last.l||x.r-1>=last.l&&x.r-x.l>3&&last.r-last.l>3)
last.l=x.l,!last.r?last.r=x.r:0; else vec.push_back(last),last=x;
}
if(last.r)vec.push_back(last);
std::swap(legal,vec),std::sort(legal.begin(),legal.end());
std::reverse(legal.begin(),legal.end()),last={mod,mod},vec.clear();
for(reg auto x:legal)
{
if(contain(last,x))continue;
if(x.r-x.l<3){vec.push_back(x); continue;}
if(x.l+2<=last.r||x.l+1<=last.r&&x.r-x.l>3&&last.r-last.l>3)
last.r=x.r,last.l==mod?last.l=x.l:0; else vec.push_back(last),last=x;
}
if(last.l)vec.push_back(last);
std::swap(legal,vec),std::sort(legal.begin(),legal.end()),last={mod,0};
for(reg int i=0,j=0;i<illegal.size();++i)
{
for(;j<legal.size()&&illegal[i].r<=legal[j].r;++j)
if(legal[j].l<=last.l)last=legal[j];
if(contain(last,illegal[i]))return puts("NO"),0;
}
puts("YES"),std::reverse(legal.begin(),legal.end()),legal.push_back({n+1,n+3}),last={0,0};
for(reg auto p:legal)
{
if(p.r-p.l<2||x[p.r])continue;
for(reg int i=last.r+1;i<p.l;++i)x[i]=B+rnd()%md;
if(!x[p.l])x[p.l]=B+rnd()%md; D=x[p.l]-x[p.l-1];
if(p.r-p.l==2)
{
if(!x[p.l+1])x[p.l+1]=x[p.l]+(Abs(D)==2?D*2:(Abs(D)==4?D/2:sign(D)*2));
D=x[p.l+1]-x[p.l];
if(Abs(D)>2)assert(D%4==0),x[p.r]=x[p.r-1]-D/2;
else x[p.r]=x[p.r-1]+(x[p.l]==x[p.l-1]+D||last.r-last.l==3?-2*D:D);
assert(Abs(D)==2||Abs(D)==4);
}else if(p.r-p.l==3)
{
if(x[p.l+1]==x[p.l]+D&&last.r-last.l<4)x[p.l]+=D*3;
if(!x[p.l+1])D=Abs(D)==4?-D:sign(D)*4; else D=x[p.l+1]-x[p.l];
x[p.l+1]=x[p.l]+D,x[p.r-1]=x[p.l]+D/2,x[p.r]=x[p.r-1]+D;
assert(Abs(D)==2||Abs(D)==4);
}else
{
if(x[p.l+1]==x[p.l]+D)x[p.l]+=D*3;
if(x[p.l+1])D=x[p.l+1]-x[p.l]; else D=Abs(D)==2?-D:(Abs(D)==4?D/2:sign(D)*2);
for(reg int i=p.l;i<=p.r;++i)if(!x[i])x[i]=x[i-1]+D;
assert(Abs(D)==2||Abs(D)==4);
}
last=p;
}
for(reg int i=1;i<=n;++i)printf("%d ",x[i]);
}
也有其他的做法,比如审核大哥就给了个 dp of dp 的做法,但同样难写到爆。
F
给出结论, 满足题目给出的二元关系当且仅当 均为同一个回文子串 重复若干次构成。
考虑怎么证明:
-
不妨设 ,则有 为 的前缀。用反证法,考虑 ,若 均没被删完,则有 ,这显然与题设的 是矛盾的。
-
接下来,转化为 均为回文串,去证均为同一字符串重复若干次。这用 理论那套是非常易于证明的。
我们枚举所有回文串 ,如果我们知道了它的最小循环节 ,那么我们可以在 处快速计算答案(假设有 个数以 为最小循环节,则对答案的贡献为 )。
无论怎么求最小循环节,必须用类似哈希表的数据结构维护 ,复杂度是 ,应该过不去,考虑怎么优化他。
枚举这个集合里的最长回文串 ,如果他的最小循环节为 ,则他对答案的贡献为 ,这样就不用数据结构维护 了。
最后的问题是怎么求最小循环节,暴力试除是 或者 的,不够优秀。
建出 的回文自动机,考虑其中的一个结点 ,则其代表的回文串的最小的非其本身的循环节长度为 (如果存在),这样就能快速计算了。
时间复杂度 。