下午2:30-5:30
潘帕斯雄鹰NOIP2007模拟赛 for 高中组(提高组)
全国700多位选手参加了本次比赛,我也在网上考了,现在将题目发出来供大家讨论

飞翔
背景
鹰最骄傲的就是翱翔，但是鹰们互相都很嫉妒别的鹰比自己飞的快，更嫉妒其他的鹰比自己飞行的有技巧。于是，他们决定举办一场比赛，比赛的地方将在一个迷宫之中。
题目
这些鹰的起始点被设在一个N*M矩阵的左下角map[1，1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角，有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示：

没有障碍，也没有死路。这样设计主要是为了高速飞行的鹰们不要发现死路来不及调整而发生意外。潘帕斯雄鹰冒着减RP的危险从比赛承办方戒备森严的基地中偷来了施工的地图。但是问题也随之而来，他必须在比赛开始之前把地图的每一条路都搞清楚，从中找到一条到达终点最近的路。（哈哈，笨鸟不先飞也要拿冠军）但是此鹰是前无古鹰，后无来鹰的吃菜长大的鹰--菜鸟。他自己没有办法得出最短的路径，于是紧急之下找到了学OI的你，希望找到你的帮助。
输入
首行为n,m(0<n,m<=100000),第2行为k（0<k<=1000）表示有多少个特殊的边。以下k行为两个数，i,j表示map[i,j]是可以直接穿越的。
输出
仅一行，1，1-->n,m的最短路径的长度，四舍五入保留到整数即可
样例输入
3 2
3
1 1
3 2
1 2
样例输出
383
来源
@潘帕斯雄鹰经典问题改编

拼图
背景
潘帕斯草原最近流行起了一种拼图游戏，@潘帕斯雄鹰为了显示自己是最强的鹰，想尽办法要在这个游戏上赢过其他鹰……

题目描述
这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从1到5。如下图所示，图形个数是4。

图形不能旋转，拼的时候不能重叠，拼完后的正方形里面不能有空隙。所有给定的图形都要使用。



左面的图表示这样拼不行，右面是一个成功的拼法。
现在，@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰；如果可以，请输出一种完成这个游戏的方案。

输入格式：
文件的第一行是一个整数n，表示图形的个数，范围从1到5。
接下来有n个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用0和1表示，1表示图形占有这个位置，0表示不占有，中间没有空格。例如上图中图形A的描述是
2 3
111
101
所有图形的长与宽都不超过5。
根据图形给出的顺序给每个图形编号，从1开始，至多到5。
保证数据无多解情况。
输出文件：
如果不能拼成一个正方形，就输出“No solution possible”；否则，输出一种拼的方案：一个正方形的数阵，每个位置上的数字是占有这个位置的图形的编号，中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4，那么就可以输出
1112
1412
3422
3442

输入样例1：
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001

输出样例1：
No solution possible

输入样例2：
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1

输出样例2：
1133
1153
2223
2444
来源
dai

比赛
背景
为了给好友老鹰送上一份生日大礼，土豆国王召集土豆王国的所有子民，让他们组建N支篮球队，进行单循环比赛（任意两队之间比赛一场）。这N支球队需要安排一个比赛日程表，庞大的数据量，使得土豆国王头疼不已，很多土豆大臣都累成了土豆泥。
问题
土豆国王把这个任务交给你，请你帮他安排一个日程表。
特别注意：比赛分成N轮进行，每轮比赛都有N div 2场比赛同时进行、并有一支球队轮空，即：每支球队共参加N-1场比赛。
保证数据无多解情况。
输入
第一行两个整数N（3<=N<=499，N为奇数），M（1<=M<=N），T（1<=T<=N）,其中N表示球队数量。
第二行到第N+1行，每行一个正整数，第i行表示编号为M的球队第i-1轮的对手球队的编号，如果第i行为M表示该队该轮轮空。
输出
1行共N个正整数。输出第T轮的所有比赛，第i个整数表示编号为i的球队的对手编号。如果第i个整数为i，则表示该队该轮轮空。
同一行相邻两个整数之间，用一个空格符间隔。
样例
match.in
3 1 2
3
1
2
match.out
1 3 2
来源
琥珀（从头再来）

羽毛
背景
众所周知，潘帕斯草原是雄鹰翱翔的地方，那里有很多的鹰，@潘帕斯雄鹰为了展示自己的与众不同将自己的羽毛进行了染色，由此给自己引来了麻烦
题目
在潘帕斯草原上牛甚多，他们统治着草原的中心部分，鹰的领地环绕着牛所在的地方，而且每个鹰都有一片自己的领地。在@潘帕斯雄鹰将羽毛进行染色后，其他的鹰纷纷效仿，也想把自己的羽毛染成五颜六色。但是问题随之而来，相邻的两个鹰（1和2相邻，1和n也是相邻的）如果发现对方身上有和自己有一样颜色的羽毛就会和对方进行一场你死我活的空中战斗。为了避免这种情况必须要想一种办法才行。由于@潘帕斯雄鹰是第一个将羽毛进行染色的鹰，他被鹰们指派去买颜料(自费T_T)，买颜料当然是要花钱的。@潘帕斯雄鹰想尽量的少买颜料。他发现由于各个鹰的喜好不同，他们想在身上染的颜色种类的个数也是不一样的，有些鹰喜欢把自己的羽毛涂的颜色多些，有些则少。通过统计得出了第i个鹰想在自己身上涂Ai种颜色。你现在的任务是维护世界和平找到最少的颜色种类使得每个相邻的鹰身上的羽毛颜色都可以没有相同的。
输入
第一行n(1<=n<=20000)
第二行开始每行有一个数ai(1<=ai<=100000)表示第i个鹰要在身上涂ai种颜色
输出
一个数，即最少的满足条件的颜色种类
样例
feather.in
4
2
2
1
1
feather.out
4
来源
@潘帕斯雄鹰改编

说实话,十分不好做
第一题DP空间不足,搜索太慢
第二题可以简单的搜索(我写了一个多小时,300行代码)
第三题打眼一看看的比较乱,直接输出的样例
第四题我用的取相临最大值法,通过了30%

对比NOIP历年试题,这次试题没有一个"送分题",可以说考出了NOIP的多样性与水准
给出标程和测试数据(.PAS)

当成伪代码看就可以了,pascal结构化很强的

以前没有做过提高组的题,平常练习的都是普及组(初中组)的,所以这次考的不理想,评测才80(由于这次修改加强了评测数据,如果是正规考试用正常数据最后一题我还能多得30分,因此如果是正规考试应该是110),看自己的名次和分数,按照正规noip比赛,应该在我们这儿(山东)至少是二等奖,一般是一等,因为noip提高每次分数线都在100左右,且题比这个简单一些

[此贴子已经被作者于2007-8-9 9:13:38编辑过]

没这么简单,必须细化分治,这是最难的,因为这次改了原测试数据,在未改前的数据,用那个方法能得60分,不过改数据后只能的30分

[此贴子已经被作者于2007-8-9 9:07:12编辑过]

n,m(0<n,m<=100000),k（0<k<=1000）
当时考虑的是时间m^2,空间n*m,当成0/1背包做的

[此贴子已经被作者于2007-8-9 9:11:41编辑过]

据说可以通过暴力穷举先找出几个小数据,然后可以找出规律,我想过构造,不过做题时一看就晕,没看懂题

以前做过一道考察最长不下降序列的DP题(防御导弹),其实最长不下降序列(就是你说的最长递增序列)与那个一个道理,只不过是正推,不过当时没有想到那些,看到m,n后就先向后做了

用贪心一律30分,而根据评测结果看,几乎做这道题的100%的都用贪心

[此贴子已经被作者于2007-8-9 15:58:55编辑过]

潘帕斯雄鹰生日模拟赛解题报告

飞翔 题解
(@潘帕斯雄鹰写)
这个题目很容易想到是DP，没错，这个题目就是DP，但是以最标准的思想列出方程
f[i,j]表示在map[i,j]到map[1,1]的最小值
则：f[i,j]=min{f[i-1,j],f[i,j-1]}+1 如果存在特殊边再这样处理一下
f[i,j]=min{f[i,j],f[i-1,j-1]+sqrt(2)}
ans=round(f[n,m])即可
但是这样就有两个问题，一个是时间复杂度问题O(nm)在这个题目中是TLE的
另一个问题是空间复杂度问题O(nm)的空间在这个题目中是MLE的

那让我们换一个思路，如果能走特殊路，必然要走特殊路，这个是显然的。
从map[i,j]到map[i+1,j+1]最多有三条路，其中的两条长度为2，而如果有特殊路，其长度为sqrt(2)
而这里k只有1000
在这1000个路中寻找最长的可走路线
即lis的变形问题。这个复杂度是O(k^2)。
实现方式，首先字典排序，把边的顺序处理好，然后lis，最后利用数学推导在取x条特殊路的时候所走的路线即可。
详细的细节参考code

还有一种思路就是利用这k个点做最短路径。这个也是可以的算法同样为O(k^2)。在题目审核的时候某位题审就是这样用spfa AC的。

这个题目是比较标准的DP了，同时也可以用图论做。并且题目本身并不难。本题其实有一个提示，M、N都是非常大的数，如果从m、n去考虑只有O(M+N)的算法能够AC，但是K十分的小，这就是提示，让大家往K的复杂度上想。和noip2006 2一样，很多大牛当时都看做tree-dp来做，其实看到附件的个数并不是很多，就可以作为背包搞定了，也减少了很多的编写复杂度。
此题考察：对算法的设计 DP 最短路

拼图 题解
Dai@Gzez
此题实质上是一道比较特殊的搜索题。难度较小，可以说得上是本次比赛最容易的题目。本题大意是给出若干块拼图，要求拼出一个正方形。
数据的设置是9个点有解，1个点无解。
本题有几个技巧需要注意：
剪枝
在这道题里剪枝并不重要，相反如果剪得不好可能会出错。一种比较好的方法是先算出所有的“有效面积”，然后看看它的平方根是不是整数。可惜在本题中，我们设置的数据得出的结果都是整数，不过对于这道题来说这个方法仍然很有效。
方块的处理
这道题的第一个数据是我设计的一个算是比较阴险的数据，给出的是一个4*4的
1000
0000
0000
0000
这样的拼图。
这种拼图的处理比较麻烦，标准程序偷懒仅使用了“单位面积判1法”，实质上推荐的做法是开一个辅助的数组记录当前与后面的行是否均为空，比如说上面的就会变成这样：
0111
1111
1111
1111
这个时候处理就方便得多了。当然方法不一，这种未必是最好的。这样的数据只有一个，还是考虑到这样的东西比较难处理的关系。
其他细节方面
这题判断能否放不能单独判断“当前方块是否已放”这么简单，详情可以参考标准程序的CanPut过程。
这道题目总体解决流程比较容易，先判断CanPut，然后PutinMap，然后搜下一层，搜不到就回朔。
希望大家在这道题中有所收获。

比赛 题解
(真圣灵骑士版)
从头再来大牛出的题目，题解应该由他去写，他家里突然出了一点事情，题解过两天才能公布
这个题目先发布我尊贵的题审真圣灵骑士大牛写的题解
————————————————————————————————————————————-
汗，这个题目其实是我蒙对的……
先用暴力搜索搜了几个小数据，发现是唯一解，而且有规律的。然后就把规律找出来了。我写两组就知道规律了。

IN
3 1 2
2
1
3

队伍 1 2 3
第一场 2 1 3
第二场 1 3 2
第三场 3 2 1

IN
5 2 4
1
3
2
5
4
队伍 1 2 3 4 5
第一场 2 1 3 5 4
第二场 5 3 2 4 1
第三场 4 2 5 1 3
第四场 1 5 4 3 2
第五场 3 4 1 2 5

观察：第一组数据：开始给的1号队伍的比赛，2，1，3；后来构造出来后，2号队伍比赛：第一场已知，打1号，然后下来是1，3，2和1号队伍纵向顺序一致，只是开头不位置不一样；3号队伍也一样，1，3，2的顺序，从第三场开始的。

第二组数据一样：还是1，3，2，5，4的错位循环。

于是大胆猜测：就是个错为循环过程，每个队伍循环开始打头的位置就是他和给定的M队打的那轮。

分析完了，程序实现很简单了，程序里有说明
————————————————————————————————————-
以下为@潘帕斯雄鹰所写
本题中真圣灵骑士大牛使用的方法是类数独的方法，从头再来大牛在出这个题目的时候用的是数论中的同余问题。
从头再来大牛的题解将在他的blog上发布，时间大约为8月20日
本题考察：基本数学问题--同余问题、数独问题

羽毛 题解(@潘帕斯雄鹰写)
这个题目是本次比赛的难题，在我找到的众多题审中也没有哪位能轻松AC的。但是一个比较特别的可能是很好找的。那就是相邻的max值作为ans。这种情况在偶数情况下显然是成立的。在我生成数据的时候发现奇数的情况也是大多成立的，反例很好找
3
5
5
5
显然答案是15，而特殊情况的值是10
这样的方法原数据可以拿到60分，但是我对数据进行了改动，在本次比赛中只有30分。
在此声明：本题目并非原创题目，题目来源于浙江省06年省选day2的第四题。
面对这样大的数据范围，一般想到的就是比较特别的算法：数学、贪心、二分查找。
本题就是一道二分查找的题目。
每次判断的规则是：
function check(m : longint) : boolean;
var
l, p, occupy, i : longint;
begin
check := false;
occupy := a[1];
for i := 2 to n do begin
l := m - a[i - 1];
p := a[1] - occupy;
if not odd(i) then
occupy := min(p, a[i])
else
occupy := max(0, a[i] - l + p);
end;
check := occupy = 0;
end;
对于i为偶数的时候尽量用第一个使用的颜色
i为奇数的时候尽量用第二个使用的颜色
如果不够用就增加颜色的种类
因为这样颜色就不可能重复。同时，对于最后访问到的那个数来说，两边都没有用的颜色如果刚好等于那个鹰所需要的颜色，那么必然是一个解

lxw是一个数学教授，像这种带有数学性的问题组合数不可能了，06年刚考过，计算几何很多牛都说考的几率要大，个人觉得是有些可能，而二分查找，以前考过一个题目，个人感觉这个算法的数学性比较强，07年的noip的几率也是比较大的。故出此题。希望大家对这类题目有所准备

总结
至此本次比赛圆满完成，让我们一起看一下本次比赛所涉及到的知识：最短路径、动态规划、搜索、数论问题、数独问题、二分查找
换一种思路看所考察知识：图论、动态规划、搜索、数学、基础算法。至此除了数据结构外的题目外本次比赛涉及到的noip考察部分已经完全。数据结构的题目实在是不好出，noip范围比较小我们出不了有水平的此类题目。故因能力问题，本次比赛没有涉及此类问题。请大家见谅。

感谢大家参加本次比赛，祝大家在noip2007中取得优异的成绩。over