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
给出结论, 满足题目给出的二元关系当且仅当 均为同一个回文子串 重复若干次构成。
考虑怎么证明:
- 不妨设 ,则有 为 的前缀。用反证法,考虑 ,若 均没被删完,则有 ,这显然与题设的 是矛盾的。
- 接下来,转化为 均为回文串,去证均为同一字符串重复若干次。这用 理论那套是非常易于证明的。
我们枚举所有回文串 ,如果我们知道了它的最小循环节 ,那么我们可以在 处快速计算答案(假设有 个数以 为最小循环节,则对答案的贡献为 )。
无论怎么求最小循环节,必须用类似哈希表的数据结构维护 ,复杂度是 ,应该过不去,考虑怎么优化他。
枚举这个集合里的最长回文串 ,如果他的最小循环节为 ,则他对答案的贡献为 ,这样就不用数据结构维护 了。
最后的问题是怎么求最小循环节,暴力试除是 或者 的,不够优秀。
建出 的回文自动机,考虑其中的一个结点 ,则其代表的回文串的最小的非其本身的循环节长度为 (如果存在),这样就能快速计算了。
时间复杂度 。
全部评论
(1) 回帖