NOIP2017提高组 模拟赛19（总结）

NOIP2017提高组 模拟赛19（总结）

第一题 数组 （贪心）

【题目描述】

【解题思路】

　　若∑ni=1ai可以被n整除，那么答案就是n，否则是n-1（等于删掉一个数，使得剩下的和可以被n-1整除）。

【代码】

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

int n;
ll s;

int main()
{
    freopen("2006.in","r",stdin);
    freopen("2006.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a; scanf("%d",&a);
        s+=a;
    }
    if(!(s%n)) printf("%d\n",n); else printf("%d\n",n-1);
    return 0;
}

第二题 歌词 （AC自动机）

【题目描述】

【解题思路】

　　典型的AC自动机，不过空间有点悬（可以开map……）
　　用歌词建AC自动机（用歌建的话会MLE），用歌去匹配，每匹配到一个地方就标记加+1。最后dfs整棵fail树，将儿子的标记加到父亲上。最后输出每个歌词的匹配数（建AC自动机时，在记下最后一个单词在AC自动机的位置，歌词的匹配数就是AC自动机的位置的匹配数）。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const int Ln=1800000;
int n,m,root,cnt;
int ne[Ln],to[Ln],h[Ln],tt;
int q[Ln],kp[550];
ll sum[Ln];
char st[50050];
struct data { int fail,fa,r[63]; } T[Ln];

int gs(char ch)
{
    if(ch=='-') return 62;
    if('0'<=ch && ch<='9') return ch-'0';
    if('A'<=ch && ch<='Z') return ch-'A'+10;
    if('a'<=ch && ch<='z') return ch-'a'+10+26;
}

void addtrie(int bel)
{
    int cl=strlen(st),now=root;
    for(int i=1;i<=cl;i++)
    {
        int cd=gs(st[i-1]);
        if(!T[now].r[cd]) { cnt++; T[cnt].fa=now; T[now].r[cd]=cnt; }
        now=T[now].r[cd];
    }
    kp[bel]=now;
}

void addedge(int a,int b) { to[++tt]=b; ne[tt]=h[a]; h[a]=tt; }

void buildfail()
{
    int head=1,tail=1; q[1]=root;
    while(head<=tail)
    {
        int fnow=q[head++];
        for(int i=0;i<63;i++)
        if(T[fnow].r[i])
        {
            int v=T[fnow].r[i];
            int k=T[fnow].fail;
            bool flag=(fnow!=root);
            while(!T[k].r[i])
            {
                if(k==root) { flag=0; break; }
                k=T[k].fail;
            }
            if(flag) T[v].fail=T[k].r[i]; else T[v].fail=root;
            q[++tail]=v;
            addedge(T[v].fail,v);
        }
    }
}

void dfs(int x,int fa)
{
    for(int p=h[x];p;p=ne[p])
    {
        int v=to[p];
        dfs(v,x);
        sum[x]+=sum[v];
    }
}

int main()
{
    freopen("2019.in","r",stdin);
    freopen("2019.out","w",stdout);
    scanf("%d",&n); tt=1;
    root=1; cnt=1; T[1].fail=1; T[1].fa=1;
    for(int i=1;i<=n;i++) { scanf("%s",st); addtrie(i); }
    buildfail();
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",st); int cl=strlen(st);
        int now=root;
        for(int j=1;j<=cl;j++)
        {
            int yu=gs(st[j-1]);
            while(now!=root && (!T[now].r[yu])) now=T[now].fail;
            if(T[now].r[yu]) now=T[now].r[yu];
            sum[now]++;
        }
    }
    dfs(root,root);
    for(int i=1;i<=n;i++) printf("%lld\n",sum[kp[i]]);
    return 0;
}

第三题 旅行 （splay优化DP）

【题目描述】

【解题思路】

50%
　　记dp[i]为去了i个目的地，所花的最小天数。
　　可以知道dp[]一定是严格递增的。
　　若加入了景点[L,R]
　　那么设p为dp[p]>=L的最小下标。
　　dp[p]=min(dp[p],L);
　　∵dp[p]>=L　∴dp[p]=L;
　　设q为dp[q]>=R+1的最小下标。
　　j∈[p+1,q-1]　dp[j]=min(dp[j],dp[j-1]+1);
　　∵dp[]一定是严格递增的。　∴dp[j]>dp[j-1]，dp[j]=dp[j-1]+1;
　　时间复杂度：O(n^2)
100%
　　可以发现：dp数组仅仅插入了一个值，把其中的一端集体+1并集体右移了一位，删除了末端的一位。
　　写个splay就好了。
　　插入的话就先找到该插入的位置（严格递增的，并不需要记是第几位），连边。
　　集体+1就打个懒惰标记，down下去。
　　删除的话就把它旋到末端，cut掉就行。
　　最后dfs整棵splay树，统计有几个是不为无穷大的。（一开始所有值为无穷大）
　　我写前驱后继写炸了，换了一种写法才A。（我也不知道为什么）

【代码】

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

const int oo=1e9+10;
const int N=610050;
int n,cnt,sum;
struct tree
{
    tree *f,*c[2];
    int val,lz;
    int d() { return (f->c[1]==this); }
    void sc(tree *x,int d) { (c[d]=x)->f=this; }
} nil[N],*root,*stack[N];

tree *newtree(int vg)
{
    nil->val=nil->lz=0;
    nil->c[0]=nil->c[1]=nil->f=nil;
    nil[++cnt]=nil[0];
    nil[cnt].val=vg;
    return nil+cnt;
}

void down(tree *x)
{
    if(x==nil) return;
    if(x->lz!=0)
    {
        if(x->c[0]!=nil)
        {
            x->c[0]->lz+=x->lz;
            x->c[0]->val+=x->lz;
        }
        if(x->c[1]!=nil)
        {
            x->c[1]->lz+=x->lz;
            x->c[1]->val+=x->lz;
        }
        x->lz=0;
    }
}

void rotate(tree *x)
{
    int d=x->d();
    tree *y=x->f;
    y->sc(x->c[!d],d);
    if(y->f==nil) root=x,x->f=nil; else y->f->sc(x,y->d());
    x->sc(y,!d);
}

void splay(tree *x)
{
    int hy=1; stack[hy]=x;
    for(;stack[hy]->f!=nil;hy++) stack[hy+1]=stack[hy]->f;
    for(int i=hy;i>=1;i--) down(stack[i]);
    for(tree *y;x->f!=nil;)
    {
        y=x->f;
        if(y->f!=nil)
        (y->d()^x->d())?rotate(x):rotate(y);
        rotate(x);
    }
}

tree *build(int L,int R)
{
    if(L>R) return nil;
    int Mid=(L+R)>>1;
    tree *ty=newtree(oo);
    ty->sc(build(L,Mid-1),0);
    ty->sc(build(Mid+1,R),1);
    return ty;
}

void cut(tree *x)
{
    for(;;)
    {
        if(x->c[0]!=nil)
        {
            down(x->c[0]);
            rotate(x->c[0]);
        } else
        if(x->c[1]!=nil)
        {
            down(x->c[1]);
            rotate(x->c[1]);
        } else
        {
            x->f->sc(nil,x->d());
            splay(x->f);
            return;
        }
    }
}

void dfs(tree *x)
{
    down(x);
    if(x==nil) return;
    if(x->val>0 && x->val<oo) sum++; 
    if(x->c[0]!=nil) dfs(x->c[0]);
    if(x->c[1]!=nil) dfs(x->c[1]);
}

void search(int dl)
{
    tree *x,*now=root;
    while(now!=nil)
    {
        if(now->val>=dl)
        {
            x=now;
            now=now->c[0];
        } else now=now->c[1];
        down(now);
    }
    splay(x);
}

int main()
{
    freopen("2020.in","r",stdin);
    freopen("2020.out","w",stdout);
    scanf("%d",&n);
    root=newtree(0);
    root->sc(build(1,n),1);
    for(int i=1;i<=n;i++)
    {
        int dl,dr;
        scanf("%d%d",&dl,&dr);
        search(dl);
        root->val++;
        root->c[1]->val++;
        root->c[1]->lz++;
        tree *now=root->c[0];
        while(now->c[1]!=nil)
        {
            down(now);
            now=now->c[1];
        }
        down(now);

        now->sc(newtree(dl),1);
        splay(now->c[1]);

        search(dr+1);
        root->c[1]->val--;
        root->c[1]->lz--;
        cut(root);
    }
    sum=0; dfs(root);
    printf("%d\n",sum);
    return 0;
}