A7442 | 无限水
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
> 这个玩家梦见了什么？
> 他梦见了阳光与草木，梦见了火与水。他梦见他创造，亦梦见他毁灭。他梦见他狩猎，亦被狩猎。他梦见了避身之处。
> ……
> 曲终人散，黄粱一梦。玩家开始了新的梦境。玩家再次做起了梦，更好的梦。玩家就是宇宙。玩家就是爱。
> 你就是那个玩家。醒来吧。
>
> ——Minecraft《终末之诗》
> 一切都结束了……吗？
Steve 修建了一个长 $n$ 格、宽 $m$ 格的水池，他想往这个水池中注满水。具体地，Steve 每次可以将一个冰块放置在某个格子中，把这个格子变成水源。同时在任意时刻，如果某个格子周围四个格子中有大于等于两个格子是水源，这个格子也会转化为水源。
请你帮 Steve 找到一种放置尽量少的冰块的方案，使得最后全部 $n\times m$ 个格子都成为水源。
输入格式
每个测试点包含多组测试数据。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据：
第一行包含两个正整数 $n,m$，表示水池的大小。
第一行包含两个正整数 $n,m$，表示水池的大小。
输出格式
*本题采用 Special Judge**，你只需要构造出任意一种符合条件的方案。同时根据你放置冰块数量的多少，你可以得到部分分，具体标准见下方的【评分方式】。
对于每组测试数据，输出 $n$ 行，其中的第 $i$ 行包含一个长度为 $m$ 的 $01$ 串 $s_{i,0}s_{i,1}\cdots s_{i,m}$。记格子 $(i,j)$ 为第 $i$ 行的第 $j$ 个格子，若 $s_{i,j}=1$，表示 Steve 要格子 $(i,j)$ 中放置冰块，否则表示不在格子 $(i,j)$ 中放置冰块。
对于每组测试数据，输出 $n$ 行，其中的第 $i$ 行包含一个长度为 $m$ 的 $01$ 串 $s_{i,0}s_{i,1}\cdots s_{i,m}$。记格子 $(i,j)$ 为第 $i$ 行的第 $j$ 个格子，若 $s_{i,j}=1$，表示 Steve 要格子 $(i,j)$ 中放置冰块，否则表示不在格子 $(i,j)$ 中放置冰块。
输入输出样例
输入 #1
0 1 3 3
输出 #1
111 110 100
【评分方式】
本题只有一份输入文件，但由于 ACGO 的限制，该题目分为 $10$ 个测试点，对于第 $i$ 个测试点，如果你在该输入文件中的得分大于等于 $10i$，则该测试点视为通过，否则视为不通过。
对于该输入文件中的每一组测试数据 $n,m$，若你构造的放置冰块的方案不合法，你在该组测试数据中获得 $0$ 分；否则设你放置了 $x$ 个冰块，该组测试数据至少要放置 $y$ 个冰块：
* 若 $x=y$，你能够获得 $100$ 分；
* 否则若 $x\le\max(n,m)$，你能获得 $80$ 分；
* 否则若 $x\le n+m$，你能获得 $60$ 分；
* 否则若 $x\le 2(n+m)$，你能获得 $50$ 分；
* 否则若 $x\le \lfloor 0.3nm\rfloor$，你能获得 $30$ 分；
* 否则若 $x\le \lfloor 0.6nm\rfloor$，你能获得 $20$ 分；
* 否则若 $x\le nm$，你能获得 $10$ 分。
你在该输入文件中的得分为所有测试数据得分中的最小值。
【样例解释】
对于第一组测试数据，放置了六个冰块，使格子 $(1,1),(1,2),(1,3),(2,1),(2,2),(3,1)$ 成为水源。格子 $(2,3),(3,2)$ 由于周围有两个水源，首先被转化为水源。因此格子 $(3,3)$ 周围有两个转化得来的水源 $(2,3),(3,2)$，进而被转化为水源。
注意该样例不满足实际测试中 $n,m\ge 10$ 的条件，且构造出的方案也无法拿到满分。
【数据范围】
对于 $100\%$ 的测试点，保证：$1\le T\le10^3$，$10 \le n,m \le 200$，单个测试点中所有测试数据的 $nm$ 之和不超过 $2\times10^5$。
本题只有一份输入文件，但由于 ACGO 的限制，该题目分为 $10$ 个测试点，对于第 $i$ 个测试点，如果你在该输入文件中的得分大于等于 $10i$，则该测试点视为通过，否则视为不通过。
对于该输入文件中的每一组测试数据 $n,m$，若你构造的放置冰块的方案不合法，你在该组测试数据中获得 $0$ 分；否则设你放置了 $x$ 个冰块，该组测试数据至少要放置 $y$ 个冰块：
* 若 $x=y$，你能够获得 $100$ 分；
* 否则若 $x\le\max(n,m)$，你能获得 $80$ 分；
* 否则若 $x\le n+m$，你能获得 $60$ 分；
* 否则若 $x\le 2(n+m)$，你能获得 $50$ 分；
* 否则若 $x\le \lfloor 0.3nm\rfloor$，你能获得 $30$ 分；
* 否则若 $x\le \lfloor 0.6nm\rfloor$，你能获得 $20$ 分；
* 否则若 $x\le nm$，你能获得 $10$ 分。
你在该输入文件中的得分为所有测试数据得分中的最小值。
【样例解释】
对于第一组测试数据，放置了六个冰块，使格子 $(1,1),(1,2),(1,3),(2,1),(2,2),(3,1)$ 成为水源。格子 $(2,3),(3,2)$ 由于周围有两个水源，首先被转化为水源。因此格子 $(3,3)$ 周围有两个转化得来的水源 $(2,3),(3,2)$，进而被转化为水源。
注意该样例不满足实际测试中 $n,m\ge 10$ 的条件，且构造出的方案也无法拿到满分。
【数据范围】
对于 $100\%$ 的测试点，保证：$1\le T\le10^3$，$10 \le n,m \le 200$，单个测试点中所有测试数据的 $nm$ 之和不超过 $2\times10^5$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？