FCS省选模拟赛 Day5

传送门

Solution

Code 

#include
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
const int inf=0x3f3f3f3f,MN=105,T=235,S=0,TT=245;
int n,m,k,nx[MN],ny[MN],ans;
bool mp[MN][MN];
int d[TT],q[TT],top;
struct edge{int to,w,nex;}e[MN*MN*2];int hr[TT],cur[TT],en=1;
inline void ins(int f,int t,int w)
{e[++en]=(edge){t,w,hr[f]};hr[f]=en;e[++en]=(edge){f,0,hr[t]};hr[t]=en;
}
bool bfs(){memset(d,0,sizeof d);register int i,j;for(d[q[top=i=1]=S]=1;i<=top;i++)for(j=hr[q[i]];j;j=e[j].nex)if(e[j].w&&!d[e[j].to])d[q[++top]=e[j].to]=d[q[i]]+1;return d[T];
}
int dfs(int x,int f){if(x==T) return f;int used=0;for(int &i=cur[x];i;i=e[i].nex)if(e[i].w&&d[e[i].to]==d[x]+1){int w=dfs(e[i].to,min(e[i].w,f-used));used+=w;e[i].w-=w;e[i^1].w+=w;if(used==f) return used;}return d[x]=-1,used;
}
inline void dinic()
{while(bfs()){memcpy(cur,hr,sizeof cur);ans-=dfs(S,inf);}
}
int main()
{register int i,j,x,y;n=read();m=read();k=read();for(i=1;i<=n;++i) nx[i]=m-read();for(i=1;i<=m;++i) ny[i]=n-read();for(i=1;i<=k;++i) x=read(),y=read(),--nx[x],--ny[y],mp[x][y]=true;for(i=1;i<=n;++i) if(nx[i]<0) return 0*puts("IIllIIll1！");for(i=1;i<=m;++i) if(ny[i]<0) return 0*puts("IIllIIll1！");for(i=1;i<=n;++i) ins(S,i,nx[i]);for(i=1;i<=m;++i) ins(i+MN,T,ny[i]);for(i=1;i<=n;++i)for(j=1;j<=m;++j) if(!mp[i][j]) ins(i,j+MN,1);ans=n*m-k;dinic();return 0*printf("%d
",ans);
}

/*
rongchi : f_n=d_n-a_n a_n:num of n's factor that is not QQn
Sum d_i easy = sum (N/i)
sum a_n =sum mu[i]^2 * (n/i)
mobi : sum mu[i]^2 = sum mu[i]*N/(i^2)
*/
#include
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
const int MN=35000;
ll mu[MN],prime[MN],tot;
bool mk[MN]; 
inline void init()
{mu[1]=1;register int i,j;for(i=2;i

/*
后缀自动机+线段树合并
对Fail树进行dfs
每个点的level应该是祖先中满足出现次数大于1的最大lev+1
如果没有，level等于祖先中最大的lev
判断出现次数，用线段树区间求和
为什么实现是每个节点只需考虑它的最大len？
如果有小的len，它每次出现时必然伴随最大的len一同出现，所以不影响
2019/3/20 by pac
*/
#include
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int MN=2e5+5,MX=4e5+5,MS=1e7+5;
char s[MN+5];
int len;
class Seg
{int ls[MS],rs[MS],v[MS],root[MX],tot;void Md(int &x,int l,int r,int a,int ad){if(!x) x=++tot;if(l==r){v[x]+=ad;return;}int mid=(l+r)>>1;if(a<=mid) Md(ls[x],l,mid,a,ad);else Md(rs[x],mid+1,r,a,ad);v[x]=v[ls[x]]+v[rs[x]];}int Qy(int x,int l,int r,int a,int b){if(!x) return 0;if(l==a&&r==b){return v[x];}int mid=(l+r)>>1;if(b<=mid) return Qy(ls[x],l,mid,a,b);if(a>mid) return Qy(rs[x],mid+1,r,a,b);return Qy(ls[x],l,mid,a,mid)+Qy(rs[x],mid+1,r,mid+1,b);}int Merge(int x,int y,int l,int r){if(!x||!y) return x|y;int o=++tot;v[o]=v[x]+v[y];int mid=(l+r)>>1;ls[o]=Merge(ls[x],ls[y],l,mid);rs[o]=Merge(rs[x],rs[y],mid+1,r);return o;}public:void md(int x,int k){Md(root[x],1,len,k,1);}bool qy(int x,int l,int r){return Qy(root[x],1,len,l,r)>=2;}int merge(int x,int y){root[x]=Merge(root[x],root[y],1,len);}
}T;
class SAM
{int c[MX][26],fa[MX],step[MX],pos[MX];int last,cnt,n;int ans=0,lev[MX];struct ed{int to,nex;}e[MX<<1];int en,hr[MX];void ins(int x,int y){e[++en]=(ed){y,hr[x]};hr[x]=en;}void pre_dfs(int x){register int i;for(i=hr[x];i;i=e[i].nex)pre_dfs(e[i].to),pos[x]=max(pos[x],pos[e[i].to]),T.merge(x,e[i].to);}void dfs(int x,int mx){if(x!=1&&(T.qy(mx,pos[x]-step[x]+step[mx],pos[x])||step[x]==1)) lev[x]=lev[mx]+1,mx=x;else lev[x]=lev[mx];register int i;for(i=hr[x];i;i=e[i].nex) dfs(e[i].to,mx);ans=max(ans,lev[x]);}public:inline void init(){cnt=last=1;n=0;for(int i=1;i<=n<<1;++i)memset(c[i],0,sizeof c[i]),lev[i]=step[i]=fa[i]=0;}void Insert(int x){int p=last,np=++cnt;step[np]=step[p]+1;T.md(np,pos[np]=++n);for(;p&&!c[p][x];p=fa[p]) c[p][x]=np;if(!p) fa[np]=1;else {int q=c[p][x];if(step[q]==step[p]+1) fa[np]=q;else {int nq=++cnt;step[nq]=step[p]+1;memcpy(c[nq],c[q],sizeof c[q]);fa[nq]=fa[q];fa[np]=fa[q]=nq;for(;c[p][x]==q;p=fa[p]) c[p][x]=nq;}    }last=np;}void solve(){register int i;for(i=2;i<=cnt;++i) if(fa[i]) ins(fa[i],i);pre_dfs(1);dfs(1,1);printf("%d
",ans);}
}sam;
int main()
{scanf("%s",s+1);len=strlen(s+1);sam.init();register int i;for(i=1;i<=len;++i) sam.Insert(s[i]-'a');sam.solve();return 0;
}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！