GDKOI2017模拟赛二

OI 校内赛

【xsy1815】clear - 栈+kmp

题意

给你两个串$A$和$B$，每次在$B$串中从左到右找串$A$，并将该子串删除，直到找不到为止，问你能删几次。
$|A|,|B|\leq 10^7$

分析

肯定是从前往后跑，能合并的就合并。
快速判断能不能合并的方法有：
①栈+kmp
②栈+字符串Hash
③etc

个人觉得那种深度的冥想也可以在打OI的时候使用。
闭上眼睛好好地想想。
（什么玄学的东西qaq）

代码

#include <cstdio>
#include <cstring>
#define F(i,a,b) for (int i=(a);i<=(b);i++)
const int A=524288;
const int B=10000010;
char a[A];
int na;
int nx[A];
char b[B];
int nb;
char c[B];
int nc;
int ex[B];
int cnt;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("A.in","r",stdin);
        freopen("A.out","w",stdout);
    #endif
    scanf("%s",a+1);
    na=strlen(a+1);
    nx[1]=0;
    int j=0;
    F(i,2,na) {
        while (j>0&&a[i]!=a[j+1])
            j=nx[j];
        if (a[i]==a[j+1])
            j++;
        nx[i]=j;
    }
    scanf("%s",b+1);
    nb=strlen(b+1);
    F(i,1,nb) {
        int j=ex[nc];
        while (j>0&&b[i]!=a[j+1])
            j=nx[j];
        if (b[i]==a[j+1])
            j++;
        if (j==na) {
            cnt++;
            F(i,2,na)
                c[nc--]=0;
        }
        else {
            c[++nc]=b[i];
            ex[nc]=j;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

【xsy1820】mst - 最小割

题意

给定一个边带正权的连通无向图$G=(V,E)$，其中$N=|V|$，$M=|E|$，$N$个点从$1$到$N$依次编号，
给定三个正整数$u$，$v$，和$L (u≠v)$，假设现在加入一条边权为$L$的边$(u,v)$，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
数据保证原图为联通图。
$N≤20000$，$M≤200000$，$L≤20000$

分析

什么叫做出现在最小生成树或者最大生成树上。
最小生成树和最大生成树类似，考虑最小生成树。

可能出现，意味着对于任意一个经过$(u,v)$的环，这条边都不是环上的最大值。
即：我们把$u$当做起点，把$v$当做终点，不存在一条路径，满足每一条边的长度都小于$L$。

我们考虑一张图，$n$个点，把小于的边给实质化。
那么，现在要断掉一些小于的边，使得不连通。

最小割！
网络流。

如果既要求最小生成树又要求最大生成树呢？
注意到两个图的边没有交集。
所以最小生成树求一次最小割，最大生成树也求一次最小割就好了。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define fore(k,u) for (int k=hd[u];k>0;k=mp[k].nx)
int rd(void);
const int N=524288;
const int INF=(0x7fffffff)>>1;
int n,m;
struct Ed {
    int u,v,l;
    Ed(int _u=0,int _v=0,int _l=0) {
        u=_u,v=_v,l=_l;
    }
}ed[N];
int u,v,l;
struct G {
    int v,f,nx;
    G(int _v=0,int _f=0,int _nx=0) {
        v=_v,f=_f,nx=_nx;
    }
}mp[N];
int tot,hd[N];
int q[N],qh,qt;
int lev[N];
int ans;
void Ins(int u,int v,int f) {
    mp[++tot]=G(v,f,hd[u]);
    hd[u]=tot;
    mp[++tot]=G(u,f,hd[v]);
    hd[v]=tot;
}
void Build(int kd) {
    tot=1;
    memset(hd,0,sizeof hd);
    F(i,1,m)
        if (kd==(l<ed[i].l))
            Ins(ed[i].u,ed[i].v,1);
}
int BFS(int fs,int ft) {
    memset(q,0,sizeof q);
    qh=qt=0;
    memset(lev,0,sizeof lev);
    q[++qt]=fs;
    lev[fs]=1;
    while (qh!=qt) {
        int x=q[++qh];
        fore(k,x)
            if (mp[k].f>0&&!lev[mp[k].v]) {
                lev[mp[k].v]=lev[x]+1;
                if (mp[k].v==ft)
                    return 1;
                q[++qt]=mp[k].v;
            }
    }
    return 0;
}
int DFS(int x,int ft,int flow) {
    if (x==ft)
        return flow;
    int sum=0;
    fore(k,x)
        if (mp[k].f>0&&lev[mp[k].v]==lev[x]+1) {
            int t=DFS(mp[k].v,ft,min(flow,mp[k].f));
            if (t>0) {
                sum+=t;
                flow-=t;
                mp[k].f-=t;
                mp[k^1].f+=t;
                if (!flow) break;
            }
            else lev[mp[k].v]=INF;
        }
    return sum;
}
int Dinic(void) {
    int mx_flow=0;
    while (1) {
        int tag=BFS(u,v);
        if (!tag)
            break;
        int del=DFS(u,v,INF);
        mx_flow+=del;
    }
    return mx_flow;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("B.in","r",stdin);
        freopen("B.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,m) {
        int u=rd(),v=rd(),l=rd();
        ed[i]=Ed(u,v,l);
    }
    u=rd(),v=rd(),l=rd();
    Build(0);
    ans+=Dinic();
    Build(1);
    ans+=Dinic();
    printf("%d\n",ans);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

【xsy1828】string - 后缀数组+二分

题意

给出$n$个字符串，求出一个最长的串，使得这个串或者这个串的回文在所有$n$个字符串中都出现。
$t≤10$，$n≤200$，$每个字符串长度≤200$

分析

把所有字符串存到一个大的字符串里面。
注意这里的姿势。

int n;
int star[N],fini[N],slen[N];
int own[L];
char s[L];
int len;

中间加若干的连字符。
把原串和反串都加进来。

求SA。
二分答案。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
int rd(void);
const int N=256;
const int L=131072;
int nT;
int n;
int star[N],fini[N],slen[N];
int own[L];
char s[L];
int len;
int sa[L],rk[L],ht[L];
int sum[L],tsa[L],trk[L]; 
int al,ar;
int mid;
int vis[N];
int tot,ind;
void Prework(void) {
    memset(sa,0,sizeof sa);
    memset(rk,0,sizeof rk);
    memset(ht,0,sizeof ht);
    memset(sum,0,sizeof sum);
    memset(tsa,0,sizeof tsa);
    memset(trk,0,sizeof trk);
    int lim=512,p;
    F(i,1,len)
        sum[rk[i]=s[i]]++;
    F(i,1,lim)
        sum[i]+=sum[i-1];
    D(i,len,1)
        sa[sum[rk[i]]--]=i;
    rk[sa[1]]=p=1;
    F(i,2,len) {
        if (s[sa[i]]!=s[sa[i-1]])
            p++;
        rk[sa[i]]=p;
    }
    lim=p;
    for (int j=1;lim!=len;j<<=1) {
        p=0;
        memset(tsa,0,sizeof tsa);
        F(i,len-j+1,len)
            tsa[++p]=i;
        F(i,1,len)
            if (sa[i]>j)
                tsa[++p]=sa[i]-j;
        memset(sum,0,sizeof sum);
        memmove(trk,rk,sizeof rk);
        F(i,1,len)
            sum[rk[i]=trk[tsa[i]]]++;
        F(i,1,lim)
            sum[i]+=sum[i-1];
        D(i,len,1)
            sa[sum[rk[i]]--]=tsa[i];
        rk[sa[1]]=p=1;
        F(i,2,len) {
            if (trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+j]!=trk[sa[i-1]+j])
                p++;
            rk[sa[i]]=p;
        }
        lim=p;
    }
    p=0;
    F(i,1,len) {
        if (p>0)
            p--;
        while (s[i+p]==s[sa[rk[i]-1]+p])
            p++;
        ht[rk[i]]=p;
    }
}
int contain(int xl,int xr,int yl,int yr) {
    return yl<=xl&&xr<=yr;
}
void Add(int x,int lim) {
    int ow=own[x];
    if (!ow)
        return;
    if (vis[ow]==ind)
        return;
    int l=star[ow];
    int r=fini[ow];
    int mid=l+slen[ow];
    if (contain(x,x+lim-1,l,mid-1)||contain(x,x+lim-1,mid+1,r)) {
        vis[ow]=ind;
        tot++;
    }
}
int Check(int lim) {
    tot=ind=0;
    memset(vis,0,sizeof vis);
    F(l,1,len) {
        int r=l;
        while (r+1<=len&&ht[r+1]>=lim)
            r++;
        ind++,tot=0;
        F(i,l,r)
            Add(sa[i],lim);
        if (tot==n)
            return 1;
        l=r;
    }
    return 0;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("C.in","r",stdin);
        freopen("C.out","w",stdout);
    #endif
    nT=rd();
    F(c,1,nT) {
        n=0;
        memset(star,0,sizeof star);
        memset(fini,0,sizeof fini);
        memset(slen,0,sizeof slen);
        memset(own,0,sizeof own);
        memset(s,0,sizeof s);
        len=0;
        n=rd();
        F(i,1,n) {
            int di=fini[i-1]+1;
            s[di]='>';
            star[i]=di+1;
            scanf("%s",s+di+1);
            slen[i]=strlen(s+di+1);
            s[di+slen[i]+1]='-';
            F(j,di+1,di+slen[i])
                s[2*(di+slen[i]+1)-j]=s[j];
            fini[i]=di+slen[i]+1+slen[i];
            F(j,star[i],fini[i])
                own[j]=i;
        }
        s[len=fini[n]+1]='>';
        Prework();
        al=0;
        ar=*max_element(slen+1,slen+n+1);
        while (al<ar) {
            mid=(al+ar+1)>>1;
            int tag=Check(mid);
            if (tag)
                al=mid;
            else ar=mid-1;
        }
        printf("%d\n",al);
    }
    return 0;
} 
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}