由数据范围容易想到网络流。由于操作只是对于棋盘上相邻两格,容易想到给其黑白染色。
假设已经知道最后要变成什么数。那么给黑白点之间连边,其流量则表示同时增加的次数,再用源汇给其限流为需要增加的数即可。
考虑最后应该变成什么数。
如果棋盘中黑白格子数量不同,设最后变成的数是x,则x*黑格数量-黑格数字和=x*白格数量-白格数字和,若黑格数量多即x=黑格数字和-白格数字和。直接变为最大值是不一定合法的。
否则首先黑白格子内权值和应相同,否则无解。如果变成某个数是合法的,变的更大也是合法的。那么二分最后变成的数即可。因为最终方案中并不一定存在能恰好覆盖整个棋盘的操作,所以直接变为最大数是错的。注意二分上界需要开的非常大。
无数次死于long long。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 42#define S 0#define T 1601#define inf 2000000000000int test,n,m,p[N*N],a[N][N],t;int d[N*N],q[N*N],cur[N*N];bool flag[N*N];long long ans;struct data{ int to,nxt;long long cap,flow;}edge[N*N<<5];void addedge(int x,int y,long long z){ t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=0,p[x]=t; t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=0,edge[t].flow=0,p[y]=t;}int trans(int x,int y){ return (x-1)*m+y;}bool bfs(){ memset(d,255,sizeof(d));d[S]=0; int head=0,tail=1;q[1]=S; do { int x=q[++head]; for (int i=p[x];~i;i=edge[i].nxt) if (d[edge[i].to]==-1&&edge[i].flow 1) addedge(trans(i,j),trans(i-1,j),inf); if (i 1) addedge(trans(i,j),trans(i,j-1),inf); if (j =v?(check(sumy-sumx,(sumy-sumx)*n*m-sumx-sumy>>1)?sumy-sumx:-1):-1; else { if (sumx==sumy) { long long l=v,r=inf; while (l<=r) { long long mid=l+r>>1; if (check(mid,mid*n*m-sumx-sumy>>1)) tot=mid,r=mid-1; else l=mid+1; } } } if (tot==-1) cout<<-1< >1)<