博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【Atcoder】AGC 016 C - +/- Rectangle
阅读量:6767 次
发布时间:2019-06-26

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

【题意】给定大矩阵的边长H和W,给每格填数(<=|10^9|),要求大矩形总和为正数,而每个h*w的小矩形总和为负数,求构造方式。

【算法】数学

【题解】结论题。

★当h|H&&w|W(H是w的倍数,W是w的倍数)时,每个小矩阵之和加起来翻倍刚好成为大矩阵,无解。

当不为倍数时,显然会有多余的行列,我们尝试一种构造方式使多余的行列起作用。

1.从0计数,在h倍数行全部填正数1000(h-1)-1,在其他行全部填负数-1000(行是倍数时换成列,同理)。

这样构造,在h行范围内只有一行正数,每列之和都是-1。而论总和而言,多余行也有一行正数,小矩阵不满,所以每列至少多出1000-500,解决问题。

2.另一种构造方式,从1计数,在每个h*w倍数处填-1000*(h*w-1)-1,其它地方填1000,这样只要有一多余行列,多的若干个1000就可以将矩阵变成正数。

关键在第一个倍数无解的结论,有解时只要利用多余行列构造即可。

#include
#include
#include
#include
#include
#define ll long longusing namespace std;int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t;}/*------------------------------------------------------------*/const int inf=0x3f3f3f3f; int N,M,n,m; int main(){ scanf("%d%d%d%d",&N,&M,&n,&m); if(N%n==0&&M%m==0){printf("No");return 0;} printf("Yes\n"); for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++) printf("%d ",i%n||j%m?1100:-1100*(n*m-1)-1); printf("\n"); } return 0;}
View Code

 

转载于:https://www.cnblogs.com/onioncyc/p/7358734.html

你可能感兴趣的文章
#51CTO学院四周年# 又一年的碎碎念,感谢现在奋斗的自己
查看>>
vi tips
查看>>
程序书籍推荐
查看>>
救援模式修复bootloader
查看>>
公告:文字/图片滑动显示功能Scrollamount和scrolldela
查看>>
coreData
查看>>
Android开机logo
查看>>
Veeam Backup & Replication(三):创建备份与还原备份
查看>>
配置 失败 的 lamp 过程
查看>>
Exchange Server 2010系列之一:了解Exchange角色
查看>>
Exchange Server2010系列之四:初谈邮箱基本管理
查看>>
我的友情链接
查看>>
我的友情链接
查看>>
sql server 2008以上数据库 收缩事务日志
查看>>
Exchange 2013服务器常用的性能监视器
查看>>
详解linux运维工程师入门级必备技能
查看>>
创建pacemaker+corosync集群
查看>>
Xshell使用密钥认证机制远程登录Linux
查看>>
PHP重命名和移动目录
查看>>
服务器内存缓存的设计与实现
查看>>