博客
关于我
[省选联考 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 索引深入解析及优化策略
查看>>
MySQL 索引的面试题总结
查看>>
mysql 索引类型以及创建
查看>>
MySQL 索引连环问题,你能答对几个?
查看>>
Mysql 索引问题集锦
查看>>
Mysql 纵表转换为横表
查看>>
mysql 编译安装 window篇
查看>>
mysql 网络目录_联机目录数据库
查看>>
MySQL 聚簇索引&&二级索引&&辅助索引
查看>>
Mysql 脏页 脏读 脏数据
查看>>
mysql 自增id和UUID做主键性能分析,及最优方案
查看>>
Mysql 自定义函数
查看>>
mysql 行转列 列转行
查看>>
Mysql 表分区
查看>>
mysql 表的操作
查看>>
mysql 视图,视图更新删除
查看>>
MySQL 触发器
查看>>
mysql 让所有IP访问数据库
查看>>
mysql 记录的增删改查
查看>>
MySQL 设置数据库的隔离级别
查看>>