[MCOI-06]Gerrymandering
2021/10/1 23:12:25
本文主要是介绍[MCOI-06]Gerrymandering,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定正整数 \(n,m,k\) 能否将一个 \(n\times m\) 表格染色,使得每一个颜色形成恰好一个连通块,并且每一个连通块大小为 \(k\)。如果存在,构造一个合法方案。
对于矩形涂色,使其形成连通块一个,一个常见思路是走蛇形路线:从第一行左端开始涂色,走到行末跳到下一行反向涂,涂 \(k\) 个格子换色。显然,如果 \(n\times m\) 能被 \(k\) 整除,则可以完成涂色。具体如下图所示:
所以,对于样例4 3 2
而言,我们涂色结果是这样的:
1 1 2 3 3 2 4 4 5 6 6 5
需要注意一个细节,\(\sum n\times m \le 10^6\),所以不能直接开二维数组(MLE),可以开一个一维的 \(10^6\) 的数组,只存当前行的颜色。
下面是 AC 代码,有注释:
//其实是有多测的,注意 int n, m, k; scanf("%d%d%d", &n, &m, &k); if (n * m % k != 0) puts("NO"); else { puts("YES"); int col = 1, cnt = k;//当前颜色,当前这种颜色还需要涂几格 for (int i = 1; i <= n; i++) { if (i & 1)//奇数行从左往右,偶数行从右往左 { for (int j = 1; j <= m; j++) { a[j] = col; if (--cnt == 0) cnt = k, col++;//行末换行 } } else { for (int j = m; j; j--) { a[j] = col; if (--cnt == 0) cnt = k, col++; } } for (int j = 1; j <= m; j++) printf("%d ", a[j]); putchar('\n'); } }
CF1254A和这道题的构造思路比较相似,可以一做。这道题的题解。
THE END
这篇关于[MCOI-06]Gerrymandering的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding