《提交答案型题目解题方法讲解》由会员分享，可在线阅读，更多相关《提交答案型题目解题方法讲解（56页珍藏版）》请在金锄头文库上搜索。
1、提交答案型题目解题方法提交答案型题目解题方法 清华大学清华大学 交叉信息研究院交叉信息研究院 赵金昊赵金昊 2016.52016.5 写写在最前面在最前面 如果没有接触过提交答案型题目，可能会觉得这节课很有趣 如果接触过提交答案型题目，可能会觉得这节课很无聊 为了避免后一种情况，我为这些同学准备了替代方案 （前提是要带电脑呀） 一道提交答案型试题坦克大战坦克大战 讲座结束时提交，根据得分可以获得纪念品 试题获取：见某同性交友群；或者 提交地址：957685908QQ.COM；或者直接U盘交也行 XfI9 提交答案是什么？提交答案是什么？ 题面 1.in 2.in 10.in abc.cpp a
2、bc.exe 1.out 2.out 10.out 1.ans 2.ans 10.ans +0 +0 +0 Wrong Answer! 传统型传统型 题面 1.in 2.in 10.in 1.out 2.out 10.out 1.ans 2.ans 10.ans +10 +10 +10 AC! 提交答案型提交答案型 2.exe 1.exe 瞎猜. exe 为什么要学习提交答案？为什么要学习提交答案？ 大多数OI比赛中都有提交答案 IOI、NOI、省选、WC、APIO、CTSC NOIP是什么鬼 怎么做提交答案？怎么做提交答案？ 如果一页PPT就说完了，这个讲座也太没价值了吧 快速上手快速上手举
3、个栗子举个栗子 NOI2012 DAY2 三重镇 提交答案题目的做法提交答案题目的做法 题目是第一位的，每道题都有其独特的解法 当然以下这些算法很通用啦 常用算法常用算法1.1.手算手算 留意输入文件中特别小的数据，往往是可以手算的。 （而且手算比写代码快得多呀） 常用算法常用算法2.2.搜索搜索 暴力可以战胜一切！ 对于有些数据，搜索就是正确的做法。 对于另外一些数据，搜索可以得到漂亮的部分分。 程序的运行时间可以是5个小时！ 常用算法常用算法3.3.非完美程序非完美程序 有时数据是有规律的，与题目条件结合，题目就会 变成DP 变成DP 变成DP 变成贪心 常用算法常用算法4.4.程序辅助构
4、造程序辅助构造 有时对应的数据是构造类的，但是很长，需要写程序来输出。 （有些题目全都是构造，简直可怕呀） 常用算法常用算法5.5.骗分骗分 大多数题目有输出就有1分 手敲10个合法输出就是10分呀 常用算法常用算法6.6.启发式搜索启发式搜索 在状态空间中的搜索对每一个搜索的位置进行评估，得到最好 的位置，再从这个位置进行搜索直到目标。这样可以省略大量 无谓的搜索路径，提高了效率。 通俗地说就是奇技淫巧。 在传统类题目中基本只能用来骗分，但却是许多提交答案题目 的正确解法。 常用算法常用算法6.6.启发式搜索启发式搜索 常见的启发式搜索算法有： 爬山算法 模拟退火 蚁群算法 遗传算法 6.1
5、 6.1 爬山算法爬山算法 给定F(X)为一个未知的函数，求最大值？ 选择一个状态作为基准，然后从基准态开始向相邻位置扩展 相邻位置若更优，则替换为新的基准态 往往会得到极大值 重复以上步骤，就可以得到最大值啦 6.1 6.1 爬山算法爬山算法 二维的情况呢？ 选择一个状态作为基准，然后从基准态开始向相邻位置扩展扩展 相邻位置若更优，则替换为新的基准态 往往会得到极大值极大值 重复以上步骤，就可以得到最大值啦 6.1 6.1 爬山算法爬山算法 N维的情况呢？ 选择一个状态作为基准，然后从基准态开始向相邻位置扩展扩展 相邻位置若更优，则替换为新的基准态 往往会得到极大值极大值 重复以上步骤，就可
6、以得到最大值啦 6.1 6.1 爬山算法爬山算法 N维的情况呢？ 随机向某个方向扩展 差不多收敛时即认为已达到极大值 6.1 6.1 爬山算法爬山算法 总结 1.随机（或简单搜索后）选取一个状态 2.随机改变变量，替换为更优的状态，直到达到极值 3.重复12 6.2 6.2 模拟退火模拟退火 爬山算法隐藏的风险在哪里？ 初始状态基本确定了这次调整的结果 如果可以跳出局部最优呢？ 6.2 6.2 模拟退火模拟退火 退火是什么？ 初始时，物体处于高能量和高温度 物体最终能量尽可能低 温度越高，粒子越活跃，更容易变化 温度越低，粒子越稳定，更容易保持原状 结束状态有可能也是极小值 6.2 6.2 模
7、拟退火模拟退火 思路： 用时间T来代表温度。 随着时间的推移，变化的概率越来越小。 6.2 6.2 模拟退火模拟退火 6.2 6.2 模拟退火模拟退火 特殊情况： 概率不随时间变化，而是常数呢？ 随机化贪心 6.2 6.2 模拟退火模拟退火 总结： 1.随机（或简单搜索后）选取一个状态 2.随机改变变量，当更优时直接跳转，当更劣时有概率跳转。 3.2中的概率随时间变小。稳定时即认为达到极值。 4.重复123 6.3 6.3 蚁群算法蚁群算法 另一种跳出局部最优的方法： 即使更优也不一定接受？ 6.3 6.3 蚁群算法蚁群算法 蚁群： 每只蚂蚁都会在路径上留下信息素 后面的蚂蚁会朝着信息素多的方
8、向前进 但每一步都有一定概率犯错误，从而开辟新的道路 蚂蚁是往返前进，因此在较短的路上留下的信息素多，从而较 短的路可以吸引更多蚂蚁 信息素会消失 6.3 6.3 蚁群算法蚁群算法 思路： 用这条路线的结果，来为每个节点增加信息素，结果越好，信 息素越多。 每次更换状态时，有高概率到信息素最大的方向，也有低概率 随机变换。 6.3 6.3 蚁群算法蚁群算法 选取初始状态。 向周围扩展，但是 以高概率选取信息素最大的节点。 以低概率随机选取。 没有信息素时，可以判断局部状态，也可以完全随机。 以一定规则添加和删除信息素 6.3 6.3 蚁群算法蚁群算法 反向思考：禁忌搜索 搜索过的路径再搜一次没
9、有什么意义 以更低的概率进入走过的状态 6.3 6.3 蚁群算法蚁群算法 总结： 1.选取一种扩展方式。 2.以小概率犯错的方式，向信息素高(低)的方向扩展。 3.以一定方式向节点添加信息素 4.重复23 6.4 6.4 遗传算法遗传算法 一种新的思路： 通过已有的解法，能否得到更优的？ 将两种解法合并一下？ 6.4 6.4 遗传算法遗传算法 直接合并： 合并每一组变量，随机选择/取平均值 间接合并： 合并搜索的参数、中间状态 6.4 6.4 遗传算法遗传算法 总结： 种群：由一定的个体组成 个体的产生：遗传/变异 遗传通过已有的个体合并得到 变异有低概率发生，产生新的个体 个体的消失：淘汰
10、通过评估函数，淘汰最差的个体 Q Exec(checker.exe,input.txt output.txt); Exec(del *.out,); C+: #include system(“checker.exe input.txt output.txt”); system(“del *.out”); 一些小技巧一些小技巧 输入输出重定向 windows: program.exe output.txt linux: ./program.exe output.txt 回到回到刚才刚才的题目的题目 一定要看数据！一组一组地来吧。 tritown1.in 3 3 0 0 .1. .11 . 30
11、2 4 1 4 2 1 3 1 1 1 1 2 1 1 2 1 1 2 2 1 1 1 2 1 1 1 2 1 1 4 手算！手算！ tritown2.in 1 3 40 60 80 9 9 9 9 9 9 9 9 9 9 6 9 8 5 9 2 4 1 8 3 9 3 8 7 8 6 8 9 4 1 1 7 6 1 5 8 7 6 9 6 3 1 3 1 7 5 9 2 8 4 3 7 3 4 7 3 4 8 3 2 6 6 2 7 4 8 3 4 8 5 5 3 6 7 1 2 5 6 5 9 动态规划动态规划 ftijksb 进行到操作序列的第t 个，且当前从左到右 的方块分别为i,j,
12、k，有 s个STAR和b个 BOMBER时，所获得 的最高分数 tritown3.in 1 3 100 300 400 9 9 9 9 9 9 9 9 9 9 6 9 8 5 9 2 4 1 8 3 9 3 8 7 8 6 8 9 4 1 1 7 6 1 5 8 7 6 9 6 3 1 3 1 7 5 9 2 8 4 3 7 3 4 7 3 4 8 3 2 6 6 2 7 4 8 3 4 8 5 5 3 6 7 1 2 5 6 5 5 6 1 6 7 8 6 4 7 4 3 1 6 1 2 1 6 8 6 9 2 7 4 3 2 3 2 9 4 7 9 1 3 5 4 7 4 1 3 3 4
13、9 9 6 2 7 7 3 4 4 7 2 7 9 7 9 9 4 5 9 2 9 8 4 8 8 2 4 6 8 7 5 3 7 7 6 9 8 3 3 4 6 8 3 8 7 9 1 3 7 9 5 6 4 9 3 4 2 1 3 6 5 3 6 5 7 1 7 7 4 5 2 1 9 2 4 3 7 9 2 9 3 8 7 2 6 1 1 3 8 2 9 3 9 1 9 3 5 3 2 1 6 2 4 3 5 6 1 2 7 7 5 4 2 9 6 1 4 4 7 6 3 9 6 9 2 5 7 7 8 8 9 6 2 3 3 9 7 2 5 1 3 7 9 4 7 3 2 9 3 3
14、8 1 4 4 3 4 9 4 5 3 3 1 2 9 9 3 9 9 7 5 6 1 1 7 1 8 8 2 9 8 8 8 7 7 5 9 3 4 9 9 6 1 2 1 6 8 6 8 8 9 5 7 2 1 3 4 8 5 2 2 5 5 4 8 5 3 4 5 9 5 9 2 9 4 7 2 6 8 9 6 3 2 1 2 4 9 6 3 3 1 8 2 4 2 5 5 4 9 2 2 1 3 5 9 3 6 4 7 1 9 1 9 3 4 2 7 2 6 9 6 5 6 4 3 6 8 9 5 9 9 tritown4.in 1 100 0 0 . . 360 1 1 1 1 1
15、1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
