音乐播放器
HMF-have much fun Site
 
文章 标签
16
✎首页 ✎首页
☰归档 ☰归档
★标签 ★标签
☎关于 ☎关于
♚推荐 ♚推荐
说说 说说
友人帐 友人帐
Powered by Gridea | Theme: Fog
载入天数...
载入时分秒...
总访问量:  |   访问人数:
Copyright © 2020 备案号: 闽ICP备21335467号
阅
2022-03-25
2 min read
CodeForce 题解

【题解】CF1638D Big Brush

  热度: loading...

考场上想出来了，可惜被抓去睡觉了。

首先如果我们要正着构造的话不太好构造，这时候我们观察到一个特点：在最后一步操作后一定会留下一个 2×22 \times 2 的同色方格，这就引导我们往构造题的常见套路——反向构造来想。

考虑将一个 2×22 \times 2 方块染成同色的反操作：将一个 2×22 \times 2 的同色方块替换成任意颜色。将无色方块看成可以变作任意颜色的方块，操作变为将 2×22 \times 2 的同色方块变为无色，之后由于无色方块可以变作任何颜色，因此如果有一个残缺的 2×22 \times 2 同色方块但其所缺少的部分是无色方块，那我们就可以直接将无色方块看做这种颜色，直接将其消掉。

考虑消掉一个 2×22 \times 2 方块后影响的最多是以其为中心的 4×44 \times 4 方块，其左上角最多在原本左上角的八连通块位置，因此往原本左上角的八连通块搜索即可，代码简单，可以自行写出。

掉大分.jpg

赏
  • 文章作者：Linky
  • 原文链接：https://lookcatbox.github.io/post/ti-jie-cf1638d-big-brush/
  • 版权声明：本博客所有文章除特别声明外，均采用BY-NC-SA 许可协议。转载请注明出处！