博客
关于我
[省选联考 2021]矩阵游戏
阅读量:257 次
发布时间:2019-03-01

本文共 4289 字,大约阅读时间需要 14 分钟。

题解

很明显,前50pts可以手玩出来

我们可以先不考虑 0 ⩽ a ⩽ 1 0 6 0\leqslant a\leqslant 10^6 0a106的限制,先暴力跑出来一组解,在这组解上修改得到合法解。

如何进行修改得到的答案满足 b b b的限制呢?我们需要使得每一个方块格子和不变。于是,我们有了以下四种构造方法:
+ x +x +x, + x +x +x, + x +x +x, + x +x +x, . . . . . ..... .....
− x -x x, − x -x x, − x -x x, − x -x x, . . . . . ..... .....
+ x +x +x, + x +x +x, + x +x +x, + x +x +x, . . . . . ..... .....
− x -x x, − x -x x, − x -x x, − x -x x, . . . . . ..... .....
. . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . .... ....

+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....

+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....
+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....
+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....
. . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . .... ....

+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....

− x -x x, + x +x +x, − x -x x, + x +x +x, . . . . . ..... .....
+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....
− x -x x, + x +x +x, − x -x x, + x +x +x, . . . . . ..... .....
. . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . .... ....

− x -x x, + x +x +x, − x -x x, + x +x +x, . . . . . ..... .....

+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....
− x -x x, + x +x +x, − x -x x, + x +x +x, . . . . . ..... .....
+ x +x +x, − x -x x, + x +x +x, − x -x x, . . . . . ..... .....
. . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . . ..... ....., . . . . .... ....

很明显,前面两种行列全部都是加的我们是比较难维护的,而后面的两种我们是可以通过差分约束来进行维护。

我们假设第3种每行加上的是 r o w i row_{i} rowi,第十种每行加上的是 c o l j col_{j} colj,那么针对点 ( i , j ) (i,j) (i,j)有限制 − A i , j ⩽ ( − 1 ) i + j r o w i − ( − 1 ) i + j c o l j ⩽ 1 0 6 − A i , j -A_{i,j}\leqslant (-1)^{i+j}row_{i}-(-1)^{i+j}col_{j}\leqslant 10^6-A_{i,j} Ai,j(1)i+jrowi(1)i+jcolj106Ai,j,这里的 A i , j A_{i,j} Ai,j指我们暴力跑出解得 A i , j A_{i,j} Ai,j
我们将 r o w i row_{i} rowi c o l j col_{j} colj都建成一个点,那么我们就针对每个点都得到 n / m n/m n/m个限制。
也就是一个有 n + m n+m n+m个点, 2 n m 2nm 2nm条边的带权有向图,如果这个图中有负环,那么就是无解的。

我们只需要跑一遍SPFA就可以得到解了。时间复杂度 O ( T n m ( n + m ) ) O\left(Tnm(n+m)\right) O(Tnm(n+m))

很明显,如果出现负环,时间复杂度就会被卡满,我们得加点小优化,准确说就是当一个点到1号点经过的边超过30的时候就给他直接判无解了。还真能过
然后,根据 r o w i row_{i} rowi c o l j col_{j} colj A i , j A_{i,j} Ai,j进行修改即可。

源码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define MAXN 305#define MAXM 605#define lowbit(x) (x&-x)#define reg register#define mkpr make_pair#define fir first#define sec secondtypedef long long LL;typedef unsigned long long uLL;typedef unsigned int uint;typedef pair
pii;const int INF=0x7f7f7f7f;const int lim=1000000;const double PI=acos(-1.0);template
_T Fabs(_T x){ return x<0?-x:x;}template
void read(_T &x){ _T f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){ if(s=='-')f=-1;s=getchar();} while('0'<=s&&s<='9'){ x=(x<<3)+(x<<1)+(s^48);s=getchar();} x*=f;}int T,n,m,head[MAXM],tot,cnt[MAXM];LL dis[MAXM],a[MAXN][MAXN],b[MAXN][MAXN];bool inque[MAXM];queue
q;struct edge{ int to,nxt;LL paid;}e[MAXM*MAXM];void addEdge(int u,int v,LL w){ e[++tot]=(edge){ v,head[u],w};head[u]=tot;}void sakura(){ for(int i=1;i<=n+m;i++)dis[i]=INF,inque[i]=0,cnt[i]=0; dis[1]=0;q.push(1);inque[1]=1; while(!q.empty()){ int u=q.front();q.pop();inque[u]=0; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to;LL w=e[i].paid; if(dis[u]+w
min(30,n+m)){ puts("NO");return ;} if(!inque[v])inque[v]=1,q.push(v); } } } puts("YES"); for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++){ if(i+j&1)a[i][j]+=dis[i],a[i][j]-=dis[j+n]; else a[i][j]-=dis[i],a[i][j]+=dis[j+n]; printf("%lld ",a[i][j]); }}signed main(){ read(T); while(T--){ read(n);read(m);for(int i=1;i
0;i--)for(int j=m;j>0;j--)a[i][j]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ LL l=-a[i][j],r=lim-a[i][j]; if(i+j&1)addEdge(i,j+n,-l),addEdge(j+n,i,r); else addEdge(j+n,i,-l),addEdge(i,j+n,r); } sakura();for(int i=1;i<=n+m;i++)head[i]=0;tot=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=b[i][j]=0; } return 0;}

谢谢!!!

转载地址:http://mrqt.baihongyu.com/

你可能感兴趣的文章
mysql problems
查看>>
mysql replace first,MySQL中处理各种重复的一些方法
查看>>
MySQL replace函数替换字符串语句的用法(mysql字符串替换)
查看>>
mysql replace用法
查看>>
Mysql Row_Format 参数讲解
查看>>
mysql select, from ,join ,on ,where groupby,having ,order by limit的执行顺序和书写顺序
查看>>
MySQL Server 5.5安装记录
查看>>
mysql server has gone away
查看>>
mysql slave 停了_slave 停止。求解决方法
查看>>
MySQL SQL 优化指南:主键、ORDER BY、GROUP BY 和 UPDATE 优化详解
查看>>
MYSQL sql语句针对数据记录时间范围查询的效率对比
查看>>
mysql sum 没返回,如果没有找到任何值,我如何在MySQL中获得SUM函数以返回'0'?
查看>>
mysql Timestamp时间隔了8小时
查看>>
Mysql tinyint(1)与tinyint(4)的区别
查看>>
mysql union orderby 无效
查看>>
mysql v$session_Oracle 进程查看v$session
查看>>
mysql where中如何判断不为空
查看>>
MySQL Workbench 使用手册:从入门到精通
查看>>
mysql workbench6.3.5_MySQL Workbench
查看>>
MySQL Workbench安装教程以及菜单汉化
查看>>