前言

ZhYic是个非常菜的小伙子,这天听同学说打CF,于是兴奋起来,上了这趟黑车。“打CF?水水水?好啊!”

然后打CF时先是迟到了半个多小时。

后来打了AB之后一看C:“DP?好像不可能做到啊。看看D吧。”

看D题:目测优化一波暴力大概可以混一下,复杂度不会证,等会再打吧。

看F题:wa,树形DP上啊,然后发现题目没看全,还要链长度和最大,GG。

思考脑抽一波后想起白天才学的点分治,感觉良好,$O(nlog^2n)$应该可以卡一卡吧?

还剩15分钟,弃坑了。。。D题,最后一分钟交上去,TLE$\#8$,凉凉。

最后掉回了绿名。。。又是一只pupil。

题解

A. Diverse Substring

题意

一个字符串,问有没有一个连续子串满足其中任意字符出现次数不超过$l/2$(l为子串长度),并输出任意一个子串。

做法

随便check$s_i,s_{i+1}$,遇到$s_i\ne s_{i+1}$输出这两个字符即可。

B. Vasya and Books

题意

给出一个序列$a_i$表示栈中每层元素编号,另一个序列$b_i$表示取出元素的顺序。输出每次取出元素时总共移出多少元素(取出第i个元素需要先取出1~i-1个元素,若已经取出就输出0)。

做法

用一个$top$记录当前栈顶位置,每次操作比较$b_i$和$top$大小,若$top\ge b_i$就不管,否则更新为$b_i$,输出增加值。

C. Vasya and Robot

先$ ^{sto^{sto^{sto}}}orz_{orz_{orz}}$一波@ViXbob&@Edgration,当时就秒了。然而他们发的代码我没看到,于是光荣地掉车,掉分惨重。

感觉当时我好像没完全看懂题意或者潜意识理解错题意了。。任意改变方向这么水的东西。

题意

给定二维平面上起点终点和一个原移动序列(UDLR),求最少改变多长一个子序列中的值可以使vasya到终点。

做法

思路是二分。但是关于怎么check,就需要发现题中的一点特性了。

因为可以任意更改操作方向,我们可以发现每次更改对于总移动的$x+y$的影响是$\pm2$的,区间更改的影响$\varDelta(x+y)\le len$。

因此我们可以二分得到一个区间长度$m$,$O(n-m)$check过去,如果更改此区间能满足对总移动的x+y的影响就可以缩小长度m。

总复杂度$O(nlogn)$。

代码

#include<bits/stdc++.h>
        using namespace std;
        int dx['Z'],dy['Z'];
        bool chk(int x,int y,int m)
        {
            return x+y<=m&&(x+y)%2==m%2;
        }
        int n,x,y,ans;
        char str[200020];
        int main()
        {
            dx['U']=dx['D']=0,dy['U']=1,dy['D']=-1,dx['L']=-1,dx['R']=1,dy['L']=dy['R']=0;
            scanf("%d%s%d%d",&n,str,&x,&y);
            int sx=0,sy=0;
            if(n<abs(x)+abs(y)||(n-abs(x)-abs(y))%2){printf("-1");return 0;}
            for(int i=0;i<n;i++)
                sx+=dx[str[i]],sy+=dy[str[i]];
            if(sx==x&&sy==y){putchar('0');return 0;}
            int l=-1,r=n;
            while(l<=r)
            {
                int m=(l+r)/2,lx=0,rx=0,ly=0,ry=0;
                bool b=false;
                for(int i=m;i<n;i++)
                    rx+=dx[str[i]],ry+=dy[str[i]];
                for(int i=0;i+m<=n;i++)
                {
                    if(b=chk(abs(x-(rx+lx)),abs(y-(ry+ly)),m)){ans=m,r=m-1;break;}
                    lx+=dx[str[i]],ly+=dy[str[i]];
                    if(i+m<n)rx-=dx[str[i+m]],ry-=dy[str[i+m]];
                }
                if(!b)l=m+1;
            }
            printf("%d",ans);
            return 0;
        }
        

 

D. Berland Fair

感谢神仙@ViXbob&@Anoxiacxy,给出了正确复杂度证明。

题意

一个循环的序列,从初始位置1号点开始在上面跑,对于每个点如果当前money不少于到达的点的花费c就会用c买一件物品,到下一个点。如果当前的money不足以买任何物品就退出。

做法

我们循环地算出每次到1号点时环内所有可购买物品(只要1号点时money不少于c就可购买)的价值总和sum,然后用T直接对sum取模,继续重复此过程,如果money<sum就跑一遍处理出这一趟之后的money。

代码

#include<bits/stdc++.h>
        using namespace std;
        priority_queue<pair<int,int> >q;
        long long n,mn=INFINITY,a[200020];
        long long ans;
        long long T,sum,cnt;
        int main()
        {
            scanf("%I64d%I64d",&n,&T);//T是拥有的money
            cnt=n;
            for(int i=1;i<=n;i++)
                scanf("%lld",&a[i]),mn=min(mn,a[i]);
            while(T>0)
            {
                sum=0;cnt=n;
                for(int i=1;i<=n;i++)
                {
                    if(a[i]>T){cnt--;continue;}
                    sum+=a[i];
                }
                //可以使用堆优化,就不用每次都扫n个了。但复杂度主要还是在下面的过程
                if(cnt==0)break;
                if(T>=sum)
                {
                    ans+=cnt*(T/sum);
                    T%=sum;
                }
                else
                {
                    for(int i=1;i<=n;i++)
                        if(T>=a[i])T-=a[i],ans++;
                }
            }
            printf("%lld",ans);
        }
        

 

复杂度问题

结合代码分析,如果当前T>=sum会进行取模,因此此部分复杂度为$O(logn)$。

如果当前T<sum,会遍历1~n,此过程一定会使T减小到小于某个$a_i$,因此也就相当于一次取模(对某个$a_i$)。

最多取模$logn$次,因此总复杂度为$O(nlogn)$。

F. Choosing Two Paths

题意

给一棵无根树,要求选出两条链满足在两链的交最长的基础上两链的总长度最长并输出一组可行点对。

即找出最长两个端点的度>3的链,并使它两个端点的子树的直径和最大。

做法

当时知道怎么解决第一个条件(类树的直径DP),但对于第二点就束手无策了。

其实很简单,类似于树的直径有DP和DFS两次两种写法,这里可以采用DFS两次的方法。

我们从任意点出发,找到它的子树中度>3的最长链中子树直径最大的。即先DFS找出所有度>3的端点的链后按端点为第一关键字,端点子树直径为第二关键字排序就可以得到一个等效意义上的最远点。从这个点出发再进行上述过程就找到了树的等效直径。

这里说等效直径是因为实际上这里就是类似于树的直径的一个东西,已双关键字作为直径。并且这种方法的正确性和DFS两次找直径的方法证明基本相同(greedy有什么好说的)。

DP方法又是@ViXbob神仙研究了,但我记得他调了整整一个下午没调出来。

代码

#include<bits/stdc++.h>
        #define Side(x) for(int i=p[x];i;i=nt[i])
        using namespace std;
        const int N=200020;
        int v;char ch;
        int read()
        {
            v=0;while(!isdigit(ch))ch=getchar();
            while(isdigit(ch))v=(v<<1)+(v<<3)+ch-'0',ch=getchar();
            return v;
        }
        int n,cnt,tot,e[N<<1],nt[N<<1],p[N],edg[N],ans[2];
        void _add(int x,int y){e[++tot]=y,nt[tot]=p[x],p[x]=tot,++edg[x];}
        inline void add(int x,int y){_add(x,y),_add(y,x);}
        struct pt
        {
            int d,id;
            bool operator <(const pt& x)const{return d<x.d;}
            bool operator >(const pt& x)const{return d>x.d;}
            pt operator +(const int x){return (pt){d+x,id};}
        }f[N][2];
        struct node
        {
            int s,d;
            pt x,y;
            bool operator <(const node& a)const{return d==a.d?x.d+y.d>a.x.d+a.y.d:d>a.d;}
        }o[N];
        void dfs(int x,int fr,int d)
        {
            pt tmp;
            f[x][0].d=0;
            Side(x)
            {
                if(e[i]==fr)continue;
                dfs(e[i],x,d+1);
                if(f[e[i]][0]+1>f[x][0])tmp=f[e[i]][1]+1,f[x][1]=f[x][0],f[x][0]=f[e[i]][0]+1;
                else if(f[x][1]<f[e[i]][0]+1)f[x][1]=f[e[i]][0]+1;
            }
            if(edg[x]>2)
                o[++cnt]=(node){x,d,f[x][0],f[x][1]};
        }
        int main()
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++)f[i][0].id=f[i][1].id=i,f[i][0].d=f[i][1].d=-INFINITY;
            for(int i=1,xi,yi;i<n;i++)add(read(),read());
            dfs(1,1,0);
            sort(o+1,o+1+cnt);
            ans[0]=o[1].x.id,ans[1]=o[1].y.id;
            cnt=0;
            for(int i=1;i<=n;i++)f[i][0].id=f[i][1].id=i,f[i][0].d=f[i][1].d=-INFINITY;
            dfs(o[1].s,o[1].s,0);
            sort(o+1,o+1+cnt);
            printf("%d %d\n%d %d",ans[0],o[1].x.id,ans[1],o[1].y.id);
        }
        

后记

E题太难啦,数位DP还有什么记忆化搜索,留坑日后再填。