博客
关于我
[省选联考 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 多个表求多个count
查看>>
mysql 多字段删除重复数据,保留最小id数据
查看>>
MySQL 多表联合查询:UNION 和 JOIN 分析
查看>>
MySQL 大数据量快速插入方法和语句优化
查看>>
mysql 如何给SQL添加索引
查看>>
mysql 字段区分大小写
查看>>
mysql 字段合并问题(group_concat)
查看>>
mysql 字段类型类型
查看>>
MySQL 字符串截取函数,字段截取,字符串截取
查看>>
MySQL 存储引擎
查看>>
mysql 存储过程 注入_mysql 视图 事务 存储过程 SQL注入
查看>>
MySQL 存储过程参数:in、out、inout
查看>>
mysql 存储过程每隔一段时间执行一次
查看>>
mysql 存在update不存在insert
查看>>
Mysql 学习总结(86)—— Mysql 的 JSON 数据类型正确使用姿势
查看>>
Mysql 学习总结(87)—— Mysql 执行计划(Explain)再总结
查看>>
Mysql 学习总结(88)—— Mysql 官方为什么不推荐用雪花 id 和 uuid 做 MySQL 主键
查看>>
Mysql 学习总结(89)—— Mysql 库表容量统计
查看>>
mysql 实现主从复制/主从同步
查看>>
mysql 审核_审核MySQL数据库上的登录
查看>>