[CF1517C]Fillomino 2
2021/4/24 18:25:09
本文主要是介绍[CF1517C]Fillomino 2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 壹、题目描述 ¶
- 贰、题解 ¶
壹、题目描述 ¶
传送门 to CF
贰、题解 ¶
考试的时候感觉它存在贪心思路,就随便打了一个贪心填发:
考虑每个点都是从 \((x,x)\) 开始走,如果我们当前走到了 \((i,j)\),如果能够往 \((i-1,j)\) 走,就往 \((i-1,j)\) 走,不然依次考虑 \((i,j-1),(i+1,j),(i,j+1)\) 走,直到这个数字被填完为止。
然后,它就过了......
事后看了一下 \(\rm tutorial\) 里面关于这道题的证明,它使用很巧妙的方法进行递归:
先从数字为 \(1\) 的那个格子开始,假设 \((x,x)\) 上填的数字是 \(1\),那么它一定是自成一块。
对于 \((y,y)(y<x)\) 的格子,将 \((y+1,y)\)(就是往下走一格)和 \((y,y)\) 绑在一起,对于 \((z,z)(z>x)\) 的格子,将 \((z,z-1)\)(就是往左走一个)和 \((z,z)\) 绑在一起,然后递归处理这个问题,到最后它一定是有解的。
这篇关于[CF1517C]Fillomino 2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置