下午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
来源
@潘帕斯雄鹰改编
)
BtynDmPA.rar
