2018 Winter Series 7th 题解

2018-02-10 12:18:26 By youyl

题解

扑克牌

本题有很多做法,以下给出一种简单的做法:

先在首尾各加入一个0,然后考虑相邻两个数的差的绝对值。

首先每次去掉一个顺子必然是去掉尽可能长的顺子,即开头和结尾的值不为0。

每次去掉一个顺子只会在顺子的开头和结尾发生变化。

所以答案就是相邻两个数的差的绝对值的和除以2。

直径

考虑去掉一条边,树被分成了两个部分。

然后考虑这两个部分的直径,那么最大值显然是将两个部分的直径首尾相连,最小值显然是连接两个直径的中点。

只需要维护树上每条边两侧的两个子树的直径即可。

字符串

满足条件2的子串很好处理。

接下来考虑满足条件1的子串。

设前i个字符中,B的个数是b[i],S的个数是s[i],C的个数是c[i]。

那么考虑考虑一段j+1到i的子串,满足条件1的子串需要满足:

  • c[i]-c[j]!=s[i]-s[j]
  • c[i]-c[j]!=b[i]-b[j]
  • b[i]-b[j]!=s[i]-s[j]

移项可以得到:

  • c[i]-s[i]!=c[j]-s[j]
  • c[i]-b[i]!=c[j]-b[j]
  • b[i]-s[i]!=b[j]-s[j]

所以对每个点维护c[i]-s[i],c[i]-b[i],b[i]-s[i]

按照第一维排序,用树状数组维护第二维的前缀和后缀,树状数组中存储i的最大值,第三维不同的最大值,最小值,第三维不同的最小值

最终复杂度$O(n\log n)$

标程

扑克牌

#include<cstdio>
using namespace std;
long long a[120000];
int n;
long long ans;
inline long long fab(long long x)
{
    if(x>0)return x;
    return -x;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for (int i=1;i<=n+1;i++)
    {
        ans+=fab(a[i]-a[i-1]);
    }
    printf("%lld\n",ans/2);
    return 0;
}

直径

#include<cstdio>
#include<algorithm>
using namespace std;
int n,x1,x2;
int ed,st[520000];
struct node
{
    int to,next;
}g[1200000];
int minn,maxx;
inline void add(int x,int y)
{
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    st[x]=ed;
}
int fir[520000];
int sec[520000];
int thi[520000];
int dia[520000];
int fd[520000];
int sd[520000];
inline void dfs(int x,int fa)
{
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            dfs(g[i].to,x);
            thi[x]=max(thi[x],fir[g[i].to]+1);
            if(sec[x]<thi[x])
            {
                swap(sec[x],thi[x]);
            }
            if(sec[x]>fir[x])
            {
                swap(sec[x],fir[x]);
            }
            dia[x]=max(dia[x],dia[g[i].to]);
            sd[x]=max(sd[x],dia[g[i].to]);
            if(sd[x]>fd[x])swap(sd[x],fd[x]);
        }
    }
    dia[x]=max(dia[x],fir[x]+sec[x]);
}
inline int calc(int x,int y)
{
    return max(max(x,y),x/2+y/2+x%2+y%2+1);
}
inline void solve(int x,int fa,int dis,int lg)
{
    if(fa!=0)
    {
        minn=min(minn,calc(dis,dia[x]));
        maxx=max(maxx,dis+1+dia[x]);
    }
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            int tmp1=fir[x],tmp2=fd[x];
            if(tmp2==dia[g[i].to])
            {
                tmp2=sd[x];
            }
            if(tmp1==fir[g[i].to]+1)
            {
                tmp1=sec[x];
                tmp2=max(tmp2,sec[x]+max(thi[x],lg));
            }
            else if(sec[x]==fir[g[i].to]+1)
            {
                tmp2=max(tmp2,fir[x]+max(thi[x],lg));
            }
            else
            {
                tmp2=max(tmp2,fir[x]+max(sec[x],lg));
            }
            tmp1=max(lg,tmp1);
            tmp2=max(tmp2,dis);
            solve(g[i].to,x,tmp2,tmp1+1);
        }
    }
}
int main()
{
    scanf("%d",&n);
    minn=1000000000;
    for (int i=1;i<n;i++)
    {
        scanf("%d %d",&x1,&x2);
        add(x1,x2);
        add(x2,x1);
    }
    dfs(1,0);
    solve(1,0,0,0);
    printf("%d\n%d\n",minn,maxx);
    return 0;
}

字符串

#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans,top;
const int M=1000010;
char str[1200000];
int b[1200000];
int c[1200000];
int s[1200000];
struct node
{
    int b,c;
}a[1200000];
int ed,st[2200000];
struct graph
{
    int to,next;
}g[1200000];
inline int lowbit(int x)
{
    return (x&(-x));
}
inline void add(int x,int y)
{
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    st[x]=ed;
}
struct nodeminmax
{
    int mi1,mi2,mx1,mx2;
    nodeminmax()
    {
        mi1=-1;
        mi2=-1;
        mx1=-1;
        mx2=-1;
    }
    inline void update(int pos)
    {
        if(mi1==-1)
        {
            mx1=pos;
            mi1=pos;
            return;
        }
        if(mi1>pos)
        {
            if(a[pos].c!=a[mi1].c)
            {
                mi2=mi1;
            }
            mi1=pos;
        }
        else if((mi2==-1||mi2>pos)&&(a[pos].c!=a[mi1].c))
        {
            mi2=pos;
        }
        if(mx1<pos)
        {
            if(a[pos].c!=a[mx1].c)
            {
                mx2=mx1;
            }
            mx1=pos;
        }
        else if((mx2==-1||mx2<pos)&&(a[pos].c!=a[mx1].c))
        {
            mx2=pos;
        }
    }
    inline void query(int pos)
    {
        if(mx1!=-1&&a[pos].c!=a[mx1].c)
        {
            ans=max(ans,mx1-pos);
        }
        else if(mx2!=-1&&a[pos].c!=a[mx2].c)
        {
            ans=max(ans,mx2-pos);
        }
        if(mi1!=-1&&a[pos].c!=a[mi1].c)
        {
            ans=max(ans,pos-mi1);
        }
        else if(mi2!=-1&&a[pos].c!=a[mi2].c)
        {
            ans=max(ans,pos-mi2);
        }
    }
};
struct prebit
{
    nodeminmax a[2200000];
    inline void update(int b,int pos)
    {
        while (b<=top)
        {
            a[b].update(pos);
            b+=lowbit(b);
        }
    }
    inline void query(int b,int pos)
    {
        while (b)
        {
            a[b].query(pos);
            b-=lowbit(b);
        }
    }
}pre;
struct sufbit
{
    nodeminmax a[2200000];
    inline void update(int b,int pos)
    {
        while (b)
        {
            a[b].update(pos);
            b-=lowbit(b);
        }
    }
    inline void query(int b,int pos)
    {
        while (b<=top)
        {
            a[b].query(pos);
            b+=lowbit(b);
        }
    }
}suf;
int main()
{
    ans=0;
    int bef=0;
    scanf("%d",&n);
    scanf("%s",str+1);
    for (int i=1;i<=n;i++)
    {
        if(i==n||str[i]!=str[i+1])
        {
            ans=max(i-bef,ans);
            bef=i;
        }
    }
    a[0].b=0;
    a[0].c=0;
    add(M,0);
    for (int i=1;i<=n;i++)
    {
        b[i]=b[i-1]+(str[i]=='B');
        c[i]=c[i-1]+(str[i]=='C');
        s[i]=s[i-1]+(str[i]=='S');
        a[i].b=c[i]-s[i];
        a[i].c=s[i]-b[i];
        add(b[i]-c[i]+M,i);
    }
    top=M+M+10;
    for (int x=1;x<=top;x++)
    {
        for (int i=st[x];i!=0;i=g[i].next)
        {
            pre.query(a[g[i].to].b+M-1,g[i].to);
            suf.query(a[g[i].to].b+M+1,g[i].to);
        }
        for (int i=st[x];i!=0;i=g[i].next)
        {
            pre.update(a[g[i].to].b+M,g[i].to);
            suf.update(a[g[i].to].b+M,g[i].to);
        }
    }
    printf("%d\n",ans);
    return 0;
}

评论

avatar
skyline
补充:C题(#72. 字符串)O(n)做法 算法:8个代表重要思想 http://acm.nflsoj.com/submission/4069 欢迎hack

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。