CQ-NOIP round5 游记

这个..先把题目贴上来。

1、回文图
（palindrome.c/cpp/pas）
【问题描述】
有一片透明玻璃，我们可以在上面涂色。涂色后，你可以对它做两种操作：
1.旋转，顺时针或逆时针旋转 90 度；
2.翻转，水平或垂直翻转 180 度；
不管进行多少次旋转或翻转，我们看到都是相同的图形，我们把这样的图形称为"回文
图"。
下图是操作示例。

现在给你一块 n*n 的方格状透明玻璃和 k 种颜色的油漆。请你给每个方格都涂上颜色，
涂完后得到一幅回文图。但是这块玻璃上有 m 个方格事先已被涂上了颜色，你不能修改它
们。
请问，总共能画出多少种不同的回文图？
【输入格式】
第一行，三个空格间隔的整数 n,m,k
接下来 m 行，每行两个整数 x 和 y，表示坐标为(x,y)的格子已被涂上了颜色(0 <= x,y <
n)。【输出格式】
输出仅一行为一个整数，表示方案总数，结果可能很大，请输出 Mod 100 000 007 后
的结果。 【输入样例 1】
3 0 2
【输出样例 1】
8
【输入样例 2】
4 2 3
1 1
3 1
【输出样例 2】
3
2、分礼物
（gift.cpp/c/pas）
【问题描述】
一颗圣诞树挂有很多礼物，每个礼物都挂在树的分叉点或树枝端点上。挂有礼物的
点标记为 1，没挂礼物的标记为 0，现在要把这些礼物连同树枝分给小盆友（当然一个
小盆友只能分一个礼物）需要把圣诞树剪成很多小树，且保证一棵小树上有一个礼物。
请你计算一下共有多少种不同的剪法方案数。由于答案比较大，只需输出对 1000000007
取模即可。 【输入格式】
第一行 n,表示树共有 n 个节点，从 0 开始编号。
以下 2 到 n 行每行一个数，表示编号 i-1 的节点的父亲编号
第 n+1 行共 n 个数,若第 i 号节点有礼物，则为 1，否则为 0. 【输出格式】
一个整数，若无法保证一棵小树上有一个礼物输出 0. 【输入样例】
6
0
0
1
1
3
1 0 0 0 1 1
【输出样例】
5
【数据范围】
对于 30%的数据：n<=10
对于 70%的数据：n<=1000
对于 100%的数据：n<=100000
3、光通讯
（light.cpp/c/pas）
【问题描述】
BB 和 SS 是一对好盆友，他们制作了两部光学仪器，使用光缆测试通讯。BB 和 SS
所在的地方有 N 栋楼、M 条双向光缆。每条光缆连接两栋楼，仪器发出的光信号只能沿着
光缆传递，当然通讯需要时间。现在 BB 要进行 Q 次试验，每次选取两栋楼，并想知道仪
器的光信号在这两栋楼之间传递至少需要多长时间。
说明：N 栋楼通过光缆一定是连通的，光缆连接三类情况：
A：光缆仅有 N-1 条。
B：光缆仅有 N 条。
C：每条光缆仅在一个环中。 【输入格式】
第一行包含三个用空格隔开的整数，N、M 和 Q。
接下来 M 行每行三个整数 x、y、t，表示楼 x 和 y 之间有一条传递时间为 t 的光缆。
最后 Q 行每行两个整数 x、y，表示 BB 想知道在 x 和 y 之间通讯最少需要多长时间。 【输出格式】
输出 Q 行，每行一个整数，表示 BB 每次试验的结果。 【输入样例 1】
5 4 2
1 2 1
1 3 1
2 4 1
2 5 1
3 5
2 1
【输出样例 1】
3
1
【输入样例 2】
5 5 2
1 2 1
2 1 1
1 3 1
2 4 1
2 5 1
3 5
2 1
【输出样例 2】
3
1
【输入样例 3】
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
【输出样例 3】
5
6
【数据规模和约定】
送分数据占 10%，2<=N<=1000，N-1<=M<=1200。
A 类数据占 30%，M=N-1。
B 类数据占 50%，M=N。
C 类数据占 10%，M>N。
对于 100%的数据，2<=N<=10000，N-1<=M<=12000，Q=10000，1<=x,y<=N，
1<=t<32768。

T1果断模拟翻转旋转+乘法原理，因为只用看一个(n+1)/2*(n+1)/2大小的矩阵，直接for循环走人了。

T2一脸懵逼，看同考场的同学也是众脸懵逼，想了30到40来分钟的样子跳走。

T3有90分都是模板题，特别好写，不到10来分钟就写好了，1A样例，自己出了组数据也没问题，最后10分一脸懵逼，走人。

搞完T3距离考试结束还有90来分钟的样子，留在T2懵逼，怎么也没懵逼出来.....

最后20分钟发现实在是没有办法直接输出n-1，然后开始捣鼓我的kindle..

期望得分190，第二题直接输出n-1还过了样例好开心，后来发现190在CQ已经是非常高的分数了。

出考场的时候瞥了一眼其他同学的T1看到好几个快速幂wtf？？跟另外一个同学对了一下算法发现没问题就开开心心的去吃饭了。

吃完饭回来发现爆零了！！赫然发现评测机是xp系统，赫然发现我全写的是longlong，全用的lld...

抱着希望把lld改了一下，但是第一题还是炸了！只剩10分！

后来听AC的同学说这个题还要考虑翻转+旋转一起搞的情况，加上之后果断AC..

T3改后只有80分，发现是因为送分的数据SPFA的队列清空太慢了，把数组开小一点也拿到了送来的10分..

尴尬死了..还以为能走上人生巅峰呢..

第一题真的考细心，以后做T1的时候一定要多花一点时间检查算法错误，注意细节。

难的大家都做不来，尽量骗分。

模板题比较少见，见到一定拿稳。