nbhkdz.com冰点文库

wc2014


IOI2013 Day1试 题讨论 及几题非传统趣题讨论
南京外国语学校 许昊然

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

给定一幅分辨率不超过500*500的油

画照片,要求判断这幅油画是题目 给定的4种类型中的哪一种。题目免费附赠了36幅图片(每种类 型9张)以帮助你测试自己的程序。 得分公式: 正确率小于25%:0分 正确率25%~50%:0分~10分,得分与正确率线性关系 正确率50%~90%:10分~100分,得分与正确率线性关系 正确率90%以上:100分

下面是作品鉴赏时间. . . . . .

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
第一种可能的风格是:新造型主义现代画。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

看起来像是铺地砖工人出身的画家创造的作品,因此简称为地砖画。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
第二种可能的风格是:印象派风景画。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

这个看上去很正常向啊,就叫风景画好了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
第三种可能的风格是:表现派细节组合画。

你们随意感受一下艺术家的世界. . . . . .

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
第三种可能的风格是:表现派细节组合画。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题 非传 统 趣 题讨论

IOI2013 Day1 Artclass

不知道在座各位有没有艺术细菌比较丰富的同学,能感受到这些作品 中蕴含的美感. . . . . . 反正我是没感受到,于是就简称乱码画好了. . . . . .

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
第四种可能的风格是:色块组合画。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

如果说地砖画的作者是铺地砖工人出身的话,本类作品的作者大概是 刷墙工人出身。于是就叫刷墙画吧。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
讨论时间. . . . . .

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

朴素思路:随机返回1~4的一个值,多次提交取最优解。 时间、空间、编程复杂度:极小 期望得分:个位数。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

更靠谱的做法?. . . . . . 观察四种风格的规律。 地砖画:主要由色块组成,色块内颜色十分均一,但色块间颜色 可以差异很大;色块边界十分规整,色块间一般由深色线条分 割。 风景画:有一个基础色调,各个像素点颜色大致差不多,但又不 像地砖画或刷墙画那样整齐划一。 乱码画:杂乱无章,十分混乱。各种颜色的乱线交错在一起。 刷墙画:整幅画主要由三四块大块的颜色块构成,色块内部颜色 比较均一。可能有一些细线条之类的点缀。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

可以发现这四类画作中,乱码画显得十分突兀。其他画作要么有一个 整体的“大致色调”,要么至少在局部有一个“大致色调”,其中的颜色 都比较接近。而乱码画中充满了乱码一样的东西。 但是,怎样用计算机程序来进行判断呢?计算机程序没有像人类一样 的视觉,显然是无法直接“看”出来的。 很容易想到,对于图片中每个点,计算它与它周围的一些点颜色的差 距,然后利用平均数/方差等数据进行判定。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

怎么计算两个点色差? 最简单的方法: 直接把RGB值视为三维坐标,算欧几里德距离或曼哈顿距离之类的。 当然也有一些更高端的方法: 有理论认为RGB色彩空间的表示方式与人眼感受色彩是有一定差距 的,因此提出了一些新的表示方法。 例如HSV色彩空间、HSL色彩空间、LAB色彩空间等一听起来就很高端 的东西。 据说转换成HSV色彩空间的表示法后再算欧几里德距离/曼哈顿距离效 果更佳。 但对这题来说,直接用RGB表示法算色差就足够了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
我们不妨试验一下我们的策略对题目自带图片的效果。 效果如下:(考虑每个像素为中心7*7的点,欧几里德距离的平方作为 差距估价,第一列为每个点与周围点RGB差值的平均值,第二列为标 准差的平均值,四张图依次对应地砖画、风景画、乱码画和刷墙画)

可以发现,刷墙画的两个参数明显地小于其他三类画(均远小 于1000),因此可以直接用这个标准来判断刷墙画。 但是其他三类画并没有明显拉开差距(虽然乱码画的参数值明显比较 高,但乱码画中参数值较低的与地砖画、风景画中参数值较高的并没 有明显拉开差距)。因此我们需要寻找更合适的判定标准。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

进一步观察可以发现: 风景画中每个像素点与周围像素点RGB值普遍有差距但差距都不 大 地砖画中每个像素点要么与周围像素点RGB差距很小(色块内 部),要么与周围像素点RGB差距很大(边界) 乱码画中每个像素点与周围像素点RGB差距普遍比较大

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
新策略:统计每个点到周围点的RGB差距值中,大于某个值的差距所 占的比例。 试验一下效果(各列分别表示RGB差距 在1000、2000、3000、4000、5000以上的像素点对占的比率):

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass
我们发现,这三类图片在这几个特征值的大小上并没有完全拉开差 距. . . . . . 但是我们可以发现,地砖画和乱码画的5个参数值都比较接近,而风景 画中,5个参数值相对大小变化的很明显,第一个参数值都达到了最后 一个参数值的好几倍。这个是因为风景画中颜色渐变相对平滑,所以 颜色差距在1000~2000,2000~3000,3000~4000,4000~5000 的像 素点对都有不少。 而地砖画和乱码画中,颜色要么几乎一样(地砖画色块内、乱码画线 条内),要么差距极大(地砖画地砖边界处,乱码画各个线条之 间),导致大部分差距较大的点对差距都在5000以上,所以从第1个参 数到第5个参数变化比较小。 因此我们得到了风景画的判定:如果5个参数值在合理的范围内,且第 一个参数达到了第5个参数的若干倍(我考场上写的是2倍),那么就 判定为风景画。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Artclass

最后只剩下地砖画和乱码画的判定了。我们发现,在排除了风景画 后,这5个参数值差距已经拉的非常明显了,直接设一个标准进行判定 即可。 我考场上基本按这个思路写的判定,第一次提交就做到了98%的准确 率(120幅画中只错了2幅)。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
给定一张图片(边长不超过2000像素),白色背景上有一些黑色的圆 和正方形(可能有旋转),但加入了噪音(每个点有20%概率被翻转 成相反的颜色)。 问图片中有多少个圆多少个正方形。保证正方形的边长/圆的直径不小 于15像素,任意两个图形间隔不小于10像素,图形总数不超过50个, 且图片用肉眼可识别。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem

假如没有噪点? Flood?ll每个连通块 每个连通块内,试图找到距离最远的两个点,它们构成了正方形的对 角线或圆形的直径 进而估测出正方形/圆形的面积,与实际面积相比较,确定是正方形还 是圆形 (距离最远的两个点不太好找?) (实际只要找距离重心最远的那个点就行了. . . . . . )

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
有噪点怎么办? 无视噪点直接Flood?ll,最后面积除以0.8? 确实,仅仅20%的随机颜色翻转几乎不可能把一个图形分成两块,或 把两个分离的图形连起来(注意直径/对角线至少15像素,且图形间隔 至少10像素)

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
但是这么做实际效果很糟糕,难以正确识别比较小的图形(事实上连 样例都过不了)。 考虑如何降低噪声对结果的干扰。 最简单的策略:直接Flood?ll,如果连通块大小小于某个阈值,直接视 为噪声,反色。 实战效果:能够去除大部分的噪声,但有效图形和背景的边缘部分依 然很糟糕。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
更好的方法?使用一个听起来很高大上的技术:高斯模糊(Guassian Blur) 回忆一下,大家刚看到这幅充满噪声的图时,是否本能地眯着眼睛去 数圆和方块的个数,以尽量减少烦人的噪音干扰? 人的眼睛相当于一个透镜,眯着眼睛实际相当于刻意避免完美对焦, 让原图中每个点实际投影到视网膜的一片区域而不是一个点上。 高斯模糊实际就是模仿了这个过程。把每个点的色值变成其周围的点 的色值按某种方式加 权平 均得到的结果。大家可以想象一下,这样一 来,因为噪音是随机的,背景里的每个点周围噪点数量都差不多,从 而都会变成颜色差不多的点;前景里的噪点同理。而真正的前景不会 受到太大影响。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
具体方法是这样的:首先选择一个值σ ,表示对每个点考虑其周围行差 距和列差距不超过σ 的像素点。 然后设定一个(2σ + 1) ? (2σ + 1)的权值矩阵G ,表示各个像素点对中心 点贡献的权重,矩阵里所有权重的和应当是1(以防止图片颜色越来越 深或越来越浅)。

例如左图就是一个可行的矩阵(σ = 2) 最后像上文所说的,对每个点算一下带权平均数就可以了: ai ,j = ai +x ,j +y ? Gx ,y
|x |,|y |<=σ

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
权值矩阵里填的内容? 方法一:随手敲一个,看着舒服就行了,效果不好就再敲一个。 1 方法二:每个元素都取 (2σ+1) 2 (相当于不给权重,直接进行平均) 方法三:可以想象靠近中心点的点权重应该比距离较远的点权重更大 2 v2 ? u +2 1 2σ 一些。不妨用正态分布公式来建立矩阵G (u , v ) = 2πσ 2e

上图是运用正态分布公式建立出的权值矩阵直观的样子。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
权值矩阵的大小? σ 太小,去噪效果不佳,给判定算法带来麻烦。 σ 太大,对图片边缘损坏严重,给判定算法带来麻烦。 通过试验和实际情况选择合适的σ 值。

上图分别是σ = 0, 1, 2, 3, 5, 10,以正态分布公式建立矩阵进行高斯模糊 的效果。可以发现取σ = 1是效果最好的。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

Codeforces 178E The Beaver’s Problem
降低噪声后,再使用之前的算法(对每个连通块找到距离最远的两个 点作为对角线/直径,估测面积,与实际面积比较)来判,就可以过 掉Codeforces上的数据了。但这个算法仍然过不掉tsinsen版本的变态数 据(即使加上一些随机化乱搞和调参数也只能得到95分左右)。 更优秀的判定方法? 考虑把每个图形的边界求出来(对每一列,记录下最高和最低的黑色 像素),然后计算重心到边界各点的距离。 如果是圆,距离应该都差不多;如果是方块,距离应该有较大的差 异。利用最大最小值的差/方差等进行判定 因为考虑了更多的信息,判定更准一些。 其他的一些想法? 对每个连通块求一个凸包,可以想象如果是正方形,凸包上的点应该 很稀少;如果是圆形,凸包上的点应该很多。 通过实践才能得知各个算法的优劣。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语

有一张图片,深色背景上面写了一行浅色字,字体字号一样,没有重 叠没有扭曲,不超过3个字符,且字符只可能是阿拉伯数字 或A,D,E,L,X. 现在要求你识别图片中写了什么。 文字可能有轻微旋转,也可能有少量噪音。

例如,上图分别为03、038、A、E。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语

与上一题一样,我们首先应该试图把文字从背景里提取出来,然后再 考虑如何识别它是什么字母。 如何提取? 背景比较黑,前景比较亮. . . . . . 设一个阈值,灰度小于它的设为黑,大 于它的设为白。 怎么比较科学地取这个阈值呢?直接猜一个显然是不靠谱的. . . . . .

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语
再引入一个听起来很高大上的东西:OTSU方法。 思想:背景和前景之间的颜色差距比较大,因此应该选一个阈值k 把灰 度分成两类,使得这两类的类间方差尽可能大。因为如果有前景被错 误的归类到背景中,或背景被错误的归类到前景中,都会导致类间方 差变小。 数学化的表达:设ω1 为第一类(前景)的元素个数,?1 为第一类元素 的平均灰度;设ω2 为第二类(背景)的元素个数,?2 为第二类元素的 平均灰度;?T 为全体元素的平均灰度。那么我们应当最大化: ω1 ? (?1 ? ?T )2 + ω2 ? (?2 ? ?T )2 实现应该很简单吧,预先排序后扫一遍就可以了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语
OTSU二值化处理的效果:

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语

然后我们试图把这些字符分离开来,以进行识别。 如何分离? 用一个土办法就行了:统计一下每列有多少个像素是白点,把连续的 有白点(或白点比较多)的列视为一个字母。 因为字符没有重叠或粘连,这么做的效果已经足够了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语
如何识别字符? 最简单的想法:对每个字符写一个判定。 比如说我们考虑如何识别字符“L”吧。首先我们大概可以在左下角的地 方枚举一下,确定那个拐点的位置。 嗯嗯,然后我们往上面和右边扫,看看能不能找出“L”的横线和竖线。 嗯,从图片里识别出一条线,有点难度的样子。不过大概判定写详细 一些还是可以的。 然后把识别出的部分删掉吧。看看删掉后白点是不是已经基本没了, 如果答案是肯定的,那就应该是L了。 嗯嗯,然后我们来看下怎么识别字符“2”吧。我们大概得先想办法识别 出顶上那条弧线。 这个好像有点难度的样子. . . . . . 试试看枚举圆心?嗯,然后. . . . . .

什么?考试已经结束了?
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语

为每个字符都写一个判定方法显然是不可行的. . . . . . 不仅时间上不可行,即使真的写出来了,恐怕效果也会很糟糕。几个 噪点、一点轻微的旋转都很可能会给这些判定算法造成巨大的麻烦。 回想一下我们怎么解决我们最初讲的Artclass这道题目的。我们显然没 有教电脑去感受艺术,只是让电脑分析了作品的几个特征值,并以此 判定。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

HNOI2007 所罗门的咒语
注意到字符只有0123456789ADELX这几个。这些字符长得都不太像, 如果能提取出几个合适的特征值就能相对靠谱地识别出来了。 我们不妨考虑切成9块,统计“上层、下层、左侧、右侧、中间的白点 所占的比例”这5个值作为特征值。

预先处理出0123456789ADELX这些字符的特征值,选择最接近的一个 作为答案。 通过适当地对着数据调参数,可以过掉本题。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西
在上一题中,我们已经实现了一个简陋的OCR(图片文字识别),虽 然它只能不太靠谱地识别出几个简单的字符。 下面我们来挑战一下更困难也更有趣的任务:识别网站的验证码。 首先我尝试了识别中国国航网站的验证码:

基本信息:图片大小为80像素*240像素,验证码由大写字母和阿拉伯 数字组成,但没有I和1,O和0等过于容易混淆的字符。如图所见,验 证码的形式是网格上“浮起”了4个字母,网格和字母有小幅旋转,但字 母没有重叠,且字体、字号固定。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西

首先,与之前一样,我们应该去除噪音,提取出真正的文字部分。 那张网格肯定很碍眼,我们应该想办法把它去掉。 观察若干验证码的图案后,可以发现,所有网眼的大小都是4或 者3(因为错位)。 因此,如果一个白色联通块的大小既不是3也不是4,那么说明它很可 能是验证码文字的一部分,否则就很可能只是网眼。 还可以发现,大小小于3的黑色四联通块、大小为2*2的黑色方块也很 可能是文字的一部分,其余的很可能只是网格线。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西

我们只保留这些可能是文字的部分,把其余部分全删光,然后删除图 片中残余的过于稀疏的黑点(我选择的是7*7矩形中不超过4个黑点就 删掉,11*11矩形中不超过10个黑点就删掉,当然这也是根据实际试验 结果得到的方案),进一步降低噪音。 这时候图片已经非常可看了:

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西

然后我们需要把字符分割开来。这道题中字符分割比上一题还要简 单:只要等分成4块就行了。 接下来就是识别了。直接用上一题粗制滥造的画九宫格法进行识别肯 定是不行的,可以想象这种方法在分辨5和S等比较接近的字符时会有 多无力。 我用的识别方法是这样的:因为我们已经能分割出字母了,直接 找100个字母人工进行识别,作为样本。 然后对每个要判定的字母,找到样本中最接近的字母作为答案。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西
怎么判定最接近的字母? 字母有旋转,位置也不一定相同,我们需要找一种比较优的匹配方 案。 我们观察到,字符大小都是相同的。因此,很容易想到,找到每个字 符的重心,在匹配两个字符时,最优的匹配应该让重心重合。 然后,我们可以枚举一个旋转角度。这样,我们就只剩下确定两个字 符的相异程度这个问题了。 很容易想到的估价是,对于两个字符中所有有色像素点,找到另外一 个字符中与其最接近的像素点,以其距离作为估价。得到了一组距离 后,用它们的和/平均数/标准差等得到最终估价。 经过尝试,可以发现用“它们的和”作为估价是一个比较好的选择。并 且,可以发现如果有点根本不能在近距离匹配上,那么这个字母不太 可能是答案。为了突出这一点,我设定以所有距离的2.5次方后的和为 估价。这样即使很小的不匹配也能造成比较大的答案差距。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西
上述算法已经能识别出绝大多数字符了,但仍然偶尔会错,经过测试 可以发现错误主要集中在对“5”和“6”,“8”和“9”等相近字符的识别 上。

我当时尝试了很多方法,但都效果不佳。后来尝试了一个很好玩的方 法:在原图中,因为是从网格上“凸起”了一些字符,这些字符是有“阴 阳面”的!也就是说,字符凸起的侧面有面向我们的,也有背对我们 的。我们可以尝试利用这个信息,在匹配时考虑只允许阴面匹配阴 面,阳面匹配阳面。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西

可以想象,字符背对我们的侧面从我们的视角看,应该是一团阴影。 进一步观察发现,大小2*2的黑色方块很可能是文字的“阴影”造成的, 我们把这些方块标记为红色。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

一个有趣的东西
加上阴阳面的设定后,在匹配寻找最近点时,应该更优先找同色点。 也就是,异色的点虽然也可以作为答案,但要承受一个额外的代价, 我设定的是距离会额外乘2.5。

加上这个设定后,程序便可以无压力分辨出5和6、8和9之类的相似字 符了。 还可以加一些优化,比如在快速找最近点时可以用k-d树加速等,或者 可以考虑对准重心后,再按照比如“从重心出发包含最多黑点的射 线”等方式对齐,以省掉枚举旋转角的时间等等。 最后可以做到98%以上的识别正确率。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

更大的挑战?

前段时间我又尝试了识别12306的验证码,示例图片如下:

基本特点:图片大小只有26像素*78像素,字符集包括大小写字母和阿 拉伯数字。字母粘连严重,有旋转,有缩放。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

更大的挑战?
这个问题我也没有想到特别好的解决方法。下面是我尝试过的一些思 路: 1. 第一个字符左半部分绝大多数情况都是“干净”的,直接用上道题的 方法识别第一个字符的左半部分就能读出第一个字符。 2. 第二个字符与第三个字符粘连一般不严重,使用一些启发式的方法 (比如按某种方式设权值找一条从顶部到底部的最短路等)可以将它 们大致分离开。如果分离成功可以基本正确读出第三个字符。 但因为第二个字符几乎总是与第一个字符严重粘连,即使能读出并移 除第一个字符,也往往会破坏第二个字符的很多特征。加上图片特别 小,读第二个字符错误率很高。第四个字符情况也差不多。 最后只做到了大约10%的准确率,大部分都是识别出了粘连不严重的 情况。与新闻中说的直接用现成OCR软件破解正确率差不多。如果同 学们有更好的想法欢迎与我交流。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

网站应该怎么做?
思考:为了增加验证码的强度,可以采取什么措施? 12306曾经采取过动图验证码的措施,但我个人认为这个措施反而降低 了强度:在动态验证码中每个字符是不同颜色显示的,给程序分离字 符带来了巨大的方便。同时,动图对程序不但没有任何害处,反而相 当于给程序一次提供了很多幅不同角度拍的图片进行分析,恐怕反而 能增加程序的识别率。倒是真正老老实实用眼睛的用户面对眼花缭乱 的动态验证码不知所措了。 还有一些网站使用汉字作验证码,比如用一到九的繁体字作为验证 码。这样看似难识别了,但如果总共就几个汉字的话,只要识别出任 意一小部分属于哪个字就可以确定这个字了(以前看过一篇破解天涯 的繁体数字验证码就用的这个方法)。还有一些网站(比如百度贴 吧)直接找四个汉字让用户输,但这样往往很影响用户体验,弄到最 后还是妥协成提供几个选项让用户去选答案,但这样又为识别提供了 方便。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

网站应该怎么做?

我设想过几条策略来增强验证码的强度: 1. 字符使用相同的颜色,不让程序能从颜色上分离字符。 2. 在人眼可识别的前提下,尽可能重叠、粘连字符,增加分离字符的 难度。 3. 字符要扭曲、缩放、旋转、用多种不同字体,最好用罕见字体、空 心实心字体混用等,给样本搜集、模式匹配尽可能制造麻烦。 4. 如有必要还可以加入噪音、干扰线等,并尽可能缩小图片。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

我们应该怎么做?

有很多更高端的方法可以更有效的识别验证码,如图形上下文、神经 网络、深度学习等听起来就很神的算法。 同时,我们作为攻击方,可以充分发挥人类智慧,发现和利用设计者 的疏忽。 图像识别领域也是计算机科学近年研究的热点,不断有新的识别方法 和应对方法出现,这是一场没有止境的攻防战。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language
你需要编写一个交互式的程序,该程序需要猜测10000段来自维基百科 上的摘录(每段摘录100字符)的语言类别。 每次系统会给你一段摘录,你的程序要猜测这段摘录的语言,然后系 统会告诉你正确的答案 以方便你的程序从中学习。 总共有56种可能的语言,它们是IOI2010的所有参赛国家的母语。每个 摘录所用的语言随机选自这56种语言之一,而摘录内容来自维基百科 的随机文章的第一段。所有字符都会被编码为1至65535之间的整数, 且不对应任何标准编码。 得分公式: 低于0.3的准确度没有分 达到0.3的准确度就可以获得30分 接下来你的得分会随准确度线性增加,达到0.91的准确度就可以 获得100分

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

题目还给出了一种示例做法,这种被称为Rocchio法的算法可以达到大 约0.4的准确率。 这种算法思路是这样:对每段摘录E ,选择与到目前为止遇到的语言中 最相似的作为答案。摘录E 与语言L的“相似度”被定义为E 中没有在任 何已知语言为L的摘录中出现的字符个数。 直接实现这个算法,发现对题目中的数据实际准确率达到 了53%,56分就这么到手了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

更好的做法? 官方做法是一个看起来有点不可思议的算法:改进一下Rocchio算法, 找一个合适的k 值,把连续的k 个字符当作k 元组处理。 然后摘录E 与语言L的相似度定义改为:E 中没有在任何已知语言为L的 摘录中出现的k 元组的个数。 这个算法我最初也没有理解为什么会有很好的效果,直到后来偶然看 到了一篇与自然语言处理相关的科普文后才知道这个算法是n-gram算 法的一个变形。在这里介绍一些相关的比较有意思的东西。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

首先我们需要了解一些概率论基础知识。 我们用P (A)表示事件A发生的概率。 P (A|B )表示,在事件B 发生的前提下,事件A发生的概率。 P (AB )或P (A, B )或P (A ∩ B )都是等效的写法,均表示既发生事 件A也发生事件B 的概率。 P (AB ) = P (A) ? P (B |A) P (A|B ) = P (AB )/P (B )

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

一个重要的公式:贝叶斯(Bayes)公式。 P (A|B ) =
P (B |A)?P (A) P (B )

举个很简单的例子以帮助理解这个公式: 我们知道女生中参加OI竞赛的比例是远低于男生的。假设某学校 中60%是男生40%是女生,其中男生有40%是OIer,女生 有20%是OIer。有一天你偶然看见学校机房里有一个OIer正在对着题目 苦思冥想(这里假设每个人出现在机房是等概率的),那么这 名OIer是女生的概率是多少呢?

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

我们实际要求的是P (Girl |OIer ),
GirlOIer ) 也就是 P ( P (OIer ) , ?P (OIer |Girl ) 也就是 P (Girl ) , P (OIer )

也就是有P (Girl |OIer ) =

P (OIer |Girl )?P (Girl ) , P (OIer )

把Girl 和OIer 分别换成A和B ,这就是贝叶斯公式。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

利用贝叶斯公式我们可以简化很多问题。 比如,我们敲键盘时候有时会手抖敲错单词,这时候有些文本编辑器 会提示你单词拼错了,并给出可能的正确拼法。 这是怎么做到的呢? 直接找词典里每个单词,看看哪个和当前单词最接近? 不够靠谱,比如用户手抽打了collwge这个词,用户更可能想输入的 是college(大学)还是collage(把. . . . . . 制作成拼贴画)呢?字母w和 字母a、e在键盘上都靠得很近,但college这个词很明显比collage常用很 多,用户打出collwge时十次里可能有九次心里想的是college只有一次 是collage,显然最佳的更正建议是college而不是collage.

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language
记”敲出来的单词是x ”这个事件为Ax , ”需要敲出单词y ”这个事件为By , 概率P (By |Ax )就是敲出的单词是x , 而想敲的单词是y 的概率. 那么文本编辑器要做的是, 在已知用户敲出了x , 找一个单词y , 使得用 户想敲的是y 的概率最大. 翻译成概率语言, 即找一个y , 使 得P (By |Ax )最大。 运用一次贝叶斯公式,我们能得到 P (Ax |By )?P (By ) P (By |Ax ) = P (Ax ) P (Ax )项是个常数,可以不考虑. 那么我们实际要优化的 是P (Ax |By ) ? P (By )的大小, 用大白话说, 就是我使用单词y 的概率乘上 想要输入单词y 却把单词y 手抖打成单词x 的概率。这两部分显然都不难 求。 和刚才那个直接找字典里最接近的单词的方法不同之处?刚才的做法 求的实际是P (Ax |By ),而不是我们想求的P (By |Ax )。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language
再看一个很常见的例子:垃圾邮件过滤。 大多数邮箱系统都提供了反垃圾邮件的功能。如果我们要实现一个简 单的判断垃圾邮件的系统应该怎么做呢? 我们可以统计出一个邮件是否是垃圾邮件的先验概率,不妨设 为P (好)和P (坏)。(也就是所有邮件中有多大比例是垃圾邮件) 不妨设邮件A由n个单词组成。我们把一封邮件包含A的第i 个单词称为 事件Ti 。运用贝叶斯公式,可以计算出此时的后验概率:一封包含了 邮件A的每个单词的邮件是垃圾邮件的概率为

P (坏|T1 , T2 , . . . , Tn ) P (坏) ? P (T1 , T2 , . . . , Tn |坏) = P (T1 , T2 , . . . , Tn ) P (坏) ? P (T1 , T2 , . . . , Tn |坏) = P (好) ? P (T1 , T2 , . . . , Tn |好) + P (坏) ? P (T1 , T2 , . . . , Tn |坏) P (坏) ? P (T1 |坏) ? P (T2 |坏, T1 ) ? P (T3 |坏 = P (好) ? P (T1 |好) ? P (T2 |好, T1 ) ? P (T3 |好, T1 , T 2) ? · · · + P (坏) ? P (T1
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

也就是P (坏|T1 , T2 , . . . , Tn ) =

P (坏)?P (T1 |坏)?P (T2 |坏,T1 )?P (T3 |坏,T1 ,T2 )?... P (好)?P (T1 |好)?P (T2 |好,T1 )?P (T3 |好,T1 ,T 2)?···+P (坏)?P (T1 |坏)?P (T2 |坏,T1 )?P (T3 |坏,T1 ,T 2)?...

然后我们就会发现,这个式子一切都好,惟一的问题就是没法算。 问题:假设邮件只有20个单词,想靠谱地算 出P (T20 |好, T1 , T2 , . . . , T19 )的值,需要多大的语料库? 一封信的前19个单词有多少种不同的可能性? 想想都能吓死人啊,恐怕把全世界的硬盘都拿来也装不下吧. . . . . . 更别 提找这么多的邮件了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

那怎么办? 于是产生了一个被逼无奈的办法:一个单词大概只与前面若干个单词 关系比较紧密吧,与更靠前的其实关系不算特别大。 于是n-gram算法就产生了:我们干脆假设每个单词只受其前面连续k 个 单词影响,不再受更靠前的单词影响了。 通过取一个适当的k 值,就可以有效避免数据稀疏性的问题了。而且实 践表明这个算法效果很好。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

为什么武断地认为每个单词只与前k 个单词有关不会玩脱呢?要知道, 很多时候一句话可能与老早以前的某句话都有逻辑关系。 一个解释是,很早以前的单词确实可能会对当前单词产生影响,但这 个影响太小了,而且很可能正面影响和负面影响都差不多,很可能会 基本抵消掉,因此对最终答案没有什么影响。 而且从现实角度看,有很多词语是“专属”于广告的。正常人看到“大减 价”“优惠券”“物美价廉”“快来抢购”等词语时候,不管前面说了啥,就 已经能基本确定是广告了。至于到底是“吮指原味鸡优惠券”还是“黄金 脆皮鸡优惠券”并不重要~ :) 所以以短词组为单位识别还是相对靠谱 的。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

怎么选取k 的值? k 值太小,区分度不够高,统计“快来抢购”这个词组显然比统 计“快”“来”“抢”“购”这四个单字分别出现的次数更能确定广告。 k 值太大,数据稀疏性问题又来了。 根据实际情况选择合适的k 值。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

回到原题,我们要识别一段摘要是哪个语言。 这个和之前讲的识别一段话是否是广告本质是一个问题啊,相当于识 别一段话有多大程度符合某种语言的特征。 这时候大家应该很容易理解题解中的“把k 个连续元素组成k 元组”了 吧。也可以发现,题目中给出的那个Rocchio方法就是k = 1的n-gram, 相当于假设所有字符都是独立事件。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language

适当地选取k 值进行试验,结果如下: k值 1 2 3 4 5 6 7 8 准确率 53% 74% 87% 91% 87% 84% 79% 74%

可以发现k = 4时效果最好,正确率达到了91%,可以得到100分。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Language
下图是k = 1, 2, 3, 4, 5时,准确率与询问个数的变化曲线。

我也尝试过随着询问个数的增加,逐步加大k 等优化,但发现优化效果 极为有限。 能否做到更高的准确率?欢迎有兴趣的同学与我讨论。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Save It

有一个n点m边的边权均为1的无向图和一个值H 。 你被要求写两个程序,第一个程序可以获知这个图的信息和H 的值, 并发送一串二进制串给第二个程序。 第二个程序只能获知这串二进制串,要求输出结点1~H 与结点1~n两 两之间的最短路。 ?1) , H ≤ 36 n ≤ 1000, m ≤ n?(n 2 得分规则: 如果你发送的二进制串长度不超过16000000,你可以得到25分; 如果你发送的二进制串长度不超过360000,你可以得到50分; 如果你发送的二进制串长度不超过80000,你可以得到75分; 如果你发送的二进制串长度不超过70000,你可以得到100分;

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Save It

朴素算法: 由于所有边权都是1,最短路长度很明显不会超过n。直接暴力BFS求 出最短路,总共最多有n ? H = 36000个数,每个数不超过1000,直接 用10位二进制位表示,发送过去,正好360000位。 这样就50分了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2010 Save It
特殊性质?边权都是1。如何利用? 注意到,如果存在一条边权为1的边(u , v ),那么对于任意点i ,必然 有|dis (i , u ) ? dis (i , v )| ≤ 1。 建立从1开始的最短路径树,树上每个结点记录该结点到1~H 的各个 最短路径长度。 考虑父结点u 与孩子结点v 上的H 个值的关系。由上述结论,对任 意i ,dis (u , i )与dis (v , i )必定只相差-1,0或1。因此我们只要记录这 个-1,0,1序列,就能从父结点u 的答案推出孩子结点v 的答案。 把这棵最短路径树传递给程序2就可以了。 需要传递的信息:每个结点的父结点以还原树结构,每条树边的 的-1,0,1序列以还原答案。 每个树结点需要的长度:log2 336 + 10 = 68位。 总长度:68000位,可以得到满分。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

你需要写两个程序,第一个程度读入n个0~255之间的整数,输出不超 过L个0~255之间的整数。 然后第一个程序的输出会被随机洗牌打乱次序后提供给第二个程序。 第二个程序必须还原出第一个程序所读入的n个数(n个数的次序也要 一样)。 得分规则: 任务一:限制n ≤ 16, L ≤ 10n 任务二:限制n ≤ 32, L ≤ 10n 任务三:限制n ≤ 64, L ≤ 5n

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

想法一: 被打乱顺序了怎么办? 想办法保存额外信息,记录每个数是序列里的第几个。 设用x 位记录自己是序列里的第几个,那么剩下的8 ? x 位可以保存有 效信息。 那么最多一共能传送2x ? (8 ? x )位信息。 取x = 6时能传送的位数最多。此时能传送128个二进制位信息,也就 是16字节,L的长度是4n,可以满足任务一的要求。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

前6位作为位置码,依次存储0~63。后两位存储真正的有效信息。 解码时,先按前6位进行排序,然后把后两位依次拼起来,即可次序不 变地还原出信息。最多能传递26 ? 2 = 128位二进制位。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

怎么解决任务2? 考虑把要求的序列的二进制形式直接写下来(第二个数直接接在第一 个数后面这样)。 总共长度最多32*8=256位。 如果第i 位是1,我们就把第i 位输出出来。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

任务3? 上一个做法的实质是,用一个长度为256的2进制整数与原序列(一个 长度为32的256进制整数)一一对应起来。 于是. . . . . . 为什么我们必须使用二进制整数?进制数并不是限制。 真正的限制是“代价等于所有数位的和”。因此我们应该按照“所有数位 的和”从小到大为次序进行编码。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

k 利用组合数学,很容易发现数位和为k 的编码方案数共有C255+ k 种。 64 而64个0~255的整数共有256 种可能性。

至少要数位和达到多少,才能让编码数量达到25664 呢? 也就是找到最小的k 使得
k i =0 i 64 C255+ i ≥ 256

写个程序算一下,发现答案是261。因此最多只要用不超过261个数, 就能传递64个0~255以内的整数。 效率? L n =
261 64

≈ 4.08,足以满足任务3的要求。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2011 Parrot

但上述方法的代码太难写了,为了进行编码,不得不写高精度等麻烦 东西. . . . . . 更简单的方法? 使用更浪费但更好写的编码方案。 16个数位一组,每组使用不超过20个数。总方案数约7.3 ? 109 种,足以 编码32个二进制位,也就是4字节。 效率正好是 20 4 = 5,恰好满足任务3要求。 这样就不用高精度了,直接用动态规划求编码序号即可。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:程序猜数
曾经,有一个30位(二进制)的整数摆在我的面前我没有珍惜,直到 我失去时才后悔莫及,如果上天再给我一次机会,我一定牢牢的记住 这个整数。 没办法,已经失去了,只好再问回来了。 你的程序可以调用一个系统提供的函数isX(x ),这个函数会返回x 与这 个数有多少二进制位不同。 你需要在不超过5次调用内确定这个整数。 特殊附加条件:本题有20组数据,可以多次提交,每次提交都可以看 到各个测试点的评测结果。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:程序猜数

正常的做法可能在5次操作内确定一个整数吗? 每次调用的返回值都在0~30之间,共31种可能。 因此,5次调用最多只有315 种不同结果,也就最多只能分辨出315 个不 同整数,远远达不到题目从230 种可能性中找到正确的整数的要求。 因此正常做法理论上就不可能解决此题。 怎么办? 利用特殊条件,我们每次提交都可以看到各个测试点的评测结果。 我们发现,第一次询问isX(0),第二次询问isX(2k ),我们就能确定当前 要猜的数的第k 位是0还是1。 然后?如果第k 位是0,就让程序直接退出,得到Wrong Answer; 如果第k 位是1,就让程序进入死循环,得到Time Limit Exceeded; 这样就把第k 位的结果通过提交结果传递到了我们的手上。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:程序猜数

每次提交都能确定各个数据答案的某一位是0还是1; 只要30次提交就能取得全部数据的答案; 得到全部数据的答案后,只要根据这些答案人工找一个分辨规则就行 了。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:一道防AK好题
请大家无视搞笑的题目名字. . . . . . 这题其实是我出的某套NOIP模拟赛 的第一题. . . . . . 有一个长度为n ≤ 500000的的数列,第i 个数为xi 。 有很多(不超过500000组)询问,给定的a, b , c ≤ 1018 ,要找到一 个i ,使得a ? (i + 1) ? xi2 + (b + 1) ? i ? xi + (c + i ) = 0成立。 如果有多个i 满足,要求返回最小的那个i 。 输入数据中a = b = c = 0标志着询问的结束。 为了加大难度,出题人对数据进行加密以防止离线算法的出现。假设 你在输入文件中读到的三个数为a0 , b0 , c0 ,那么真正要询问 的a = a0 + lastans , b = b0 + lastans , c = c0 + lastans 。 lastans 的值是你对前一个询问的回答。如果这是第一个询问,那 么lastans = 0。所有的询问都将会按上述方式进行加密,包括标志着 询问的结束的那个询问也是这样。(也就是最后一个询问是解密后才 得到a = b = c = 0的)

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:一道防AK好题
话说这道题的平均分似乎是整场比赛三道题中最低的(虽然做法是最 简单的),在赛后这道题也得到了很多同学的好评。

同时这道题的思想似乎还被用到了山东省选的某一道题中又坑了一些 人,作为始作俑者我表示十分抱(xin)歉(w` ei)。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:一道防AK好题

首先我们发现传统的数据结构维护的思路对题目中的式子基本都是无 效的。 实际这题的突破口在于,最后那个标志询问结束的询问也是加密的。 而它解密后一定是a = b = c = 0。 也就是说,a0 + lastans = 0,于是我们可以直接得出倒数第二个询问 (也就是要回答的最后一个询问)的答案是?a0.

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

娱乐向:一道防AK好题

然后有趣的事情就发生了。得到了倒数第二个询问的答案后,我们将 答案和倒数第二个询问的a0 , b0 , c0 带入原题的式子中,可以得出一个关 于倒数第三个询问的答案的一元一次方程。于是可以O (1)直接解出倒 数第三个询问的答案。 如此推下去,就可以O (n)推出全部询问的答案。 看上去是一个复杂的数据结构题,实际考察的却是选手打破思维定势 的能力。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

总结?

嗯,和非传统题有关的就讲到这里吧。 一定要总结一点什么的话? 除去考察一些常见的思路与算法外,主要的考察点的依旧是选手针对 题目特点,充分发挥人类智慧,探索、测试、改进解决方案的能力。 接下来讨论一下IOI2013 Day1的剩下两道题。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Dream

给定一个包含n个结点的森林(n ≤ 105 ),边上有权值。 给定一个值L,你需要增加若干边权均为L的边,使得: 得到的新图是一棵n个结点的树 这棵树的直径尽可能小 问最小可能直径是多少。 n ≤ 105

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Dream

首先我们试图发现一些性质。 1. 如果某个结点是我们新加的某条边的端点,那么我们称这个点为“接 点”。可 以证 明存 在一 个 最 优解 使得 在每 个原 图中 的树 里, 都有 且 仅 有一 个 “接点 ”。 证明:如果有一个最优解使得在某个树中有超过一个“接点”,我们不 妨取其中任意两个,设为A与B 。我们不妨定义dis (T )表示结点T 所在 树中,距离结点T 最远的点的距离。不妨设dis (A) ≤ dis (B ),那么我们 将接到结点B 的边全部改为接到结点A上,可以发现,直径不会增加。 如此往复,直至这棵树中只剩一个接点,此时解没有变差。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Dream

2. 可 以证 明存 在一 个 最 优解 ,使 得对 于原 图中 每个 树, 这个 树的 接 点 T 必 定是 dis ()值最 小 的点 。 证明:如果有一个满足上个性质的最优解中,某个接点T 的值不是所 在树中dis ()最小的结点,不妨设dis ()最小的结点为T ,我们把所有接 到结点T 的边都改为接到节点T 上,可以发现,直径不会增加。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Dream

3. 有了前两条性质,我们现在需要考虑的就仅仅是这些“接点”的连接 方式了。那么最优的连接方式一定是:选择 某一 个 接 点, 其他 所有 接 点都向这个接点直接连边。 我也不会严格写这一步的证明。不过感性理解一下的话,正确性是显 然的。 对严格证明这一步有想法的同学欢迎与我讨论。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Dream
有了上文的分析,算法已经非常显然了。首先我们需要求出原图中每 个树的直径,并求出原图的每个树中dis ()的值最小的结点。 这一步只需对每个结点用树形dp求出其向下最长延伸、次长延伸的长 度,以及向上最长延伸的长度即可O (n)完成。方法十分经典,在此不 再赘述。 我们不妨用D [i ]来表示我们求出的树i 的dis ()的最小值。接下来,我们 考虑枚举那个“其他接点都向它连边”的接点,那么当前方案的答案可 以利用D 数组的最大的三个值O (1)计算出来。 最后还有一个小细节,上文所算的答案仅仅考虑了包含我们新加的边 的路径,因此最后还应该和原图中各个树的直径取max ,才能得到最 终答案。最终复杂度O (n)。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Wombats

有一个R ? C 的网格,其中所有的竖向边只能从上向下单向通行,而横 向边可以双向通行。每条边都有一个初始权值。 要求支持: 修改一条边的权值 查询从网格最上面一行的某一点到最下面一行的某一点的最短路 的长度 R ≤ 5000, C ≤ 200,修改操作不超过500次,查询操作不超 过2 ? 105 次,时间限制20秒。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Wombats

最最朴素的做法? 对每个询问暴力用Dijkstra求最短路。 O (RC log R )每次询问。 稍稍改进一些? 因为竖向边只能从上向下单向通行,这道题具有很明显的阶段性。 直接进行dp,同一行内部的转移可以用BFS通过一些技巧做到O (C )。 可以做到O (RC )每次询问。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Wombats

再改进一些? 因为竖向边都是单向的,这里的最短路是满足区间合并性质的。如果 我们有两个X ? C 的网格中,最上面的行和最下面的行两两之间最短路 的长度,那么我们显然可以在O (C 3 )内合并它们,得到这两个网格拼 起来后的情况。 我们不妨用线段树维护R 这一维,那么复杂度就是O (C 3 ? log R )每次修 改,O (1)每次查询(因为查询只查询整个网格的情况)。 做到这一步可以拿55分或76分(根据实现不同)。我考场上只想到了 这一步,于是只有55分,成为了中国队中唯一没有AC这道题的队员。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Wombats

怎么继续优化? 我们固定上半部分网格的起点,然后考虑拼接处每个点能作为哪些端 点的最优答案。可以发现,以其为最优答案的终点必定是一个区间。 归纳证明: 首先,如果只有一行,结论显然成立。 如果结论对k 行的网格成立,考虑拼上第k + 1行,发现结论依然 成立。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

IOI2013 Day1 Wombats

也就是说,转移是满足单调性的,一个老的决策一旦劣于一个新决 策,那么这个老决策就可以永远地被丢弃了。 因此,只要套用经典的1D/1D动态规划优化方法,用一个单调栈+二分 来维护最优决策即可把合并复杂度优化到O (C 2 ? log C )。 最终复杂度是,预处理O (C 2 ? R ? log C ),修改O (C 2 ? log C ? log R ), 查询O (1),足以通过本题数据。

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

谢谢大家
感谢胡渊鸣、罗雨屏、王康宁、乔明达、贾志鹏、罗翔宇等同学 提供的大量修改建议和帮助 感谢CCF提供了这个交流的平台 感谢父母、学校对我参与OI竞赛的支持 感谢所有帮助、关心我的老师们和同学们 祝大家新年快乐~

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

ZJU3639 Guess A Function
如果看到这道题目,说明我前面准备的题目太少了. . . . . . T T 定义: g (x ) h1 (x ) h2 (x ) f (x ) = x xor (x /2) = x /m1 ? m1 + (x + s1 )%m1 = x /m2 ? m2 + (x + s2 )%m2 = g (h2 (g (h1 (g (x )))))

其中xor是按位异或,/是整除,%是取模。 你只知道m1 , m2 , s1 , s2 都是不超过345678的正整数, 且0.3m1 < s1 < m1 , 0.3m2 < s2 < m2 , 但你不知道这四个常量具体的值。 现在样例给了大约5000组x 的值及对应的f (x )的值,你只需要用任意方 法解出m1 , m2 , s1 , s2 这四个常量的值就行了。 给出的数据中,大约100组数据有x ≤ 1000,其余的x 大致等概率分布 在[0, 232 )间。
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

ZJU3639 Guess A Function

首先发现函数g 是有反函数的。 因此可以把y = g (h2 (g (h1 (g (x )))))最外层和最里层的g 去掉,变 成y = h2 (g (h1 (x )))。 接下来,最自然的想法是枚举h1 ()的参数m1 和s1 ,但这时会发 现m2 和s2 依然有很多可行解,再乘上对5000组数据一一验证的复杂 度,完全无法接受。 换一个想法?考虑一旦确定了m1 ,随着s1 取不同的值,h1 (x )能取到的 值会形成两个(或一个)区间。 但很不幸,在碰到g 函数后,这些形成的区间又被打散了,没法利 用. . . . . .

南京外国语学校

许昊然

IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论

ZJU3639 Guess A Function
突破口在哪里呢? 提供的数据中有100组数据满足x ≤ 1000。 大胆猜想:此时如果m1 不特别小的话,那 么h1 (x ) = x /m1 ? m1 + (x + s1 )%m1 中,前半部分x /m1 ? m1 基本就 是0了,而且如果s1 和m1 不特别接近,后半部分也可以无视取模! 然后g 函数并不会显著改变传进来参数的大小(因为是位运算),因 此g (h1 (x ))大概只有s1 这么大。 于是. . . . . . 如果m2 也比较大的 话,h2 (x ) = x /m2 ? m2 + (x + s2 )%m2 中,前半部分x /m2 ? m2 说不定 也是0. . . . . . 于是我们带着这两个猜测试验一下。这时候,我们发现,枚举了s1 的 值后,s2 的值也就确定了。 而且发现,符合条件的(s1 , s2 )组并不多,大概只有几十组。 我们再对每一组符合条件的(s1 , s2 )枚举m2 ,此时m1 也就可以求出了, 然后逐一验证即可。这样可以在大约3分钟内找到解。 如果我们运气不好,刚才的猜测是错误的呢?留给同学们思考~ :)
南京外国语学校 许昊然 IOI2013 Day1试 题 讨 论及 几 题非 传 统 趣题 讨论


2014年中国真空开关产业竞争格局报告

//www.ibaogao.com/baogao/031213Wc2014.html 报告目录第一章 真空开关相关概述 第一节 开关简述 一、开关的种类与特点分析 二、开关和断路器的关系 三、开关...

2014年中小学幼儿园新教师优秀教学设计评选的通知

教学设计和汇 总表 用打包文件 格式 统一发送到 电子 邮箱: wcjks2014@126.com,教学设计文件名:单位名称+教师姓名+题目, 学校(园)文件包名称:新教师教学设计+...

2014年全国高考英语试题分类汇编:改错题 Word版含解析

2014年全国高考英语试题分类汇编:改错题 Word版含解析_高考_高中教育_教育专区。...The early morning barking have been disturbing us as wc arc often up all...

每天一个linux命令(40):wc命令

每天一个 linux 命令(40):wc 命令 Linux 系统中的 wc(Word Count)命令的...39 log2014.log 0 11-30 08:39 log2015.log 0 11-30 08:39 log2016....

万科形象广告汇编

更多文案设计干货欢迎关注:观止文创(微信号 GZWC2014) 万科企业形象篇广告汇编 精信广告——“珍视生活本质”系列 一、路灯篇 最温馨的灯光 一定在你回家的路上 ...

建筑电气中的WC、CC、FC代表什么意思?

WC-暗敷在墙内 CE-沿天棚顶敷设 CC-暗敷在天棚顶内 SCE-吊顶内敷设 FC-...文档贡献者 文敌霸王龙 贡献于2014-04-29 1/2 相关文档推荐 ...

水电图纸中的WC,WE,CC.CE.FC.FE.等都代表什么

水电图纸中的WC,WE,CC.CE.FC.FE.等都代表什么_建筑/土木_工程科技_专业... 2014年幼儿园教师资格考... 2014教师资格中学教育知...1/2 相关文档推荐...

《状元之路》2014届高考政治(新课标通用版)一轮复习高效作业 知能提升:模块4第4单元综合测试

woowoowc贡献于2014-02-24 0.0分 (0人评价)暂无用户评价 我要评价 贡献者等级:初试锋芒 二级 格式:doc 关键词:暂无专题推荐 2012大纲全国卷高考数学... ...

2014年“问鼎杯”全国大学生信息安全与保密技能大赛预赛试题

2014 年“问鼎杯”全国大学生信息安全与保密技能大赛预赛试题 第 1 题: 某台...s92wC4YPwA/VK8P/sB236d8///+AB8P/v/2 wC98////3f8P/v/236ge+AA...

AWS标准

AWS 标准目录索引标准号/订购号 AWS A1.1-2001 AWS A2.1WC&DC AWS A2.4-1998 AWS A3.0-2001 AWS A4.2M/A4.2-1997 AWS A AWS 标准目录索引标准号/...