当前位置:首页 >> 学科竞赛 >>

提交答案型题目解题方法


提交答案型题目解题方法
清华大学 交叉信息研究院
赵金昊

2016.5

写在最前面…
? 如果没有接触过提交答案型题目,可能会觉得这节课很有趣 ? 如果接触过提交答案型题目,可能会觉得这节课很无聊 ? 为了避免后一种情况,我为这些同学准备了替代方案 ? (前提是要带电脑呀) ? 一道提交答案型试题——坦克

大战 ? 讲座结束时提交,根据得分可以获得纪念品~ ? 试题获取:见某同性交友群;或者 http://pan.baidu.com/s/1i4WXfI9 ? 提交地址:957685908@QQ.COM;或者直接U盘交也行

提交答案是什么?
1.in abc.cpp 1.out 2.out … abc.exe 10.out 1.ans 2.ans … 10.ans +0

题面

2.in … 10.in

+0
+0

Wrong Answer!

传统型
1.in 题面 2.in … 10.in 1.exe 2.exe 瞎猜.exe 1.out 2.out … 10.out 1.ans 2.ans … 10.ans AC! +10 +10

+10

提交答案型

为什么要学习提交答案?
? 大多数OI比赛中都有提交答案 ? IOI、NOI、省选、WC、APIO、CTSC ? NOIP是什么鬼

怎么做提交答案?
? 如果一页PPT就说完了,这个讲座也太没价值了吧……

快速上手——举个栗子
? NOI2012 DAY2 三重镇

提交答案题目的做法
? 题目是第一位的,每道题都有其独特的解法 ? 当然以下这些算法很通用啦

常用算法——1.手算
? 留意输入文件中特别小的数据,往往是可以手算的。 ? (而且手算比写代码快得多呀)

常用算法——2.搜索
? 暴力可以战胜一切! ? 对于有些数据,搜索就是正确的做法。 ? 对于另外一些数据,搜索可以得到漂亮的部分分。 ? 程序的运行时间可以是5个小时!

常用算法——3.非完美程序
? 有时数据是有规律的,与题目条件结合,题目就会 ? 变成DP ? 变成DP ? 变成DP ? 变成贪心

常用算法——4.程序辅助构造
? 有时对应的数据是构造类的,但是很长,需要写程序来输出。 ? (有些题目全都是构造,简直可怕呀)

常用算法——5.骗分
? 大多数题目有输出就有1分 ? 手敲10个合法输出就是10分呀

常用算法——6.启发式搜索
? 在状态空间中的搜索对每一个搜索的位置进行评估,得到最好 的位置,再从这个位置进行搜索直到目标。这样可以省略大量 无谓的搜索路径,提高了效率。 ? 通俗地说就是奇技淫巧。

? 在传统类题目中基本只能用来骗分,但却是许多提交答案题目 的正确解法。

常用算法——6.启发式搜索
? 常见的启发式搜索算法有: ? 爬山算法 ? 模拟退火 ? 蚁群算法 ? 遗传算法

6.1 爬山算法
? 给定F(X)为一个未知的函数,求最大值? ? 选择一个状态作为基准,然后从基准态开始向相邻位置扩展 ? 相邻位置若更优,则替换为新的基准态 ? 往往会得到极大值 ? 重复以上步骤,就可以得到最大值啦

6.1 爬山算法
? 二维的情况呢? ? 选择一个状态作为基准,然后从基准态开始向相邻位置扩展 ? 相邻位置若更优,则替换为新的基准态 ? 往往会得到极大值 ? 重复以上步骤,就可以得到最大值啦

6.1 爬山算法
? N维的情况呢? ? 选择一个状态作为基准,然后从基准态开始向相邻位置扩展 ? 相邻位置若更优,则替换为新的基准态 ? 往往会得到极大值 ? 重复以上步骤,就可以得到最大值啦

6.1 爬山算法
? N维的情况呢? ? 随机向某个方向扩展 ? 差不多收敛时即认为已达到极大值

6.1 爬山算法
? 总结 ? 1.随机(或简单搜索后)选取一个状态 ? 2.随机改变变量,替换为更优的状态,直到达到极值 ? 3.重复12

6.2 模拟退火
? 爬山算法隐藏的风险在哪里? ? 初始状态基本确定了这次调整的结果 ? 如果可以跳出局部最优呢?

6.2 模拟退火
? 退火是什么? ? 初始时,物体处于高能量和高温度 ? 物体最终能量尽可能低 ? 温度越高,粒子越活跃,更容易变化 ? 温度越低,粒子越稳定,更容易保持原状 ? 结束状态有可能也是极小值

6.2 模拟退火
? 思路: ? 用时间T来代表温度。 ? 随着时间的推移,变化的概率越来越小。

6.2 模拟退火
?

6.2 模拟退火
? 特殊情况: ? 概率不随时间变化,而是常数呢? ? 随机化贪心

6.2 模拟退火
? 总结: ? 1.随机(或简单搜索后)选取一个状态 ? 2.随机改变变量,当更优时直接跳转,当更劣时有概率跳转。 ? 3.2中的概率随时间变小。稳定时即认为达到极值。 ? 4.重复123

6.3 蚁群算法
? 另一种跳出局部最优的方法: ? 即使更优也不一定接受?

6.3 蚁群算法
? 蚁群: ? 每只蚂蚁都会在路径上留下信息素 ? 后面的蚂蚁会朝着信息素多的方向前进 ? 但每一步都有一定概率犯错误,从而开辟新的道路 ? 蚂蚁是往返前进,因此在较短的路上留下的信息素多,从而较 短的路可以吸引更多蚂蚁 ? 信息素会消失

6.3 蚁群算法
? 思路: ? 用这条路线的结果,来为每个节点增加信息素,结果越好,信 息素越多。

? 每次更换状态时,有高概率到信息素最大的方向,也有低概率 随机变换。

6.3 蚁群算法
? 选取初始状态。 ? 向周围扩展,但是 ? 以高概率选取信息素最大的节点。 ? 以低概率随机选取。 ? 没有信息素时,可以判断局部状态,也可以完全随机。 ? 以一定规则添加和删除信息素

6.3 蚁群算法
? 反向思考:禁忌搜索 ? 搜索过的路径再搜一次没有什么意义 ? 以更低的概率进入走过的状态

6.3 蚁群算法
? 总结: ? 1.选取一种扩展方式。 ? 2.以小概率犯错的方式,向信息素高(低)的方向扩展。 ? 3.以一定方式向节点添加信息素 ? 4.重复23

6.4 遗传算法
? 一种新的思路: ? 通过已有的解法,能否得到更优的? ? 将两种解法合并一下?

6.4 遗传算法
? 直接合并: ? 合并每一组变量,随机选择/取平均值 ? 间接合并: ? 合并搜索的参数、中间状态

6.4 遗传算法
? 总结: ? 种群:由一定的个体组成 ? 个体的产生:遗传/变异 ? 遗传通过已有的个体合并得到 ? 变异有低概率发生,产生新的个体 ? 个体的消失:淘汰 ? 通过评估函数,淘汰最差的个体

Q&A

提交答案题目特点
? 每个数据点通常都有部分分(骗分大法好哈哈哈哈哈) ? 不涉及复杂的算法 ? 往往会提供CHECKER,考场上可以知道自己的(YOU)得(GUI)分(LE) ? 数据也是题目的一部分,语文能力要求高 ? 代码量大(也许就是10道不同的题)

经常被坑的地方…
? 把输入搞丢了 ? LINUX不够熟练 ? 不会用CHECKER

一些小技巧
? 在程序中执行命令 Pas: Uses dos; Exec(?checker.exe?,?input.txt output.txt?); Exec(?del *.out?,??);

C++: #include<cstdlib> system(“checker.exe input.txt output.txt”); system(“del *.out”);

一些小技巧
? 输入输出重定向 windows: program.exe < input.txt > output.txt linux: ./program.exe < input.txt > output.txt

回到刚才的题目…
? 一定要看数据!一组一组地来吧。

tritown1.in 33 00 .1. .11 ... 30 24142131111211211221 1121112114

手算!

tritown2.in 13 40 60 … 80 99999999996985924183 93878689411761587696 31317592843734734832 66274834855367125659

动态规划
f[t][i][j][k][s][b] 进行到操作序列的第t 个,且当前从左到右 的方块分别为i,j,k,有 s个STAR和b个BOMBER 时,所获得的最高分 数

tritown3.in 13 100 300 … 400 99999999996985924183 93878689411761587696 31317592843734734832 66274834855367125655 61678647431612168692 74323294791354741334 99627734472797994592

tritown4.in 1 100 00 ............................................................................ ........................ 360 11111111111111111111 11111111111111111111 11111111111111111111 11111111111111111111 11111111111111111111 11111111111111111111

构造
最多只能用9个1建造出 3 两个3之间必须空两格 最后没有空位只能造2 了

tritown5.in 20 20 00 .................... .................... … .................... 11000 11111111111111111111 11111111111111111111 11111111111111111111 11111111111111111111

构造
同样,最多只能构造出5

简单的想法是用5*5的方 格造出5
但空两格不能得到满分, 存在只空一格的构造

tritown6.in 1 20 2383 0 .................... 0

构造
递归地造STAR

目测是最水的一组数据

tritown7.in
66 00 ...... ...... ...... ...... ...... ...... 1231 11111111111111122111 11111122211123111111 11111111121111112111

乱搞
就当是真的在玩就行了

可能的优化:
相近的数尽可能放在一起 连续的数直接当成高级来 处理(9个1当成3)

8和7一样,范围大了点 9多了初始状态 10多了一些STAR和BOMB 都是乱搞,不说了……

还有什么题目吗
WC2015 未来程序

给定一段代码(PAS/C/C++)和它的输入,计算出它的输出。

program1.cpp #include <stdio.h> #include <stdlib.h> void _() { unsigned long long a, b, c, d, i; scanf("%llu %llu %llu", &a, &b, &c); i = 0; d = 0; while (i < b) { d = d + a; d = d % c; i = i + 1; } printf("%llu\n", d);

快速乘法?

program4.cpp #include <stdio.h> unsigned long long s0, s1, s2, s3, s4, i, n; int main() { scanf("%llu", &n); i = 0; while (i <= n) { s0 = s0 + 1; s1 = s1 + i; s2 = s2 + i * i; s3 = s3 + i * i * i; s4 = s4 + i * i * i * i; i = i + 1; }

n次方和公式

program7.cpp #include <stdio.h> #include <string.h> #include <iostream> using namespace std; char s[20][20]; bool check() { for (int i = 0; i <= 15; i++) { bool v[16]; memset(v, false, sizeof(v)); for (int j = 0; j <= 15; j++) { v[s[i][j] - 'A'] = true; }

什么鬼…

还有什么题目吗
WC2014 非确定机 反转运行一个程序,根据输出,找到对应的输入 APIO2013 出题人 对于给定的几个最短路算法的程序,造出数据卡掉某一个而另外 一个可以过 NOI 2014 消除游戏

A GAME FOR NANNAN

简单的总结
? 同时关注题面和输入数据 ? 对不同的数据进行不同的处理 ? 熟悉基本的操作

Q&A

完结撒花~
清华大学 交叉信息研究院
赵金昊

完成于 2016.5.6 02:00


相关文章:
细节理解题的解题步骤和方法
细节理解题解题步骤和方法一、 细节理解题.是高考英语阅读理解最重要的一类...1. 同样, 按照答案在原文中出现的位置, 细节理解题可以分为集中型细节理解题...
题型一体现类主观题答题技巧与训练
解答技巧】 无论是归纳型还是演绎型的题目,其实都可以牢记“答案必在材料中...(3)将修订后的规划提交市人大审议、表决通过后再实施,体现了党坚持依法执政。 ...
理论题库及答案
理论模拟1-4题库及答案 82页 免费 解答生物概念类...30. 审查 是指建设单位对施工单位提交的工程预算书...149. 大、中 型直流电机的电枢绕组的线圈,一般采用...
110101100101高考政治考试题答题一般技巧集
题思路) 切题--联系知识、选择内容、构思答案 答题...按照试题的思维特点,主观题可分为:演绎型主观题和...需要将最终交稿格式提交检测, 将影响降到最小,此影响...
行测答题技巧:主旨观点型题解题技巧
行测答题技巧:主旨观点型题解题技巧【导语】 在事业...也就是说没有必要人为的划分直译 和意译,故答案为...伊拉克方面与外国石油公司的 任何争端都必须提交国际...
2007年12月全国统考QMS推理题解题方法
2007 年 12 月全国统考 QMS 推理题解题方法 例一,推理题,选出正确答案填入空格(单选):某机构向 CCAA 提交注册申请表,申请领域可能由以下领域和级别组成,其 中...
事业单位考试——行测答题技巧:主旨观点型题解题技巧
主旨观点型题解题技巧【导语】 在事业单位行测考试中...也就是说没有必要人为的划分直译 和意译,故答案为...伊拉克方面与外国石油公司的 任何争端都必须提交国际仲裁...
生产动作管理随堂练习题答案
题答案本次练习有 202 题,你已做 10 题,已提交 10 题,其中答对 10 题。...的产品性质 B.不同的生产规模 C.不同的品种数量 D.不同的工艺方法 答题: ...
一级法规用书第4次增值服务-解题技巧
一级法规用书第4次增值服务-解题技巧_从业资格考试_...200 万元 此题的答案是 D。其书中相关的知识点是...(A)开标的时间应在提交投标文件截止时间后 3 天内...
PMP考试试题及答案解析
、 1) 项目范围说明书: 详细描述项目的可交付成果, 以及为提交这些可交付成果...的层级分解 ○DWBS 是对项目活动的层级分解 正确答案:A 试题解答:.正确答案。...
更多相关标签:
无解题 题目 | 画图解题题目 | 化工原理解题指南答案 | 数学分析解题指南答案 | 传热学要点与解题答案 | 四宫格解题技巧和答案 | 提交答案题 | 提交答案型 |