T1
给定一个nxn的网格，规定(x+y)&1的位置权值非负，否则一定为0，现在可以向图上放L形的石头，同时石头的任意部分不得与其他石头或者障碍重叠，且一块石头能删掉拐角处的数，求图上的最小总权值。
我们考虑用最大费用可行流来解决问题，令奇数列的0格向四周连边，S向奇数列的0格连边，偶数列的0格向T连边，然后处理拐角就好了。
考场上队列的数组开小了，挂了不少分。另外增广的时候要增广到权值非负。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define mxn 55005 #define mxm 100005 #define inf 0x3f3f3f3f using namespace std; inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*f; } struct edge{ int u,v,c,f,w,nxt; }e[2*mxm]; int prv[mxn],tot=1,S,T,SS,idx; inline void add(int u,int v,int c,int w){ //cerr<<u<<" -> "<<v<<" ("<<c<<","<<w<<")\n"; e[++tot]=(edge){u,v,c,0,w,prv[u]},prv[u]=tot; e[++tot]=(edge){v,u,0,0,-w,prv[v]},prv[v]=tot; } int dis[mxn],q[mxn],pid[mxn],qh,qt; bool vis[mxn]; inline bool spfa(){ for(int i=1;i<=idx;++i) vis[i]=pid[i]=0,dis[i]=-inf; dis[S]=0,vis[S]=1,q[qh=qt=1]=S; register int u; while(qh<=qt) { u=q[qh++]; for(int i=prv[u];i;i=e[i].nxt) { if(e[i].f<e[i].c&&dis[e[i].v]<dis[u]+e[i].w) { dis[e[i].v]=dis[u]+e[i].w; pid[e[i].v]=i; if(!vis[e[i].v]) vis[e[i].v]=1,q[++qt]=e[i].v; } } vis[u]=0; } return pid[T]; } inline void gmin(int &a,int b){if(a>b)a=b;} inline int mcmf(){ int co=0,fl=0,mn; while(spfa()) { if(dis[T]<=0) break; mn=inf; for(int i=pid[T];i;i=pid[e[i].u]) gmin(mn,e[i].c-e[i].f); for(int i=pid[T];i;i=pid[e[i].u]) e[i].f+=mn,e[i^1].f-=mn; fl+=mn,co+=mn*dis[T]; } return co; } bool flo[55][55]; int n,m,p,s[55][55],id[55][55][2]; int main(){ n=read(),m=read(),p=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) s[i][j]=read(),flo[i][j]=1; for(int i=1;i<=p;++i) { int x=read(),y=read(); flo[x][y]=0; } S=++idx,T=++idx,SS=++idx; add(S,SS,m,0); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { id[i][j][0]=++idx,id[i][j][1]=++idx; add(id[i][j][0],id[i][j][1],flo[i][j],s[i][j]); } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if((i+j)&1) { if(j&1) { if(id[i-1][j][0]) add(id[i][j][1],id[i-1][j][0],1,0); if(id[i+1][j][0]) add(id[i][j][1],id[i+1][j][0],1,0); } else { if(id[i][j-1][0]) add(id[i][j][1],id[i][j-1][0],1,0); if(id[i][j+1][0]) add(id[i][j][1],id[i][j+1][0],1,0); } } else { if(j&1) { add(id[i][j][1],T,1,0); } else { add(SS,id[i][j][0],1,0); if(id[i][j-1][0]) add(id[i][j][1],id[i][j-1][0],1,0); if(id[i][j+1][0]) add(id[i][j][1],id[i][j+1][0],1,0); if(id[i-1][j][0]) add(id[i][j][1],id[i-1][j][0],1,0); if(id[i+1][j][0]) add(id[i][j][1],id[i+1][j][0],1,0); } } } int sum=0; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) sum+=s[i][j]; int mf=mcmf(); printf("%d\n",sum-mf); } |
T2
一棵n个点的树，每次选择c(<=5)个点（可能相同），使得这些点都走到LCA处，且每个点都选取路径上的一些颜色，要求每个点选出的颜色个数相等且互不重复，求最大的选出的颜色数（<=1000）。
首先，根据hall定理，一个左侧有n个点，右侧有m个点的二分图存在完美匹配，满足任意k个点在右边都有k个点与之相邻。那么，我们就让左侧有i*c个点，右边有m个点，只需求出在c的任意子集中，所有可以到达的颜色的并集大小比上这个子集的大小的最小值，就是答案了。
对于这个东西，我们可以先树剖，用Bitset维护出每个点到达链顶的信息，按照DFS序建出线段树并维护区间信息，这样就可以单次O(logn*m/w)地查询一个点到某个祖先路径上出现的颜色了。
之后，我们再用Bitset搞搞就过了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define mxn 300005 #define lb(x) ((x)&(-(x))) using namespace std; char ibuf[65536],*ih,*it; #define getc() (((ih==it)&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it))?0:*ih++) inline int read(){ int s=0,f=1; char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc(); return s*f; } struct edge{ int v,nxt; }e[2*mxn]; int prv[mxn],tot,n,cl,p,s[mxn]; bitset<1001> bs[mxn<<2],ct[mxn]; int dep[mxn],sz[mxn],son[mxn],fa[mxn],top[mxn],id[mxn],idx,rid[mxn]; inline void dfs1(int u,int ft){ sz[u]=1,dep[u]=dep[ft]+1,fa[u]=ft; for(int i=prv[u];i;i=e[i].nxt) { dfs1(e[i].v,u); sz[u]+=sz[e[i].v]; if(sz[son[u]]<sz[e[i].v]) son[u]=e[i].v; } } inline void dfs2(int u,int tp){ top[u]=tp,id[u]=++idx,rid[idx]=u; if(u==tp) ct[u][s[u]]=1; else ct[u]=ct[fa[u]],ct[u][s[u]]=1; if(son[u]) dfs2(son[u],tp); for(int i=prv[u];i;i=e[i].nxt) if(!top[e[i].v]) dfs2(e[i].v,e[i].v); } inline void build(int o,int l,int r){ if(l==r) bs[o][s[rid[l]]]=1; else { int m=l+r>>1; build(o<<1,l,m),build(o<<1|1,m+1,r); bs[o]=bs[o<<1]|bs[o<<1|1]; } } int ql,qr; bitset<1001> res,rs[7],st[32]; inline void query(int o,int l,int r){ if(ql<=l&&r<=qr) res|=bs[o]; else { int m=l+r>>1; if(ql<=m) query(o<<1,l,m); if(m<qr) query(o<<1|1,m+1,r); } } inline int lca(int u,int v){ int f1=top[u],f2=top[v]; while(f1!=f2) { if(dep[f1]>dep[f2]) u=fa[f1],f1=top[u]; else v=fa[f2],f2=top[v]; } return dep[u]<dep[v]?u:v; } inline void work(int d,int u,int v){ rs[d].reset(); int f1=top[u],f2=top[v]; while(f1!=f2) { rs[d]|=ct[u]; u=fa[f1],f1=top[u]; } ql=id[v],qr=id[u],res.reset(); query(1,1,n); rs[d]|=res; } int cnt,pt[7],bit[32],lg[32],pcnt[32]; inline void gmin(int &a,int b){if(a>b)a=b;} int main(){ for(int i=0;i<=30;++i) bit[i]=1<<i; n=read(),cl=read(),p=read(); register int u,v; for(int i=2;i<=n;++i) { u=read(),v=i; e[++tot]=(edge){v,prv[u]},prv[u]=tot; } for(int i=1;i<=n;++i) s[i]=read(); dfs1(1,0),dfs2(1,1); build(1,1,n); for(int i=0;i<5;++i) lg[bit[i]]=i+1; for(int i=0;i<bit[5];++i) pcnt[i]=pcnt[i>>1]+(i&1); while(p--) { cnt=read(); for(int i=1;i<=cnt;++i) pt[i]=read(); int l=pt[1]; for(int i=2;i<=cnt;++i) l=lca(l,pt[i]); for(int i=1;i<=cnt;++i) work(i,pt[i],l); int ans=cl; for(int i=1;i<bit[cnt];++i) { if(i==lb(i)) st[i]=rs[lg[i]]; else st[i]=rs[lg[lb(i)]]|st[i^lb(i)]; gmin(ans,st[i].count()/pcnt[i]); } printf("%d\n",ans*cnt); } } |
T3
给出一个长度为n的字符串，同时每个位置都有权值v（非负），求出所有满足权值之和等于排名（降序）的子串的左右端点。
首先，如果我们枚举左端点，右端点向右移动时，排名单调递减，且权值之和单点不降，因此做差之后函数单调递减，我们可以二分判断是否存在零点。只需做到O(logn)算出特定子串的排名，即可O(log^2n)查询零点。我们可以考虑每个排名的后缀对于本质不同的子串产生的贡献，然后二分出合适的位置，问题就解决了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#pragma GCC optimize("-O3") #include <bits/stdc++.h> #define mxn 200005 #define ll long long using namespace std; char ibuf[65536],*ih,*it; #define getc() (((ih==it)&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it))?0:*ih++) inline int read(){ int s=0,f=1; char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc(); return s*f; } int s[mxn],tx[mxn],ty[mxn],n,m,rnk[mxn],sa[mxn],ht[mxn]; inline void radix_sort(){ for(int i=1;i<=m;++i) tx[i]=0; for(int i=1;i<=n;++i) tx[rnk[ty[i]]]++; for(int i=1;i<=m;++i) tx[i]+=tx[i-1]; for(int i=n;i>=1;--i) sa[tx[rnk[ty[i]]]--]=ty[i]; } inline void getsa(){ register int i,j,k,p,l; for(i=1;i<=n;++i) rnk[i]=s[i],ty[i]=i; m=30,radix_sort(); for(p=1,l=1;p<n;m=p,l<<=1) { for(i=n-l+1,p=0;i<=n;++i) ty[++p]=i; for(i=1;i<=n;++i) if(sa[i]>l) ty[++p]=sa[i]-l; radix_sort(),swap(rnk,ty),rnk[sa[1]]=p=1; for(i=2;i<=n;++i) rnk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p; } for(i=1,k=0;i<=n;ht[rnk[i++]]=k) for(k=k?k-1:0,j=sa[rnk[i]-1];s[i+k]==s[j+k];++k); } ll sm[mxn]; int val[mxn],lg[mxn],bit[32],mnv[18][mxn]; inline int mmin(const int &a,const int &b){return a<b?a:b;} inline void ST_init(){ for(int i=0;i<=30;++i) bit[i]=1<<i; for(int i=1;i<=n;++i) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;++i) --lg[i]; for(int i=1;i<=n;++i) mnv[0][i]=ht[i]; for(int j=1;bit[j]<=n;++j) for(int i=1;i+bit[j]-1<=n;++i) mnv[j][i]=mmin(mnv[j-1][i],mnv[j-1][i+bit[j-1]]); } inline int qmin(int l,int r){ if(l==r) return n-sa[l]+1; ++l; int d=lg[r-l+1]; return mmin(mnv[d][l],mnv[d][r-bit[d]+1]); } inline ll grnk(int l,int r) { int pos=rnk[l]; if(r-l+1>ht[pos]) return sm[pos-1]+(r-l+1-ht[pos]); int L=1,M,R=pos-1,len=r-l+1; while(R>L){ M=L+R>>1; if(qmin(M,pos)>=len) R=M; else L=M+1; } return sm[R-1]+(r-l+1-ht[R]); } ll sum[mxn]; typedef pair<int,int> pii; vector<pii> res; inline ll calc(int l,int r){ ll v1=sm[n]-grnk(l,r)+1,v2=sum[r]-sum[l-1]; return v1-v2; } int main(){ register char ch=getc(); while(ch>='a'&&ch<='z') s[++n]=ch-'a'+1,ch=getc(); getsa(); for(int i=1;i<=n;++i) sm[i]=sm[i-1]+(n-sa[i]+1)-ht[i]; ST_init(); for(int i=1;i<=n;++i) val[i]=read(),sum[i]=sum[i-1]+val[i]; for(int i=1;i<=n;++i) { int L=i,M,R=n; while(R>L) { M=L+R+1>>1; if(calc(i,M)>=0) L=M; else R=M-1; } if(i<=L&&calc(i,L)==0) res.push_back(pii(i,L)); } printf("%d\n",res.size()); for(auto i:res) printf("%d %d\n",i.first,i.second); } |
叨叨几句... NOTHING