竞赛讨论区 > 牛客挑战赛 66 解题报告
头像
tmpOUO
发布于 2023-02-06 11:10 福建
+ 关注

牛客挑战赛 66 解题报告

A

模拟题意,求出 \text{rev}(x) 即可。

时间复杂度 O(n\log_{10}x)

B

考虑所有叶子节点,设数量为 x

x\equiv 0(mod\ 2),我们可以令一半为白色,另一半为黑色。另外还要使所有非叶子节点都不作贡献,这是容易构造的。

反之,我们令 \lfloor{\frac{x}{2}}\rfloor 的叶子为白色,\lceil{\frac{x}{2}}\rceil 的叶子为黑色。那么,我们还需使一个非叶子节点的子树全为白色。

考虑只调整『所有儿子都是叶子的』非叶子节点,如果存在一个这样的点,且其的儿子个数 \le \lfloor{\frac{x}{2}}\rfloor,我们就可以构造出一组解;如果不存在,说明无解也是容易的。

时间复杂度 O(n)

C

首先要进行一些简单的计算:点数为 (n+1)(m+1),初始边数为 n(m+1)+m(n+1),删了 nm 条边,则最后剩下 n(m+1)+m(n+1)-nm=n+m+nm=(n+1)(m+1)-1 条边。再注意到题目给出的一些性质,我们可以发现最后的图是一棵树。

接下来就是一个简单的树上背包了,对被选的点进行 dp。可能要注意代码实现的一些细节。

时间复杂度 O(n^2m^2)

D

首先有一个建模,源点向所有 i 连边,所有 p_j 向汇点连边,如果 ip_j 满足题目给出的条件,则在他们间连边。我们可以根据是否满流判断是否有解,再根据残量网络构造出一组合法的解。

这样做的时间复杂度是 O(\frac{n^{2.5}}{ln^2 n}) 的。

打表观察,我们会发现一个有意思的结论:在 [1,10^5] 中,当 n>14850 时无解。(有没有 MO 老哥会证明)

存在答案的上界是因为随着 n 的增大,素数越来越稀疏。而出题人实现的网络流在 n=14850 时,可以在两倍时限内通过此题。

E

几个观察:

  • 某个 2 l r 如果满足 ,那么没用。
  • 某个 2 l r 满足 ,那么其本身一定是一个等差数列。
  • 如果两个 2 l r 的交 ,那么可以合并。
  • 如果两个 2 l r 的交 且均满足 ,那么可以合并。
  • 如果存在 1 l r,使得 ,那么无解。
  • 如果『合并后的』某个 2 l r 包含了某个 1 l r,那么无解。

除此之外,我们可以断言一定有解。

可以分类讨论,对所有优美区间以右端点升序排序,对于 r=l+2,r=l+3,r>l+3 可以分别给出不同的构造,使得所有不被任何优美区间包含的区间均无解。

嘴上说说容易,但是写起来细节多到精神污染,这里给出题人的 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

给出结论,(p,q) 满足题目给出的二元关系当且仅当 p,q 均为同一个回文子串 t 重复若干次构成。

考虑怎么证明:

  1. 不妨设 ,则有 为 的前缀。用反证法,考虑 ,若 均没被删完,则有 ,这显然与题设的 是矛盾的。
  2. 接下来,转化为 均为回文串,去证均为同一字符串重复若干次。这用 理论那套是非常易于证明的。

我们枚举所有回文串 p,如果我们知道了它的最小循环节 x,那么我们可以在 x 处快速计算答案(假设有 k 个数以 x 为最小循环节,则对答案的贡献为 2^k)。

无论怎么求最小循环节,必须用类似哈希表的数据结构维护 x,复杂度是 O(|s|log|s|),应该过不去,考虑怎么优化他。

枚举这个集合里的最长回文串 p,如果他的最小循环节为 x,则他对答案的贡献为 2^{\frac{|p|}{|x|}-1},这样就不用数据结构维护 x 了。

最后的问题是怎么求最小循环节,暴力试除是 O(|s|\sqrt |s|) 或者 O(|s|log|s|) 的,不够优秀。

建出 s 的回文自动机,考虑其中的一个结点 u,则其代表的回文串的最小的非其本身的循环节长度为 len_u-len_{fail_u}(如果存在),这样就能快速计算了。

时间复杂度 O(|s|)

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐