2017-4-14校内训练
hzwer拿了几道noi中比较简单的给我们做
思路：考虑最小割，如果一个植物的权值x是正的，我们先默认吃掉它，使答案加上x并让S向这个点连x，割这条边相当于不吃这个植物，否则让这个点向T连-x，割这条边相当于吃这个植物，每个植物让它能攻击到的格子和它的前一格向它连INF，表示要么不吃它能保护到的，要么吃它，如果构成了环，这些植物必然都不能被吃，判完环后环上的点全部向T连INF即可。
#include<cstdio> #include<cstring> inline int read() { int x,f=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')f=0; for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0'; return f?x:-x; } #define MV 600 #define ME 400000 #define S MV+1 #define T MV+2 #define INF 0x7FFFFFFF #define p(x,y) ((x)*30+(y)+1) struct edge{int nx,t,w;}e[ME*2+5]; int h[MV+5],en=1,d[MV+5],c[MV+5],q[MV+5],qn,df[MV+5],lw[MV+5],cnt,inq[MV+5]; inline void ins(int x,int y,int w) { e[++en]=(edge){h[x],y,w};h[x]=en; e[++en]=(edge){h[y],x,0};h[y]=en; } bool bfs() { int i,j; memset(d,0,sizeof(d)); for(d[q[i=qn=0]=S]=1;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx) if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1; return d[T]; } int dfs(int x,int r) { if(x==T)return r; int k,u=0; for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[e[i].t]==d[x]+1) { k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w); e[i].w-=k;e[i^1].w+=k;u+=k; if(u==r)return r; } return d[x]=0,u; } void dfs(int x) { int i,u; df[x]=lw[x]=++cnt;inq[q[qn++]=x]=1; for(int i=h[x];i;i=e[i].nx)if(e[i].w) { if(!df[e[i].t])dfs(e[i].t); if(inq[e[i].t]&&lw[e[i].t]<lw[x])lw[x]=lw[e[i].t]; } u=q[qn-1]!=x; if(df[x]==lw[x])for(;q[qn]!=x;u?(ins(q[qn],T,INF),0):0)inq[q[--qn]]=0; } int main() { int n,m,i,j,k,x,ans=0; n=read();m=read(); for(i=0;i<n;++i)for(j=0;j<m;++j) { x=read(); if(x>0)ans+=x,ins(S,p(i,j),x); else ins(p(i,j),T,-x); if(j)ins(p(i,j-1),p(i,j),INF); for(k=read();k--;)x=read(),ins(p(x,read()),p(i,j),INF); } for(i=0;i<n;++i)for(j=0;j<m;++j)if(!df[p(i,j)])dfs(p(i,j)); while(bfs())ans-=dfs(S,INF); printf("%d",ans); }
之前做过了，题解戳这里
思路：用f[i][j][k]表示前i段时间过后，钢琴在(j,k)的最长路程，转移很显然单调队列嘛，复杂度O(nmk)。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0'; return x; } #define MN 200 int f[MN+5][MN+5][MN+5],q[MN+5],ql,qr; char s[MN+5][MN+5]; int main() { int n,m,x,y,t,i,j,xx,yy,ans=0; n=read();m=read(); memset(f,200,sizeof(f)); x=read();f[0][x][read()]=0;t=read(); for(i=1;i<=n;++i)scanf("%s",s[i]+1); for(i=1;i<=t;++i) { x=read();x=read()-x+1;y=read(); if(y==1)for(yy=1;yy<=m;++yy)for(ql=1,qr=0,xx=n;xx;--xx) { while(ql<=qr&&f[i-1][xx][yy]+xx>=f[i-1][q[qr]][yy]+q[qr])--qr;q[++qr]=xx; while(q[ql]-xx>x)++ql; if(s[xx][yy]=='.')f[i][xx][yy]=f[i-1][q[ql]][yy]+q[ql]-xx; else ql=1,qr=0; } if(y==2)for(yy=1;yy<=m;++yy)for(ql=1,qr=0,xx=1;xx<=n;++xx) { while(ql<=qr&&f[i-1][xx][yy]-xx>=f[i-1][q[qr]][yy]-q[qr])--qr;q[++qr]=xx; while(xx-q[ql]>x)++ql; if(s[xx][yy]=='.')f[i][xx][yy]=f[i-1][q[ql]][yy]+xx-q[ql]; else ql=1,qr=0; } if(y==3)for(xx=1;xx<=n;++xx)for(ql=1,qr=0,yy=m;yy;--yy) { while(ql<=qr&&f[i-1][xx][yy]+yy>=f[i-1][xx][q[qr]]+q[qr])--qr;q[++qr]=yy; while(q[ql]-yy>x)++ql; if(s[xx][yy]=='.')f[i][xx][yy]=f[i-1][xx][q[ql]]+q[ql]-yy; else ql=1,qr=0; } if(y==4)for(xx=1;xx<=n;++xx)for(ql=1,qr=0,yy=1;yy<=m;++yy) { while(ql<=qr&&f[i-1][xx][yy]-yy>=f[i-1][xx][q[qr]]-q[qr])--qr;q[++qr]=yy; while(yy-q[ql]>x)++ql; if(s[xx][yy]=='.')f[i][xx][yy]=f[i-1][xx][q[ql]]+yy-q[ql]; else ql=1,qr=0; } } for(i=1;i<=n;++i)for(j=1;j<=m;++j)ans=max(ans,f[t][i][j]); printf("%d",ans); }
思路：首先kmp弄出next数组，num[i]就是每次令i=next[i]，在变成0前有多少次不超过i/2，先不考虑不超过i/2的限制，则num[i]=num[next[i]]+1，对于每个next[i]>i/2，扣掉它next几次后会小等于i/2，由于它的循环节是i-next[i]，每次取next都会使它的值减小i-next[i]，除一下就好了，复杂度O(n)。
#include<cstdio> #include<cstring> #define MN 1000000 #define MOD 1000000007 char s[MN+5]; int nx[MN+5],f[MN+5]; int main() { int n,i,j,ans; scanf("%d",&n); while(n--) { scanf("%s",s+1); for(f[1]=1,i=2,j=0;s[i];++i) { while(j&&s[i]!=s[j+1])j=nx[j]; if(s[i]==s[j+1])++j; f[i]=f[nx[i]=j]+1; } for(ans=i=1;s[i];++i) { if(nx[i]*2>i)f[i]-=(nx[i]-i/2+i-nx[i]-1)/(i-nx[i]); ans=1LL*ans*f[i]%MOD; } printf("%d ",ans); } }