来自FallDream的博客，未经允许，请勿转载，谢谢。
hzwer又出丧题虐人 4道noi.... 很奇怪 每次黄学长出题总有一题我做过了。
嗯题目你们自己看看呗 好难解释
--------------------------------------
A.[bzoj1565][NOI2009]植物大战僵尸
这道题其实挺好想的。nm比较小，考虑最小割，假设割到S表示吃，割到T表示不吃
那么能源小于0的，从S向他连边，流量是负的能源，
能源大于0的，从它向T连边，流量是能源，同时答案加上能源，
然后对于每一个限制条件，都连INF的边 最后最小割。
#include<iostream> #include<cstdio> #include<cstring> #define S 0 #define T 601 #define INF 2000000000 #define num(x,y) ((x-1)*m+y) using namespace std; 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 * 10 + ch - '0';ch = getchar();} return x * f; } int head[T+5],head2[T+5],c[T+5],d[T+5],cnt=T*T*5,tcnt=0,n,m,ans=0,q[T+5],top,s[T+5],in[T+5]; struct edge{int to,next,w;}e[5000000]; bool b[T+5]; void ins(int f,int t){e[++tcnt]=(edge){t,head2[f],0};head2[f]=tcnt;in[t]++;} void ins(int f,int t,int w) { e[++cnt]=(edge){t,head[f],w};head[f]=cnt; e[++cnt]=(edge){f,head[t],0};head[t]=cnt; } void topsort(int x) { q[top=1]=x; for(int i=1;i<=top;i++) { if(x=q[i]) b[x]=1,s[x]>=0?(ans+=s[x],ins(x,T,s[x]),0) :(ins(S,x,-s[x]),0); for(int j=head2[x];j;j=e[j].next) if(!--in[e[j].to]) q[++top]=e[j].to; } for(int i=1;i<=n*m;i++) if(b[i]) for(int j=head2[i];j;j=e[j].next) if(b[e[j].to]) ins(i,e[j].to,INF); } int dfs(int x,int f) { if(x==T)return f; int used=0; for(int&i=c[x];i;i=e[i].next) if(e[i].w&&d[e[i].to]==d[x]+1) { int w=dfs(e[i].to,min(f-used,e[i].w)); used+=w;e[i].w-=w;e[i^1].w+=w; if(used==f)return f; } return d[x]=-1,used; } bool bfs() { memset(d,0,sizeof(d));int i,j; for(d[q[top=i=1]=S]=1;i<=top;i++) for(int j=c[q[i]]=head[q[i]];j;j=e[j].next) if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1; return d[T]; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(j>1) ins(num(i,j),num(i,j-1)); s[num(i,j)]=read(); for(int k=read();k;k--) { int x=read()+1,y=read()+1; ins(num(i,j),num(x,y)); } } for(int i=1;i<=n;i++) ins(0,num(i,m)); topsort(0); while(bfs()) ans-=dfs(S,INF); cout<<ans; return 0; }
B.阿狸的打字机 戳这里
C.[bzoj1499][NOI2005]瑰丽华尔兹
题解：很容易想到O(nmk)dp，然后我们每一次的更新都只能从一个方向转移，用一个单调队列维护一下
#include<iostream> #include<cstdio> #include<cstring> #define pa pair<int,int> #define mp(x,y) make_pair(x,y) #define MN 200 #define INF 200000000 using namespace std; 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 * 10 + ch - '0';ch = getchar();} return x * f; } int f[MN+5][MN+5][MN+5],T[MN+5],dir[MN+5],n,m,x,y,k; char st[MN+5][MN+5]; struct MyQueue { int top,tail;pa s[MN+5]; void clear(int x){top=tail=0;s[top]=mp(x,-INF);} void ins(int x,int from) { while(s[top].second<x&&top>=tail) --top; s[++top]=mp(from,x); } int get(int t) { while(s[tail].first<t) ++tail; return s[tail].second; } }q; int main() { memset(f,128,sizeof(f)); q.clear(0); n=read();m=read();x=read();y=read();k=read(); f[0][x][y]=0; for(int i=1;i<=n;i++) scanf("%s",st[i]+1); for(int i=1;i<=k;i++) { int x=read(),y=read(); T[i]=y-x+1;dir[i]=read(); } for(int t=1;t<=k;t++) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[t][i][j]=max(f[t][i][j],f[t-1][i][j]); if(dir[t]==1) for(int i=1;i<=m;i++,q.clear(0)) for(int j=n;j;j--) if(st[j][i]!='x') f[t][j][i]=max(f[t][j][i],q.get(n+1-j-T[t])-j),q.ins(f[t-1][j][i]+j,n+1-j); else q.clear(n+1-j); if(dir[t]==2) for(int i=1;i<=m;i++,q.clear(0)) for(int j=1;j<=n;j++) if(st[j][i]!='x') f[t][j][i]=max(f[t][j][i],q.get(j-T[t])+j),q.ins(f[t-1][j][i]-j,j); else q.clear(j); if(dir[t]==3) for(int i=1;i<=n;i++,q.clear(0)) for(int j=m;j;j--) if(st[i][j]!='x') f[t][i][j]=max(f[t][i][j],q.get(m+1-j-T[t])-j),q.ins(f[t-1][i][j]+j,m+1-j); else q.clear(m+1-j); if(dir[t]==4) for(int i=1;i<=n;i++,q.clear(0)) for(int j=1;j<=m;j++) if(st[i][j]!='x') f[t][i][j]=max(f[t][i][j],q.get(j-T[t])+j),q.ins(f[t-1][i][j]-j,j); else q.clear(j); } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(ans,f[k][i][j]); cout<<ans; return 0; }
D.[bzoj3670][Noi2014]动物园
自己yy了一下，发现num[i]就是在i/2之前的fail节点的个数。
可以假装用自己这个串匹配自己，然后到了第i个点的时候突然不对了（别问我为什么不对），那么我跳到的fail节点一定既是前缀又是现在的后缀，因为我在匹配自己呢（雾）
#include<iostream> #include<cstdio> #include<cstring> #define MN 1000000 #define mod 1000000007 using namespace std; bool b[MN+5]; int fail[MN+5],num[MN+5],ans=1; char st[MN+5]; int main() { num[1]=1;int T; for(cin>>T;T;T--) { scanf("%s",st+1);ans=1; memset(b,0,sizeof(b)); for(int i=2,j=0;st[i];i++) { while(j&&st[j+1]!=st[i])j=fail[j]; if(st[j+1]==st[i]) ++j; fail[i]=j;num[i]=num[j]+1; } for(int i=2,j=0;st[i];i++) { while(j&&((j+1)*2>i||st[j+1]!=st[i]))j=fail[j]; if(st[j+1]==st[i]) ++j; ans=1LL*ans*(num[j]+1)%mod; } printf("%d ",ans); } return 0; }