传送门
Solution
Code
#include<bits/stdc++.h>
#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<bits/stdc++.h>
#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<MN;++i)
{
if(!mk[i]){prime[++tot]=i;mu[i]=-1;}
for(j=1;j<=tot&&i*prime[j]<MN;++j)
{
mk[i*prime[j]]=true;
if(i%prime[j]==0)
{
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=-mu[i];
}
}
}
ll get_d(int N)
{
ll ans=0;register int l=1,r;
for(;l<=N;l=r+1)
{
r=N/(N/l);
ans+=1ll*(N/l)*(r-l+1);
}
return ans;
}
ll Pre(int N)
{
register int i;ll ans=0;
for(i=1;i*i<=N;++i) ans+=1ll*mu[i]*(N/i/i);
return ans;
}
ll get_a(int N)
{
register int l=1,r;ll ans=0;
for(;l<=N;l=r+1)
{
r=N/(N/l);
ans+=1ll*(Pre(r)-Pre(l-1))*(N/l);
}
return ans;
}
ll get(int N)
{
if(!N) return 0ll;
return get_d(N)-get_a(N);
}
int main()
{
ll L,R;
init();L=read(),R=read();
printf("%lld
",get(R)-get(L-1));
}
/*
后缀自动机+线段树合并
对Fail树进行dfs
每个点的level应该是祖先中满足出现次数大于1的最大lev+1
如果没有，level等于祖先中最大的lev
判断出现次数，用线段树区间求和
为什么实现是每个节点只需考虑它的最大len？
如果有小的len，它每次出现时必然伴随最大的len一同出现，所以不影响
2019/3/20 by pac
*/
#include<bits/stdc++.h>
#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！