AT2043 [AGC004C] AND Grid
2024-10-19 22:18:24
首先可以发现一个很简单的想法,因为最外层是一定不会有 \(\#\) 的,所以可以考虑让第一个网格图将每个连通块的最外层包起来,第二个网格图将就选择这个包内部的所有点即可。
但你发现这个想法是很难实现的,只能去寻找其他的做法了。
继续沿用刚刚将连通块贴着的想法,只不过我们现在都用一条横线贴着连通块。
为了保证联通,我们让两个网格图各自占据第一列和最后一列的所有点,然后将横线连到第一列和最后一列上。
但是这样还是有问题,当两个连通块上下交错一个距离时,两个网格图还是会相交,多个连通块形成这样的结构时,也不能通过选择上下底面贴着联通的办法。
但是上面这个网格图的结构给予了我们提示,能否用这种横线将这一行上的连通块串起来呢?
于此同时,为了避免横线相交的情况,最简单的方法就是让一行只有一种横线。
因为两边是同样重要的,因此需要让两边占的行数尽可能相同。
这样一来,当一个连通块占据两行时,只需要让这几行中出现不同种类的横线即可。
又因为两种横线数量相同,可以考虑直接按照奇偶分布直线。
那么就只需要考虑单占一行的连通块了。
通过上面的构造可以发现,显然会有一遍能直接将这个联通块串起来,而这个连通块的边上一定会是另一种横线,因为 \(i, i + 1\) 不同奇偶。
因此,本题的构造方法已经浮现出来了:
- 令两个网格图分别为 \(A, B\),将第一列分配给 \(A\),最后一列分配给 \(B\),其中对于任意一行 \(i = 2k + 1\) 将 \((i, 2) \sim (i, m - 1)\) 分配给 \(A\),对于 \(i = 2k\) 将 \((i, 2) \sim (i, m - 1)\) 分配给 \(B\)。
时间复杂度 \(O(nm)\)。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 500 + 5;
int n, m;
char s[N][N], a[N][N], b[N][N];
int read() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main() {
n = read(), m = read();
rep(i, 1, n) rep(j, 1, m) a[i][j] = b[i][j] = '.';
rep(i, 1, n) {
scanf("%s", s[i] + 1);
rep(j, 1, m) if(s[i][j] == '#') a[i][j] = b[i][j] = '#';
}
rep(i, 1, n) a[i][1] = '#', b[i][m] = '#';
rep(i, 1, n) {
if(i & 1) rep(j, 1, m - 1) a[i][j] = '#';
else rep(j, 2, m) b[i][j] = '#';
}
rep(i, 1, n) {
rep(j, 1, m) printf("%c", a[i][j]);
puts("");
}
puts("");
rep(i, 1, n) {
rep(j, 1, m) printf("%c", b[i][j]);
puts("");
}
return 0;
}
可以发现,本题的构造从难以实现的想法出发,一步步简化到达了一个非常简单并且优秀的做法。
因此,当构造时出现实现困难的问题时,尽量简化流程方法本质不变的情况下往往能找到非常简单的构造方法。
最新文章
- 使用Java代码实现对宽带的连接
- MEF入门之不求甚解,但力求简单能讲明白(一)
- 四、卫星定位《苹果iOS实例编程入门教程》
- IIS7下的伪静态配置
- 使用easyui时 进入一个新页面 前要经过一个页面混乱的时候 才到正常的页面去
- 如何增强 Linux 系统的安全性,第一部分: Linux 安全模块(LSM)简介
- HDU 2602(01背包)
- python 迭代器、生成器、装饰器
- CSS 文本格式
- 2014年基于Raspberry Pi的5大项目
- MySQL的备份和恢复
- iphone手机中对于html和css的一些特殊处理
- 【AIX】AIX内存机制
- Eclpse 标准版,在联想一体机上报 eclipse failed to create the java virtual machine
- .NET Core 中基于 IHostedService 实现后台定时任务
- Android 隐藏系统状态栏
- spring cloud 版本号与 boot版本之间的对应关系(版本不对,会导致pom无法引入)
- python中的__getattr__、__getattribute__、__setattr__、__delattr__、__dir__
- sync 解释
- hdoj1203 I NEED A OFFER!(DP,01背包)
热门文章
- Regularizing Deep Networks with Semantic Data Augmentation
- CHARACTERIZING ADVERSARIAL SUBSPACES USING LOCAL INTRINSIC DIMENSIONALITY
- c++定时器执行任务
- IM2605说明书| InmicroIM2605|IM2605芯片
- 编写Java程序,判断输入的三条长度的边,是否能构成三角形
- .net core的配置介绍(三):Options
- TortoiseGit使用技巧
- Unity——ShaderLab实现玻璃和镜子效果
- Nginx 全模块安装及匹配方式、反向代理和负载均衡配置
- Git_使用SSH密钥操作远端仓库