【题解】P3129高低卡(白金)High Card Low Card
2024-08-29 20:19:25
【题解】[P3129 USACO15DEC]高低卡(白金)High Card Low Card (Platinum)
考虑贪心。
枚举在第几局改变规则,在改变规则之前,尽量出比它大的最小的牌,在改变规则之后,尽量出最大的比它小的牌。前面记录一个\(f(x)\)后面记录一个\(g(x)\)
此时,你会发现,可能方案选择重复了,怎么办??
一般人都会放弃,但是这是正确的。
证明如下:
假设我们方案重复了\(1\)次,则必定也有一张多出来的牌。由于不存在相同的牌,则这张多出来的牌,必定比那张重复用的牌大或者小。那么,这张牌一定可以代替两种规则中都使用了一次的那张牌。不影响结果。
一张牌重复了多次时,根据上述推理,显然成立。
证毕
于是我们就可以愉悦的贪心了。
这就启示我们一定不能轻易放弃想出来却感觉不正确的算法。对于这样存在矛盾或缺陷的算法,要抓住矛盾的本质,并且推导这样的矛盾到底会不会影响答案。并且要注意矛盾所带来的影响,好的或者坏的。
最新文章
- NXP Mifare S50标准IC卡- 访问位(Access Bits) 分析
- Slave_SQL_Running: No mysql同步故障解决方法
- WAF绕过神器 (过安全狗、智创SQL注入)
- Unity3D ShaderLab 透明裁剪着色器
- CInternetSession CHttpFile Post提交数据
- Delphi 递归搜索.SVN文件夹并“处理”
- 记一次Surface Pro 2还原操作
- 读undo问题
- nrf51 官方PWM库
- windows下查找指定端口被哪个程序占用
- 如何开发基于Dubbo RPC的分布式服务?
- 关于Dapper.NET的相关论述
- CoreCLR源码探索(七) JIT的工作原理(入门篇)
- C++自己实现一个String类
- VS背景设置
- Inside a low budget consumer hardware espionage implant
- sort_gff.py
- Netty实战十之编解码器框架
- 【pyspider】启动爬虫后在results页面没有看到结果
- Alpha冲刺 - (3/10)
热门文章
- 聊聊、Zookeeper Linux 启动
- [ios]objective-c 协议和委托 (重点基础知识)
- 【ActiveMQ】1.下载安装启动使用
- 动态设置表格[GridView]在编辑时 只读。
- 经验分享 | Burpsuite抓取非HTTP流量
- python logging模块学习(转)
- 【温故知新】——Bootstrap响应式知识点复习
- Scala 中Array,List,Tuple的差别
- 【Python】使用scatter()绘制散点图
- IOS知识点收集