以下是我的NOIp 2009 (提高组) 解题报告.

第一题(潜伏者, spy): 略.

第二题(Hankson 的趣味题, son):

Gcd(x,a0)=a1, Gcd(x,b0)=xb0/b1

设f(a,b) 代表b这个质因子在a中有多少个.

对于a0的任意质因子t, 若f(a0,t)=f(a1,t) 则只需保证f(x,t)≥f(a1,t), 否则f(x,t)=f(a1,t)

对于b1的任意质因子t, 若f(b1,t)=f(b0,t) 则只需保证0≤f(x,t)≤f(b1,t), 否则f(x,t)=f(b1,t)

由于x的所有因子都是b1的子集, 所以我们只需对b1的质因子按如上方法逐个检查这个质因子在x里面的取值范围(若为空则说明无解), 并按照乘法原理统计即可.

关于分解质因子: 由于b1不会超过2*10^9, 大于50000的质因子不会超过1个, 所以我们只要打出50000以内的素数表即可, 若最后除剩的b1仍未除尽, 说明此时b1一定是一个大于50000的素数.

第三题(最优贸易, trade):

做法1:

设Low[i]为从1到i当前所有路径中最便宜的价格. Profit[i]为从1到i当前所有路径中最大获利. 初始时Low[1]=P[1], Low[2..n]=infinity, Profit[1..n]=0.

那么我们可以从1开始广搜, 要注意一个点有可能多次被更新.

从i可以更新到j的条件是:

1. 存在有向/无向边(i,j)

2. Low[j]>Low[i] 或 Profit[j]<Profit[i]

做法2:

首先考虑没有环的情况, 此时1,n之间要么无法连通, 要么只存在一些单向的无环路径. 对于每一条路径, 由于不能”回头”, 走到某个点i的极优获利显然是i的费用-路径上此点之前的点的最小费用, 而此路径的最大获利便是取获利最大的点.

但是还有很多数据是有环的, 也就是对于有些点对(a,b), 在a走到b之后, b仍然可以走回到a. 在图论中, 我们把点集V, 其中任意两个点可以互达, 叫做强连通分量.

由于强连通分量中的点可以互相到达, 所以在一个强连通中的最大获利就是强连通中最贵的-最便宜的. 我们把所有强连通分量求出来缩为两个点之后. 1与n之间只存在一些无环路径, 对于这些单向的无环路径我们只需要扫描一遍便可求出最大获利.

强连通缩为两个点的具体做法: 把一个强连通缩为a,b 两个点, 连(a,b)边, a的费用为强连通中最便宜的, b的费用为强连通中最贵的. 把指向强连通中任何一个点的所有边改为指向a, 把强连通中任何一点指向强连通外部的边改为由b指出. 这样构出来的保证与原图等价.

第四题(靶形数独, sudoku): 很直白的搜索, 由于数独是NP-H问题, 所以我们肯定只能用搜索, 那么关键就在于剪枝了, 我们发现, 对于每个格子都有一个取值范围, 这个范围由其横行/纵行/小九宫格中已填的数决定, 那么无疑我们每次搜索选取值范围最小的格子搜是比较优的.

前几天，在2009年全国信息学竞赛冬令营中，CCF 的杜秘书长提出了近期要取消 NOIp （全国信息学竞赛分区联赛）的一等奖保送资格，取而代之的是高考加分。有些人就不高兴了，我在冬令营的寝室里就经常听到众多选手的埋怨。接下来，CCF 的网站被黑了，大概也是这个原因。还有就是 cnBeta 里发的这一篇《论NOIP取消保送与CCF被黑——NOIP选手自白》。

Read more…

我340的分，湖南330的线，说实话今年湖南的线的确有些吓人。不管怎么说，省一应该没有什么问题了。这个两年多的事情总算有个了结了。

这个省一（咳咳，目前国测成绩未出，应该没问题吧），还是来之不易啊，是的，我走了弯路。

发个题解吧：

1.2.水题，AC了。

3.经典动规：F[i,j,k]表示第i行，第一个人在第j列，这一行前面k个没有被第一个人取掉取掉，而第二个人就在第k个上时的最大值。经过一系列未证明的方法，被我AC了。

4.二分图。

这次NOIp，我要感谢石铮同学的不懈支持，让我有了继续的信心，感谢吴骏兄的启发和杨斐瞳兄精心准备的资料和开导，让我重拾对信息的兴趣，不光是信息，还有数学。我还要感谢的，还有一群各地跟我交谈过的支持我的大牛们。

两次普及组，两次提高组，三个省一，我想这不会是我OI生涯的结束。

RP++

测试数据和完整解题报告在此下载： DropBox | Skydrive

正文：

10月28日_G122_cnPhil_的解题报告

先看哈：

选手列表

编号 姓名 总分

02.mt 02.mt 400.00

standard standard 400.00

–测试器上一角，Orz mt大牛。

简单题目

Easy

时间限制：1s

空间限制：128M

【题目背景】

经典题目自有经典算法。

 

【题目描述】

给你一个N*M（N,M<=1000）的01矩形，求一个面积最大的不包含数字1的矩形。

 

【输入数据】

第一行两个数N，M。

接下来N行，每行M个数为0或1。

 

【输出数据】

一个数ans表示最大空矩形的面积。

Sample

Easy.in

2 4

1 0 0 0

0 1 1 0

 

Easy.out

3

Solve:

这道题，我是用类动规方法做的。对于一个点，记录其竖直向上、水平向左两条最大可以达到多长，再根据这个点左边、上面的点的值求出以这个点为右下角的矩形最大能达到多少。mlj的方法：枚举每列，求出每两个1或边界之间的最大可取矩形。（预处理时标记每点最左最右双向可取长度）

SB题

SB

时间限制：1s

空间限制：128M

【题目背景】

题如其名啦……

【题目描述】

给你一棵N（N<=10000）个节点的树，求每个点到其他点的最大距离。

【输入数据】

第一行一个数N。

接下来若干行每行两个数k，t描述一条点k到点t的边（输入数据保证无重复边）。

【输出数据】

N行每行一个数表示每个点到其他点的最大距离。

Sample

SB.in

5

1 2

1 3

1 4

4 5

SB.out

2

3

3

2

3

Solve:

这道题，有个两遍深搜的方法：首先对于每个点，先构造树结构（任选一点作为根），回溯时求出它到底层的最长路和次长路，然后再对于每个点i，枚举这个点到根的每个点j，若这一段ij不在j的最长路上，那么用ij长+j的最长路更新i点值，若这一段ij在j的最长路上，那么用ij长+j的次长路更新i点值。另外还有一个树形动规的方法，貌似很难实现：从底层到根，一层一层来，对于一条边u,v，求出去除其后，以u为根，最长的一条 路径（有边就是路，不管是子是父）就等于u连出的边的目标点的最长路径值，然后对v为根也做一遍。最后，加一个废点指向根，求出经过根的最长路径。这个方法被指有误！不知道是我听错了还是怎么地。哪位大牛能给我讲讲这个树形动规的方法？

判断

Compare

时间限制：1s

空间限制：128M

【题目背景】

这不是道水题！这真的不是道水题！这绝对不是道水题！！！

【题目描述】

给你一个n(n<=1000)个点m(m<=n*（n-1）/2)条边的图和k(k<=100)个程序对这个图做从点1到点n的最短路后得到的的结果，写一个compare判断谁的输出最优。

【输入数据】

第一行三个数n，m，k。

接下来m行，每行三个数a，b，data表示点a到点b有一条长度为data的无向边（任意两点间最多只有一条边）。

接下来k行，每行为一个程序得到的路径方案(保证路径方案的长度不超过2000)。

【输出数据】

如果所有输出均不合法，输出’Wrong‘，否则输出一个保留4位小数的实数，表示k个人得出结果中最小的一条合法路径长度。

Sample

Compare.in

3 3 4

1 2 5.2000

2 3 3.5000

3 2 6.0000

1 2 3 2 3 2 3 2 3 2 3 2 3

1 2 2 3 3 3

1 3

1 3 2 3

Compare.out

8.7000

Solve:

我觉得这道题目内容和上一道题的标题很配。

最优序列

Best

时间限制：1s

空间限制：128M

【题目背景】

背景的意义就是没人看得懂……

题目的意义就是没人做得出……

【题目描述】

给出一个长度为n(n<=1000) 的正整数序列，求一个子序列，使得原序列中任意长度为m 的子串中被选出的元素不超过k(k<=m<=10) 个，并且选出的元素之和最大。

【输入数据】

第一行三个数n,m,k 。

第二行n 个数，表示各元素数值大小。

【输出数据】

一个数，表示最大元素和。

Sample:

Best.in

10 4 2

7 3 4 8 2 6 5 7 4 8

Best.out

36

Solve:

与其说是动规，还不如说是搜索。以一个二进制串表示状态情况，然后考虑第i个取不取时，若第i-m个状态值为0，那么这个i状态值一定为0，否则枚举0,1。冷吧！

呃，今天电脑有点卡。

测试数据和解题报告完整版在这里下载：DropBox, Skydrive

正文：

呵呵，最近很忙啊，大家可以看看我的上一篇文章。 Well, I think the first step of doing anything you wanna do is to believe in yourself, and believe in it, just like “Forrest Gump” shows, no matter how “unwise” you are, there will always be a way to sucess, you’ve just got to believe in it. 有点像新东方的校训啊，“追求卓越，挑战极限，从绝望中寻找希望，人生终将辉煌！”，这个在这段时期也成为了我的座右铭。

至于我为什么要这么“贯彻”新东方 Spirit 。呃，这又是一个励志典故啊，今天先来谈谈我这段时间钻研的 OI 内容。

罗TW同学在周日给我们讲了有关数据结构的应用的专题，主要是讲题，也是为了镇镇我们，我就弄到了PPT，在这里做简述。

PPT（ .PPTX File Under PowerPoint 2007 ）在这里下载。

数据结构在简单的就是线性结构，其中栈又是相当有用的一部分。

栈的主要应用是深搜。这里弄一道只用了栈的性质而实际上是很巧妙的递归的题目：

•有n个栈，标号为1~n，栈大小分别为s[1]~s[n]，全为空栈。

•将数字1，2，3，4，5…依次加入第一个栈

•如果第i个栈满了，将这一个栈的元素依次出栈，加入第i+1个栈，之后将第1~i个栈改为空栈。如果第n个栈满了，求第n个栈第x个元素到第y个元素的和(1<=x<=y<=s[n])，否则再将数字1，2，3，4，5…依次加入第一个栈。

•N<=1000；s[i]<=longint；数组组数≈1000；时限5s

来源：ZJU 2962 Stack by Stack

•给定n(n<=1000000)个区间[ai,bi]，事先按ai由小到大排序。满足0<=ai<bi<=100000000。每个区间表示的范围是ai到bi范围内的连续的整数。

•请你找到一个整数集合Z，使得：
1、|Z|最小。即集合z内的整数个数最小。
2、z∩[ai，bi]>=2。 即z和每个集合至少有2个相交的不同整数。

并查集

•实现：数组记录父亲

•作用：合并集合；

                 判断一个元素是否在集合内；

•核心操作：路径压缩。

•扩展：路径压缩时，记录到根的路径长度。

•应用：食物链

                 银河英雄传说

                 假面舞会

其实一个树可以压缩为一个集合，每个集合都有其代表元，说白了就是一种父亲指向，每个元素的代表元就是其父亲，而代表元为自己的元素无疑就是整棵树的根了。

给道例题：

•有n个罐子，每个罐子配有一把钥匙，有钥匙就能打开罐子。告诉你这n把钥匙分别放在哪个罐子里。

•现在你要打开所有罐子，但是一开始你没有钥匙。于是你可以直接打碎一些罐子，取出里面的钥匙，或者利用之后拿到的钥匙，打开其他罐子。

•请问，最少打破多少罐子，才能拿到所有钥匙。

•数据范围：n<=1000000

第一题：给出一串已经拓扑好了的事件，求最短完成时间。

做滥了的题目啊，直接扫一边就出解，O(n)

 

第二题：给出第二周的歌曲排行榜和每首歌的歌曲排名变化（上升、下降、持平），求前一周的歌曲排行榜的一种可能解。

字符串处理的题目；

首先，我们把上升了的歌看作要把它往下移，而下降了的歌呢就看作要把它往上移，再把所有的持平歌去掉。

那么，现在的排行榜的首位肯定是下，而末位肯定是上了。

现在，找所有下一位是上的下节点。从这个下节点往上延伸到所有连着的下节点，而从这个上节点往下延伸到所有连着的上节点，把这两个模块互换即可。

第三题：你向银行贷款，告诉你你的贷款额、每月还款额和还款月数。求每个月的月利率（每个月银行先算利再让你还钱）

初以为这道题目十分简单，发现不然，这个题目列出来是个高次方程。其实是可以用log函数来解，但是对于有未知数的log函数，Pascal语言显得十分麻烦（几乎不可能实现）。所以，我在考试的时候使用了枚举的方法，得了60%的点。

但是我竟然忘记了世上有二分这样的好方法，其实，以你的总还款额/贷款额的利率（这个是绝对不可能达到的）为上界，下界为0，来二分求解，效果很好。但是虽然二分时间不超，但是发现有一个点竟然超过了int64和extended的届，呵呵。

第四题：走迷宫变形，有起始朝向，就是一秒钟内可以走1格、2格、3格，而且向左向右转也要耗费一秒。

爆容易的题目，难得写了。只有50×50的大小，不说广搜，深搜都能过啊。

课后孟LJ简单阐述了下搜索的优化，无非以下三种：

1、双向广搜（省时一半，较容易实现）；

2、普通判断剪枝（子树）；

3、估价函数剪枝（A*）。这种做法需要良好的估价能力，适合要打路径的题目。估价函数是一个可以求出从当前状态到目标状态的大概花费的函数，其值必须小于等于真实花费。所以，当走到一个（当前花费+估价花费>已知最小花费）的点时，完全可以把他的子树剪掉。这就是一种动态剪枝方法。效果甚佳，但本人未实现。