标签
题解 标程

20180210讲课

2018-02-10 19:01:23 By youyl

字符串相关

NOIP中和字符串相关的通常只有输入输出部分

历年字符串相关题目:

  • NOIP2012Vigenère密码
  • NOIP2017时间复杂度
  • NOIP2016玩具谜题
  • NOIP2015子串

KMP

KMP学习:http://www.matrix67.com/blog/archives/115

NOI2014动物园:http://uoj.ac/problem/5

标程:

#include<cstdio>
#include<cstring>
using namespace std;
int nxt[1200000];
int T;
char str[1200000];
const long long mod=1000000007;
long long ans;
int S[1200000];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",str+1);
        int ll=strlen(str+1);
        nxt[1]=0;
        S[1]=1;
        ans=1;
        int p1=0,p2=0;
        for (int i=2;i<=ll;i++)
        {
            while (p1!=0&&str[i]!=str[p1+1])
            {
                p1=nxt[p1];
            }
            if(str[i]==str[p1+1])p1++;
            nxt[i]=p1;
            S[i]=S[nxt[i]]+1;
            while (p2!=0&&str[i]!=str[p2+1])
            {
                p2=nxt[p2];
            }
            if(str[i]==str[p2+1])p2++;
            while (p2>i/2)p2=nxt[p2];
            ans*=(S[p2]+1);ans%=mod;
        }printf("%lld\n",ans);
    }
    return 0;
}

字符串hash

题目:http://acm.nflsoj.com/problem/33

题解:http://acm.nflsoj.com/blog/youyl/blog/41

标程:

#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1000000007;
const long long mul=131;
char str[1200000];
inline int solve()
{
    int l=strlen(str+1);
    int lb=1,rb=l,cnt=0;
    long long hashl=0,hashr=0,mult=1;
    while (lb<rb)
    {
        hashr+=mult*(str[rb]-'a'+1)%mod;
        hashr%=mod;
        hashl*=mul;hashl%=mod;
        hashl+=(str[lb]-'a'+1);
        hashl%=mod;
        if(hashl==hashr)
        {
            hashl=0;
            hashr=0;
            mult=1;
            cnt+=2;
        }
        else
        {
            mult*=mul;
            mult%=mod;
        }
        lb++;
        rb--;
    }
    if(lb==rb)cnt++;
    if(lb!=rb&&hashl!=0)cnt++;
    return cnt;
}
int T;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",str+1);
        printf("%d\n",solve());
    }
    return 0;
}

头文件相关

使用规则:http://www.noi.cn/about/rules/362-noi

全面的内容:http://www.cplusplus.com/reference/

下午演示的一些函数和容器的用法还需要各位多加练习。

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;
}

20180206 题目列表

2018-02-06 15:48:01 By youyl

NOIP2014 联合权值

https://www.luogu.org/problemnew/show/P1351

考虑距离为2的点对的时候考虑他们的中点

第一问很容易解决,在每个点上记录相邻点的最大值和次大值即可

第二问可以按照每条边分别计算对答案的贡献

NOIP2013 货车运输

https://www.luogu.org/problemnew/show/P1967

首先找出最大生成树

然后问题变成询问树上一条路径的最小值

用树上倍增解决

NOIP2015 运输计划

https://www.luogu.org/problemnew/show/P2680

先二分答案,假设二分的答案是t

长度小于等于t的路径可以直接排除,接下来就是在剩余路径的交集中找一条权值最大的路径进行改造

使用树上差分可以快速求出交集

NOIP2012 疫情控制

https://www.luogu.org/problemnew/show/P1084

先二分答案

可以看出让所有的军队尽量向上走一定是最优的。可以倍增求出所有的军队在mid的时间里最多走到哪个点。

对于所有走不到根的军队,它们就只能停在那里了。对于所有走到根之后还有剩余时间的军队,可以继续走到根的别的儿子上,这些军队成为可以调动的军队。

枚举根的每一个儿子,如果这个儿子所代表的子树已经被控制了,即子树中所有走不到根的军队已经可以控制了这个子树,就不用管它。

如果它代表的子树没有被控制(注意这里不包括经过这个子树走到根的点),那么称这个点为需要调入的点。

所有可调动的军队都有一个剩余时间,所有需要调入的点都有一个需要时间(即根到儿子的边的权),将这两种点分别从小到大排序,贪心地分配,就可以达到目的。

需要注意的一点是,所有能走到根的军队一定是从根的某一个儿子走上来的,如果再让这个军队调去这个儿子的话,不能计算时间。具体做法是从小到大排序后,如果当前军队走上来的那个点没有被控制的话,就让这支军队去控制它走上来的那个点,否则的话,让它去控制它能控制的最小的点。

NOIP2016 天天爱跑步

https://www.luogu.org/problemnew/show/P1600

将每条路径按照lca拆成两条链,考虑自下而上的那条链,设它为u->v

设di为点i的深度,那么路径上的点必须满足du-di=wi,即di+wi=du才可以收到u->v的贡献,问题转化成支持以下两种操作:1.给一条路径上每个点加入一个数x 2.查询一个点上有多少个di+wi

先用差分转化一下,将操作1改为在u处插入一个数x,在v的父亲处删除一个数x,那么操作2就变成了子树询问

通过dfs序将子树操作转化为序列操作,这时候可以使用可持久化数据结构来实现

如果不使用可持久化数据结构,就考虑离线,先把所有操作预处理出来,按照dfs序顺推,每到一个点就计算该点对应的询问

自上而下的那条链可以用类似方法处理

bzoj1787 紧急集合

http://www.lydsy.com/JudgeOnline/problem.php?id=1787

求出三个点两两lca,其中有两个相同,答案为另一个

codeforces 519E

http://codeforces.com/problemset/problem/519/E

设询问的点为A和B,分四种情况讨论

  • A=B:答案为n

  • A和B距离为奇数:答案为0

  • A和B到他们最近公共祖先P的距离相等:则答案为n减去A和B对应的P的儿子的子树大小

  • 其他情况:假设A的深度更大,找到A和B的中点M,答案为M的子树大小减去A对应的M的儿子的子树大小

货车运输标程

2018-02-06 13:48:32 By youyl
#include<cstdio>
#include<algorithm>
using namespace std;
struct edge
{
    int fir,sec,dis;
}edg[200000];
inline bool cmp(edge x,edge y)
{
    return x.dis>y.dis;
}
struct node
{
    int to,next,dis;
}g[220000];
int ed,st[120000];
int fat[120000];
inline int fnd(int x)
{
    if(fat[x]==x)return x;
    return fat[x]=fnd(fat[x]);
}
inline void add(int x,int y,int z)
{
    ed++;
    g[ed].next=st[x];
    g[ed].to=y;
    g[ed].dis=z;
    st[x]=ed;
}
int n,m,q,x1,x2,vis[120000];
int par[120000][20];
int val[120000][20],dep[120000];
const int inf=(int)1e8;
inline void dfs(int x,int fa,int de)
{
    vis[x]=1;
    dep[x]=de;
    par[x][0]=fa;
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            val[g[i].to][0]=g[i].dis;
            dfs(g[i].to,x,de+1);
        }
    }
}
inline void doubling()
{
    for (int i=0;i<=18;i++)
    {
        val[0][i]=inf;
    }
    for (int i=1;i<=18;i++)
    {
        for (int j=1;j<=n;j++)
        {
            par[j][i]=par[par[j][i-1]][i-1];
            val[j][i]=min(val[j][i-1],val[par[j][i-1]][i-1]);
        }
    }
}
inline int query(int x,int y)
{
    int ans=inf;
    if(dep[x]>dep[y])swap(x,y);
    for (int i=18;i>=0;i--)
    {
        if(dep[par[y][i]]>=dep[x])
        {
            ans=min(ans,val[y][i]);
            y=par[y][i];
        }
    }
    if(x==y)
    {
        return ans;
    }
    for (int i=18;i>=0;i--)
    {
        if(par[x][i]!=par[y][i])
        {
            ans=min(ans,val[x][i]);
            ans=min(ans,val[y][i]);
            x=par[x][i];
            y=par[y][i];
        }
    }
    if(x==y)return ans;
    ans=min(ans,val[x][0]);
    ans=min(ans,val[y][0]);
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&edg[i].fir,&edg[i].sec,&edg[i].dis);
    }
    sort(edg+1,edg+m+1,cmp);
    for (int i=1;i<=n;i++)
    {
        fat[i]=i;
    }
    for (int i=1;i<=m;i++)
    {
        if(fnd(edg[i].fir)!=fnd(edg[i].sec))
        {
            add(edg[i].fir,edg[i].sec,edg[i].dis);
            add(edg[i].sec,edg[i].fir,edg[i].dis);
            fat[fnd(edg[i].fir)]=fnd(edg[i].sec);
        }
    }
    for (int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            val[i][0]=inf;
            dfs(i,0,1);
        }
    }
    doubling();
    scanf("%d",&q);
    while (q--)
    {
        scanf("%d %d",&x1,&x2);
        if(fnd(x1)!=fnd(x2))
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",query(x1,x2));
        }
    }
    return 0;
}

2018 Winter Series 3rd 题解和标程

2018-02-06 12:19:28 By youyl

题解

印章

题意:用一个网格图形去覆盖另一个网格图图形并且不能旋转,重叠和溢出

考虑到方格纸最左上角的黑点和印章最左上角的墨水必然是重合的

将印章里的墨水点存在一个链表里,直接暴力依次覆盖方格纸上的黑点,并把覆盖过的黑点清空

复杂度是$O(nm)$

膜法师

题意:给出一个序列,有些节点是特殊的但是你不知道,每次你可以花费一定代价询问一段连续的区间中特殊点数量的奇偶性,问能够必然确定特殊点的最小花费。

考虑相邻两个数之间的缝隙。(包括第一个数之前和最后一个数之后)

每个询问都是在询问两个缝隙之间的奇偶性。

实际上题目要求的就是你最后必须能推导出每个数前后缝隙之间的奇偶性。

考虑将每个缝隙看作是一个点,询问就是在两个点之间建边,如果两个缝隙对应的点相邻,那么他们之间的奇偶性就可以得到。

所以问题转化成了最小生成树,边权就是对应的询问花费

看电影

题意:给出一个序列,每个节点有一种颜色,每种颜色有对应的权值,要求找出一个区间,使得区间内只出现过一次的颜色的权值之和最大。

先预处理出对于每个节点,下一个跟他相同颜色的点的位置,定义它为$nxt[i]$

然后枚举最后选的那个区间的左端点$L$,用一颗线段树记录对于每个$R$,这个区间的得分是多少

当左端点$L$向右移时,设当前左端点颜色为$i$,相当于把以$L$到$nxt[L]-1$为结尾的区间的得分减$w[i]$,再把以$nxt[L]$到$nxt[nxt[L]]-1$为结尾的区间的得分加$w[i]$

然后查询以$L$到$n$为结尾的区间的得分的最大值,得到$L$为开头的所有区间的得分的最大值

复杂度为$O(n\log n)$

标程

印章

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<pair<int,int> >adj;
int n,m,a,b,T;
bool mp[1200][1200];
char str[1200];
inline bool solve(int x,int y)
{
    if(adj.size()==0)return true;
    int sx=x-adj[0].first,sy=y-adj[0].second;
    for (int i=0;i<adj.size();i++)
    {
        int tx=sx+adj[i].first;
        int ty=sy+adj[i].second;
        if(tx<1||tx>n||ty<1||ty>m)return true;
        if(!mp[tx][ty])return true;
        mp[tx][ty]=false;
    }
    return false;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(mp,0,sizeof(mp));
        adj.clear();
        scanf("%d %d %d %d",&n,&m,&a,&b);
        for (int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for (int j=1;j<=m;j++)
            {
                if(str[j]=='x')mp[i][j]=true;
            }
        }
        for (int i=1;i<=a;i++)
        {
            scanf("%s",str+1);
            for (int j=1;j<=b;j++)
            {
                if(str[j]=='x')adj.push_back(make_pair(i,j));
            }
        }
        int fl=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                if(mp[i][j])
                {
                    if(solve(i,j))
                    {
                        printf("NIE\n");
                        fl=1;break;
                    }
                }
            }
            if(fl==1)break;
        }if(fl==0)printf("TAK\n");
    }
    return 0;
}

膜法师

#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
int cnt,x1,x2;
pair<int,pair<int,int> >edge[2200000];
int fat[2010];
inline int fnd(int x)
{
    if(fat[x]==x)return x;
    return fat[x]=fnd(fat[x]);
}
int n,cnt2;
long long ans;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        fat[i]=i;
        for (int j=i;j<=n;j++)
        {
            scanf("%d",&x1);
            cnt++;
            edge[cnt]=make_pair(x1,make_pair(i,j+1));
        }
    }
    fat[n+1]=n+1;
    sort(edge+1,edge+cnt+1);
    for (int i=1;i<=cnt;i++)
    {
        x1=edge[i].second.first;
        x2=edge[i].second.second;
        if(fnd(x1)!=fnd(x2))
        {
            fat[fnd(x1)]=fnd(x2);
            cnt2++;
            ans+=edge[i].first;
            if(cnt2==n)break;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

看电影

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int f[1200000];
int w[1200000];
int next[1200000];
int las[1200000];
struct segment
{
    int lef[5200000];
    int rig[5200000];
    long long val[5200000];
    long long laz[5200000];
    inline void update(int x)
    {
        val[x]=max(val[x*2],val[x*2+1]);
    }
    inline void upgrade(int x,long long va)
    {
        laz[x]+=va;
        val[x]+=va;
    }
    inline void pushdown(int x)
    {
        upgrade(x*2,laz[x]);
        upgrade(x*2+1,laz[x]);
        laz[x]=0;
    }
    inline void build(int x,int le,int ri)
    {
        lef[x]=le;
        rig[x]=ri;
        val[x]=0;
        laz[x]=0;
        if(le==ri)return;
        build(x*2,le,(le+ri)/2);
        build(x*2+1,(le+ri)/2+1,ri);
    }
    inline void edit(int x,int le,int ri,long long va)
    {
        if(le>ri)return;
        if(le<=lef[x]&&ri>=rig[x])
        {
            upgrade(x,va);
            return;
        }
        pushdown(x);
        if(le<=rig[x*2])edit(x*2,le,ri,va);
        if(ri>rig[x*2])edit(x*2+1,le,ri,va);
        update(x);
    }
    inline long long query(int x,int le,int ri)
    {
        if(le>ri)return 0;
        if(le<=lef[x]&&ri>=rig[x])
        {
            return val[x];
        }
        long long summ=0;
        if(le<=rig[x*2])summ=max(summ,query(x*2,le,ri));
        if(ri>rig[x*2])summ=max(summ,query(x*2+1,le,ri));
        return summ;
    }
}sgt;
long long ans;
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&w[i]);
        las[i]=n+1;
    }
    for (int i=n;i>=1;i--)
    {
        next[i]=las[f[i]];
        las[f[i]]=i;
    }
    sgt.build(1,1,n);
    for (int i=1;i<=m;i++)
    {
        if(las[i]!=n+1)
        {
            sgt.edit(1,las[i],next[las[i]]-1,w[i]);
        }
    }
    for (int i=1;i<=n;i++)
    {
        ans=max(ans,sgt.query(1,i,n));
    //    printf("%d %lld\n",i,ans);
        if(next[i]!=n+1)
        {
            sgt.edit(1,i,next[i]-1,-w[f[i]]);
            sgt.edit(1,next[i],next[next[i]]-1,w[f[i]]);
        }
        else
        {
            sgt.edit(1,i,n,-w[f[i]]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Simulation4题解与标程

2018-01-24 13:00:18 By youyl

设这个图的点集为G。

考虑一个点X,设与他相邻的点集为S,令V=G-X-S。

将V划分联通块,设这些联通块为G1,G2,……Gk,设S中与Gi相邻的点集为Si,那么如果在Si中找到了两个不相邻的点,就是有答案了。

因为可以如此构造:把Si和和Gi合并成Ti,在Ti中找到这两个不相邻的点之间的最短路径,最短路径加上点V就是我们需要的答案。

接下来的解法很显然:

枚举每个点,将他设为点X,然后按照上面的方法处理,通过合适的实现方式可以做到O(nm)。

灯泡

可以很容易发现a组b组分别考虑的时候,必然是从大到小选择。之后有很多种方法可以通过这题。

辐射

考虑一个辐射源对其他点的贡献,就是若干个正方形叠加在一起。 如:

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 2 2 2 1 0
0 1 2 3 2 1 0
0 1 2 2 2 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

考虑每个正方形,一个通用的思路就是差分:

0 0 0 0 0 0 0
0 1 0 0 0 0 -1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 -1 0 0 0 0 1

然后叠加之后就是:

0 0 0 0 0 0 0
0 1 0 0 0 0 -1
0 0 1 0 0 -1 0
0 0 0 1 -1 0 0
0 0 0 -1 1 0 0
0 0 -1 0 0 1 0
0 -1 0 0 0 0 1

所以思路很简单,二维差分,按主对角线和副对角线分别处理即可。主要需要处理的是边界上的细节。

标程 环:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector> 
using namespace std;
struct node
{
    int to,next;
}g[220000];
int ed,st[2200];
bool mp[1200][1200];
inline void add(int x,int y)
{
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    st[x]=ed;
}
int n,m,x1,x2;
vector<int>flg,flg2;
int adj[2200],cmp[2200],tag[2200],tim;
inline void dfs(int x)
{
    cmp[x]=1;
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(adj[g[i].to]==1&&tag[g[i].to]!=tim)
        {
            tag[g[i].to]=tim;
            flg2.push_back(g[i].to);
        }
        if(adj[g[i].to]==0&&cmp[g[i].to]==0)
        {
            dfs(g[i].to);
        }
    }
}
inline bool solve(int x)
{
    memset(adj,0,sizeof(adj));
    memset(cmp,0,sizeof(cmp));
    for (int i=st[x];i!=0;i=g[i].next)
    {
        adj[g[i].to]=1;
    }
    adj[x]=2;
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if(adj[i]==0&&cmp[i]==0)
        {
            cnt++;
            tim++;
        //    flg.clear();
            flg2.clear();
            dfs(i);
        //    sort(flg.begin(),flg.end());
    //        for (int j=0;j<flg.size();j++)
    //        {
    //            if(j==0||flg[j]!=flg[j-1])flg2.push_back(flg[j]);
    //        }
            for (int j=0;j<flg2.size();j++)
            {
                for (int k=j+1;k<flg2.size();k++)
                {
                    if(mp[flg2[j]][flg2[k]]==0)
                    {
                        return true;
                    }
                }
            }
        }
    }return false;
} 
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d %d",&x1,&x2);
        add(x1,x2);
        add(x2,x1);
        mp[x1][x2]=1;
        mp[x2][x1]=1;
    }
    for (int i=1;i<=n;i++)
    {
        if(solve(i))
        {
            printf("yes\n");
            return 0;
        }
    }
    printf("no\n");
    return 0;
}

灯泡:

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double ans,a[120000],b[120000]; 
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf %lf",a+i,b+i);
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    reverse(a+1,a+n+1);
    reverse(b+1,b+n+1);
    double sa=0,sb=0;
    int timb=1;
    for (int i=1;i<=n;i++)
    {
        sa+=a[i];
        while (timb<=n&&min(sa,sb)-timb-i+1<min(sa,sb+b[timb])-timb-i)
        {
            sb+=b[timb];
            timb++;
        }//printf("%d\n",timb);
        ans=max(ans,min(sa,sb)-timb+1-i);
    }
    printf("%.4lf\n",ans);
    return 0;
}

辐射:

#include<cstdio>
#include<algorithm>
using namespace std;
int w,h,n,q;
struct node
{
    long long a[6000000];
    long long &operator()(int x,int y)
    {
        return a[(x-1)*h+y];
    }
}posdia,negdia,val;
int x1,x2,y1,y2;
long long row[3000000];
long long col[3000000];
inline void updatepos(int X1,int Y1,int X2,int Y2,int step)
{
    if(X1<1&&Y1<1)
    {
        int m=min(1-X1,1-Y1);
        val(1,1)+=m*step;
        X1+=m;
        Y1+=m;
    }
    if(X1<1)
    {
        int m=1-X1;
        col[Y1]+=step;
        col[Y1+m]-=step;
        X1+=m;
        Y1+=m;
    }
    if(Y1<1)
    {
        int m=1-Y1;
        row[X1]+=step;
        row[X1+m]-=step;
        X1+=m;
        Y1+=m;
    }
    posdia(X1,Y1)+=step;
    if(X2<w&&Y2<h)posdia(X2+1,Y2+1)-=step;
}
inline void updateneg(int X1,int Y1,int X2,int Y2,int step)
{
    if(Y2>h)
    {
        int m=Y2-h;
        X1+=m;
        Y2-=m;
    }
    if(X1<1)
    {
        int m=1-X1;
        col[Y2-m+1]-=step;
        if(Y2+1<=h)col[Y2+1]+=step;
        X1+=m;
        Y2-=m;
    }
    if(X1<=w&&Y2>=1)negdia(X1,Y2)-=step;
    if(X2>w)
    {
        int m=X2-w;
        X2-=m;
        Y1+=m;
    }
    if(Y1<1)
    {
        int m=1-Y1;
        row[X2-m+1]-=step;
        if(X2+1<=w)row[X2+1]+=step;
        X2-=m;
        Y1+=m;
    }
    if(1<=X2+1&&X2+1<=w&&1<=Y1-1&&Y1-1<=h)negdia(X2+1,Y1-1)+=step;
}
inline void scandia()
{
    for (int i=1;i<=w;i++)
    {
        for (int j=1;j<=h;j++)
        {
            if(i!=1&&j!=1)posdia(i,j)+=posdia(i-1,j-1);
            if(i!=1&&j!=h)negdia(i,j)+=negdia(i-1,j+1);
        }
    }
}
inline void scanside()
{
    for (int i=2;i<=w;i++)
    {
        row[i]+=row[i-1];
    }
    for (int i=2;i<=h;i++)
    {
        col[i]+=col[i-1];
    }
}
inline void together()
{
    for (int i=1;i<=w;i++)
    {
        val(i,1)+=row[i];
    }
    for (int i=1;i<=h;i++)
    {
        val(1,i)+=col[i];
    }
    for (int i=1;i<=w;i++)
    {
        for (int j=1;j<=h;j++)
        {
            val(i,j)+=negdia(i,j);
            val(i,j)+=posdia(i,j);
        }
    }
}
inline void scan()
{
    for (int i=1;i<=w;i++)
    {
        for (int j=1;j<=h;j++)
        {
            if(j!=1)val(i,j)+=val(i,j-1);
            if(i!=1)val(i,j)+=val(i-1,j);
            if(i!=1&&j!=1)val(i,j)-=val(i-1,j-1);
        }
    }
}
inline void print()
{
    for (int i=1;i<=w;i++)
    {
        for (int j=1;j<=h;j++)
        {
            printf("%lld ",val(i,j));
        }printf("\n");
    }
}
inline long long divid(long long ss,long long area)
{ 
    //printf("%lld %lld\n",ss,area);
    long long ans=ss/area;
    if((ss%area)*2>=area)
    {
        ans++;
    }
    return ans;
}
int a1,b1,X,Y;
int main()
{
    scanf("%d %d",&w,&h);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d %d %d %d",&X,&Y,&a1,&b1);
        int d=(a1-1)/b1;
        x1=X-d;
        x2=X+d+1;
        y1=Y-d;
        y2=Y+d+1;
        int r=a1%b1;
        if(r!=0)
        {
            val(max(1,x1),max(1,y1))+=r;
            if(x2<=w)val(x2,max(1,y1))-=r;
            if(y2<=h)val(max(1,x1),y2)-=r;
            if(x2<=w&&y2<=h)val(x2,y2)+=r;
            x1++;
            x2--;
            y1++;
            y2--;
        }
        if(a1>=b1)
        {
            updatepos(x1,y1,x2,y2,b1);
            updateneg(x1,y1,x2,y2,b1);
        }
    }
//    print();
//    print();
    scandia();
//    print();
    scanside();
//    print();
    together();
    scan();
//    print();
    scan();
    scanf("%d",&q);
    while (q--)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        long long tmp=val(x2,y2);
        if(x1!=1&&y1!=1)tmp+=val(x1-1,y1-1);
        if(x1!=1)tmp-=val(x1-1,y2);
        if(y1!=1)tmp-=val(x2,y1-1);
    //    printf("%lld\n",(long long)((tmp*1.0)/(((long long)x2-x1+1)*(y2-y1+1))+0.5));
        printf("%lld\n",divid(tmp,(x2-x1+1)*(y2-y1+1)));
    }
    return 0;
}

对于Simulation3第三题“陷阱”的补充说明

2018-01-24 08:21:59 By youyl

感觉昨天讲的不太清楚,补充说明一些:

以下讨论的前提是以陷阱房为根将整个树提起来。

从subtask2开始考虑:

考虑一个点的权值,我们已经定义了一个点的权值是老鼠走到这个点的情况下的答案,那么考虑哪些点的答案能被唯一确定,那么就是叶子节点和那些儿子数量为1的节点,他们的权值就是从根到他的路径上每个点的儿子数量之和,因为这条路径上每个点向下的路径要么需要被堵,要么需要被疏通来让老鼠通过。剩余的点的权值只和他们的儿子有关,因为管理员一定会堵住最大权值的儿子,那么一个点的权值就是他第二大儿子的权值。整个问题的答案就是老鼠出发点的权值(很明显我们这里没讨论到根节点,所以用来计算节点权值的搜索应当从老鼠出发点开始)。

再考虑满分做法:

考虑从老鼠出发点到根的路径,管理员不需要对这条路径做任何操作,所以在计算权值的时候需要忽略这些边的贡献。然后发现我们现在需要对下挂在这条路径上除了根节点的点上的子树都计算出权值,然后考虑对于这样的一个子树,计算他的权值的时候我们实际上忽略了在这条路径上他下面的一些需要堵住的路贡献的权值。这样就如同标程所写的那样,y记录需要堵住的路径的数量,x记录老鼠向上走了几步,也就是给了管理者几次机会。如果需要堵住的路径数量超过了正在二分的步数或者管理者的机会不够用了,就要向上二分。如果所有的子树都被遍历到了,就要向下二分。

Simulation3题解与标程

2018-01-23 18:30:40 By youyl

追逐

50分:

考虑一条路径上的连续的三个点,假设路径从V走到X走到T。定义N(X)为X所有邻居的铁球数总和,那么在X处丢下磁铁的收益就是N(X)-F(V),无论别的磁铁丢在哪里。

证明:

考虑X的邻居,如果他们不是V也不是T,那么必然对答案有贡献,因为逃亡者一定碰不到而追杀者一定碰得到。T处的铁球会被追杀者碰到,但是因为X处放了磁铁,所以逃亡者不会碰到。V处的铁球的收益只会被前面的磁铁影响而不会被X处磁铁影响。

这样可以枚举起点,然后用堆存储路径上的每个点的收益,最终的复杂度是O(n n v * log(n))

100分:

考虑使用动态规划,每个点保存两个数组,分别表示向下面走的和从下面来的两条路径放了若干个磁铁的收益。计算答案的时候合并路径即可。 需要注意的边界情况较多,如:两条路径来自同一子树,答案路径只由一条路径构成等。

回文串

35分:

考虑动态规划。

将问题考虑为每次截取字符串一对相等的前缀和后缀,问最多截取次数。

Dp[i]为原字符串正好截取了前i个和后i个字符。转移枚举截取长度。复杂度是立方级的。

60分:

考虑贪心。

可以发现最优策略一定是每次截下尽可能短的相同的前后缀。

证明:

假设有两个分解CADBC和EDE。现在需要证明如果存在CADBC,EDE一定不是最优解。

分两种情况讨论:

B的长度大于等于C的长度。

这个时候E=CXC,X可能为空串。把E分为CXC一定是更优解。

B的长度小于C的长度。

因为CA=BC且B的长度小于C的长度,所以C=BC[1],C[1]是C的某个前缀。

可以依此类推C=BC[1]=BBC[2]=BBBC[3]……直到BB…BC[k],使得B的长度大于等于C[k]的长度。

这时C[k]既是C的前缀也是C的后缀,因此也是E的前缀和后缀。

所以存在E=C[k]XC[k]可以构成更优解。

一个直观的想法就是从原字符串两端枚举,每次判断前后缀是否相同。

判断的时间复杂度是线性的,总复杂度是平方级的。

100分:

60分做法的瓶颈在于判断前后缀是否相等,这可以使用字符串哈希处理,每次判断是常数时间的,总复杂度就是线性的。

陷阱

Subtask1:

考虑到因为可以不操作,所以所有的堵路操作一定在所有的清理操作之前,因为如果有一个堵路操作在清洁操作之后,那么他可以交换这两个操作的顺序。

进一步观察可以发现,老鼠最后一定会被堵住。在堵住老鼠之前管理者只会进行堵路操作,堵住老鼠之后管理者可以先把老鼠到陷阱的路径上的向外的路全堵住,然后开始清理。老鼠一定会走向陷阱。

可以暴力枚举堵住哪些路。

Subtask2:

将陷阱房提根。可以发现老鼠出发点一定深度为1(根的深度为0),而且他一定会往深处走。

可以发现在老鼠未被堵住之前,管理者堵住的走廊一定和老鼠所在位置相邻,而且一定会堵住老鼠的最优解。在老鼠被堵住之后,管理者可以很容易构造出通向陷阱的路径。定义一个点的权值为老鼠向下走到这个点的情况下答案是多少,接下来就可以很容易的计算出每个点的权值,老鼠起始位置的权值就是答案。

100分:

考虑一般情况,还是将陷阱房提根。

考虑老鼠的起始位置通向根的路径,管理者不会去堵这些路。考虑这条路径,上挂的子树,可以发现最后老鼠必然是选择一个子树进去,然后卡住,最后被放到陷阱。

考虑二分答案,二分操作者需要多少步进行步,然后自下而上扫描,判断每个子树能否满足条件。复杂度为O(n log n)

标程

追逐:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int ed,st[120000];
struct node
{
    int to,next;
}g[220000];
inline void addedge(int x,int y)
{
    ed++;
    g[ed].next=st[x];
    g[ed].to=y;
    st[x]=ed;
}
int n,v,x,y;
long long best,p[120000],tot[120000];
long long up[120000][120],down[120000][120];
inline void solve2(int x,int ch)
{
    for (int i=0;i<=v;i++)
    {
        best=max(best,up[x][i]+down[ch][v-i]);
        best=max(best,down[x][i]+up[ch][v-i]);
        if(i!=v)
        {
            best=max(best,up[x][i]+down[ch][v-i-1]+tot[ch]-p[x]);
            best=max(best,down[x][i]+up[ch][v-i-1]+tot[x]-p[ch]);
        }
    }
}
inline void update(int x,int ch)
{
    for (int i=0;i<=v;i++)
    {
        up[x][i]=max(up[x][i],up[ch][i]);
        down[x][i]=max(down[x][i],down[ch][i]);
    }
    for (int i=1;i<=v;i++)
    {
        up[x][i]=max(max(up[x][i-1],up[x][i]),up[ch][i-1]+tot[x]-p[ch]);
        down[x][i]=max(max(down[x][i-1],down[x][i]),down[ch][i-1]+tot[ch]-p[x]);
    }
}
inline void solve(int x,int fa)
{
    vector<int>adj;
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            adj.push_back(g[i].to);
            solve(g[i].to,x);
        }
    }
    up[x][0]=0;
    for (int i=1;i<=v;i++)
    {
        up[x][i]=tot[x];
    }
    if(adj.size()==0)
    {
        return;
    }
    update(x,adj[0]);
    for (int i=1;i<adj.size();i++)
    {
        solve2(x,adj[i]);
        update(x,adj[i]);
    }
    best=max(best,up[x][v]);
    best=max(best,down[x][v]);
    if(v>0)best=max(best,down[x][v-1]+tot[x]);
    //printf("v:%d\n",x);
}
int main()
{
    scanf("%d %d",&n,&v);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&p[i]);
    }
    for (int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        addedge(x,y);
        addedge(y,x);
        tot[x]+=p[y];
        tot[y]+=p[x];
    }
    solve(1,0);
    printf("%lld\n",best);
    return 0;
}

回文串:

#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1000000007;
const long long mul=131;
char str[1200000];
inline int solve()
{
    int l=strlen(str+1);
    int lb=1,rb=l,cnt=0;
    long long hashl=0,hashr=0,mult=1;
    while (lb<rb)
    {
        hashr+=mult*(str[rb]-'a'+1)%mod;
        hashr%=mod;
        hashl*=mul;hashl%=mod;
        hashl+=(str[lb]-'a'+1);
        hashl%=mod;
        if(hashl==hashr)
        {
            hashl=0;
            hashr=0;
            mult=1;
            cnt+=2;
        }
        else
        {
            mult*=mul;
            mult%=mod;
        }
        lb++;
        rb--;
    }
    if(lb==rb)cnt++;
    if(lb!=rb&&hashl!=0)cnt++;
    return cnt;
}
int T;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",str+1);
        printf("%d\n",solve());
    }
    return 0;
}

陷阱:

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>adj[1200000];
int parent[1200000];
int weight[1200000];
vector<pair<int,int> >subtrees;
int ispath[1200000];
int root,m,n;
int dfs1(int x,int fa)
{
    int fati=-1;
    for (int i=0;i<adj[x].size();i++)
    {
        if(adj[x][i]==fa)fati=i;
    }
    if(fati!=-1)
    {
        adj[x].erase(adj[x].begin()+fati);
    }
    parent[x]=fa;
    int step=-1;
    if(x==m)
    {
        step=0;
    }
    for (int i=0;i<adj[x].size();i++)
    {
        step=max(step,dfs1(adj[x][i],x));
    }
    ispath[x]=step;
    if(step==-1)
    {
        return step;
    }
    else
    {
        return step+1;
    }
}
void dfs2(int x,int c)
{
    if(adj[x].size()==0)
    {
        weight[x]=c;
        return;
    }
    if(ispath[x]==-1)
    {
        int cur=c+adj[x].size();
        for (int i=0;i<adj[x].size();i++)
        {
            dfs2(adj[x][i],cur);
        }
        if(adj[x].size()==1)
        {
            weight[x]=c+1;
            return;
        }
        int best=-1;
        int sbest=-1;
        for (int i=0;i<adj[x].size();i++)
        {
            if(weight[adj[x][i]]>best)
            {
                sbest=best;
                best=weight[adj[x][i]];
                continue;
            }
            if(weight[adj[x][i]]>sbest)
            {
                sbest=weight[adj[x][i]];
            }
        }
        weight[x]=sbest;
        return;
    }
    int cur=c+adj[x].size()-1;
    if(x==root)
    {
        cur=0;
    } 
    if(x==m)
    {
        cur++;
    }
    for (int i=0;i<adj[x].size();i++)
    {
        dfs2(adj[x][i],cur);
    }
    if(x==root)return;
    for (int i=0;i<adj[x].size();i++)
    {
        if(ispath[adj[x][i]]==-1)
        {
            subtrees.push_back(make_pair(ispath[x],weight[adj[x][i]]));
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&root,&m);
    for (int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int pathl=dfs1(root,-1);
    dfs2(root,0);
    sort(subtrees.begin(),subtrees.end());
    int lef=0,rig=n;
    while(lef<rig)
    {
        int mid=(lef+rig)/2;
        int x=0,y=0,pt=0;
        for (int i=0;i<pathl;i++)
        {
            if(pt>=subtrees.size())
            {
                rig=mid;
                break;
            }
            x++;
            int ydelta=0;
            while(pt<subtrees.size()&&subtrees[pt].first<=i)
            {
                if(subtrees[pt].second+y>mid)
                {
                    ydelta++;
                    x--;
                }
                pt++;
            }
            y+=ydelta;
            if(x<0||y>mid)
            {
                lef=mid+1;
                break;
            }
        }
    }
    printf("%d\n",lef);
    return 0;
}
共 8 篇博客