模拟退火是一个很实用的算法,在 OI 中可以有效地骗分甚至碾标算。其优势在于实现简单,思路简单粗暴,并且运气好的欧皇选手可以取得很不错的成绩。
反正我做过的模拟退火能过的题基本都在里面了,当然有些题正解并不是模拟退火(数据水),应该也要去学习正解。
持续更新中 \~
Part1 计算几何类
这一类是我个人觉得最经典也最正常的模拟退火使用实例,比如费马点。
- P1337 [JSOI2004]平衡点 / 吊打XXX
- UVA10228 A Star not a Tree?
- P4703 偷上网
- CF2C Commentator problem
- P5544 [JSOI2016]炸弹攻击1
- SP4587 FENCE3 - Electric Fences
- P4035 [JSOI2008]球形空间产生器
- SP34 RUNAWAY - Run Away
Part2 乱搞类
这一类能过一般来说都是数据水吧。。。建议模拟退火过去之后看看标算。
- P5194 [USACO05DEC]Scales S
- P2831 愤怒的小鸟
- P4342 [IOI1998]Polygon
- P3878 [TJOI2010]分金币
- P4360 [CEOI2004]锯木厂选址
- P2210 Haywire
- P3936 Coloring
- P2538 [SCOI2008]城堡
- P3052 [USACO12MAR]Cows in a Skyscraper G
- P3475 [POI2008]POD-Subdivision of Kingdom
- P4212 外太空旅行
- P1248 加工生产调度
- P1001 A+B Problem