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

飞翔 题解
(@潘帕斯雄鹰写)
这个题目很容易想到是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