前言：第三题出奇的难，第二题让我觉得出奇的不可做。。。
a 机密信息
题目描述
FJ有个很奇怪的习惯，他把他所有的机密信息都存放在一个叫机密盘的磁盘分区里，然而这个机密盘中却没有一个文件，那他是怎么存放信息呢？聪明的你一定想到了，FJ的信息都是以文件夹名称的形式保存的。FJ给机密盘中的每一个文件夹都编了号，而FJ的机密信息是由S文件夹转到T文件夹的过程中必须经过的文件夹名称组合而成的，由于FJ的磁盘很慢，打开每个文件夹所耗费的时间等于该文件夹内下一级文件夹的数量。这次的任务是，给出每个文件夹的编号、名称以及它的父目录的编号和隐藏了FJ机密信息的起始文件夹编号和终点文件夹编号，你要计算出来的是FJ机密信息的长度以及寻找这个机密信息所需要的总时间。假设你一开始就在起始文件夹位置，此时耗费的时间为0；你每打开一个文件夹，能够知道的文件夹名除了当前这个文件夹名之外，还有该文件夹内下一级的文件夹名。
输入格式
输入文件的第一行为3个整数n、s、t，分别代表文件夹的个数、起始文件夹编号、终点文件夹编号，接下来n行，每行有2个整数i、pi和一个长度不超过255的字符串si（不包含空格）,用空格分开，pi是i号文件夹的父目录编号（为0时表示该文件夹为根目录下的一级文件夹），si是i号文件夹的名称。
输出格式
输出文件共2行，第一行是FJ的机密信息的长度，第二行是所消耗的时间。
输入样例
6 1 5
1 2 Lo
2 3 ra
3 0 .
4 3 bi
5 4 t
6 5 .COM
输出样例
8
4
3<=n<=10000，1<=i<=n，0<=pi<=n，保证一定有解。
解题思路(LCA)
本题又是一题送分题，但不少人没理解题目，变成了送命题。
很容易发现我们只要随便搜索或模拟一下就可以出解了。然而考场上的naive的我一开始以为是多组数据，然后就写了个倍增求LCA，后面就懒得改了，实际上只有一组数据，这样更慢，不如其他人直接一步一步模拟LCA。
然后这么水的题目有什么坑点呢？
题目意思说得很不清楚，导致很多人被坑。
①s文件夹已经打开了，不算它的时间。
②从下面打开t，是要算t的时间的，否则不算。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 10010
using namespace std;
int n, s, t, cur = -1, head_p[N], q[N], dep[N], f[20][N];
int C[N], child[N], path[N];
struct Tadj{int next, obj;} Edg[N];
char ch[300];
void Insert(int a, int b){
cur ++;
Edg[cur].next = head_p[a];
Edg[cur].obj = b;
head_p[a] = cur;
}
void ycl(){
int head = 0, tail = 0;
q[0] = 0;
dep[0] = 1;
f[0][0] = 0;
while(head <= tail){
int now = q[head++];
for(int i = head_p[now]; ~ i; i = Edg[i].next){
int v = Edg[i].obj;
q[++tail] = v;
f[0][v] = now;
dep[v] = dep[now] + 1;
child[v] += child[now];
path[v] += path[now];
}
}
for(int i = 1; i <= 18; i++)
for(int j = 0; j <= n; j++)
f[i][j] = f[i-1][f[i-1][j]];
}
int LCA(int x, int y){
if(dep[x] > dep[y]) swap(x, y);
for(int i = 18; i >= 0; i--)
if(dep[f[i][y]] >= dep[x]) y = f[i][y];
if(x == y) return x;
for(int i = 18; i >= 0; i--)
if(f[i][x] != f[i][y]){
x = f[i][x];
y = f[i][y];
}
return f[0][x];
}
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d%d%d", &n, &s, &t);
for(int i = 0; i <= n; i++) head_p[i] = -1;
int a, b, c;
for(int i = 1; i <= n; i++){
scanf("%d%d%s", &a, &b, &ch);
c = strlen(ch);
path[a] = c;
child[b] ++;
C[b] ++;
Insert(b, a);
}
ycl();
int stop = LCA(s, t), temp = (stop == t) ? t : f[0][t];
int Ans1 = path[s] + path[t] - path[stop] - path[f[0][stop]];
int Ans2 = child[s] + child[temp] - child[stop] - child[f[0][stop]] - C[s];
printf("%d\n%d\n", Ans1, Ans2);
return 0;
}b 路由器
题目描述
Farmer John 最近买了些新电脑，它向为奶牛们提供上网的机会，但是上网需要路由器，FJ想尽量少买路由器。FJ 有N个 (1 <= N <= 100,000)(编号为1..N)个农场，由 N-1 条长度是1的边连接起来，没有环. FJ 可以决定把路由器放在哪些农场. 每个农场只有长度为 K (0 <= K <= 10)的网线，该农场可以连接到距离小于等于K的路由器. 路由器本身已经可以连接到互连网，可以被放置到任意的农场.
FJ至少要买多少个路由器，才能让每个农场都能上网？农场想要上网的话，至少要连接到一个包含路由器的农场.
输入格式
- 第1行:两个整数: N 和 K
- 第 2..N行: 每行两个整数，表示两个农场之间有长度为1的边.
输出格式
第1行:一个整数，FJ至少需要买多少个路由器.
输入样例
8 2
3 6
7 1
1 8
2 4
1 4
4 5
2 6
输出样例
2
样例解释
有8个农场. 农场3和农场6有长度为1的边,等等
每个农场的网线最远只能够连接到2个单位长度的农场.
解题思路(贪心)
本题我在考场上想了将近2h，最后还是不会。我想这是不是一道dp呢？图论？二分答案+？yy了好久好久，最后我竟然败给了一条贪(cao)心(yu)题。
首先，略过考场上我脑抽想得那些乱七八糟的奇怪方法，最后没有任何用(为什么我就不曾想过贪心呢？)，回到正解贪心。
方法一：
我们发现，每个农场都要上网，这是解题的关键。我们先搞出一棵树，然后从深度最深的做起。因为最深的也要上网，而且它无法通过其后代的路由器来上网，必然是通过其上方的节点来上网。
经观察发现，必然是在其祖先上放最好，而且放在能放的最远处最好。因为当前点已经最深，与其共享同一个祖先的点也必然能上网。而越远，放置路由器的上方的点就有更大可能上网。于是我们简单证明了贪心的正确性。
于是我们按深度排序，将最深的当前不能上网的点向上跳至最远的能使其上网的点，然后将网络信号扩展，将能被影响到的点打上标记。然后继续重复此操作，指导所有点都能上网了为止，同时统计答案。
这个的时间复杂度呢，如果排序用桶排，仍旧无法保证是线性的，理论上最坏是平方级别的(不可能达到)，所以这就有点玄学了。因为每次打标记后的点还是可能放路由器，很多点会被重复搜到并重复打标记，所以这不是严格的线性了。但实测是能过的，下面有一种更加稳定可靠的方法。
方法二：
直接一遍dfs，并在dfs过程中搞贪心。我们记录两个数组far[]和near[]。far[]代表离当前点root最远的不能上网的后代(包括自己)离当前点的距离是多少呢？一开始far[root]=0；near[]代表离当前点root最近的安装了路由器的后代(包括自己)离当前点root的距离是多少呢？一开始near[root]=oo。我们发现这两个记录的信息很有意思，因为我们知道了最有用的路由器的位置和最需要被“拯救”的节点的位置，由于全部要能上网，所以必须要拯救那个节点。此时就可以贪心了。
dfs完后代后，先更新出near,far的值：
near[root] = min(near[root], near[v] + 1);
far[root] = max(far[root], far[v] + 1);
然后如果far[root] + near[root] <= K，代表不用在此点装路由器就可以使其后代(包括自己)全部上网，那么far[root] = -1。
如果far[root] == K，代表前面更新不了，而且安装路由器“迫在眉睫”，于是答案加1，far[root] = -1, near[root] = 0, Ans ++。
每个节点都保证其后代都能上网，更新记录的信息，是不是还有点dp的意味呢？这真是种巧妙无比的方法！
最后由于无法保证根节点1能上网，要特判一下(就是说根离最远的上不了网的点距离不足K，不用急迫的安装，但是往上已经没路了，而自己的一些后代和可怜的自己还无法上网)，这始这需要判断一下far[1]是否等于-1就行了。
这样，只有一次简单的dfs，维护一些东西，时间复杂度就严格的线性了。在Linux下也不会dfs爆栈(辣鸡winxp)。
当然，这不是本蒟蒻我想出来的，是一个女同学想出来的。。。。
(我并不知道考试时的我在想些什么)
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 100010
#define oo 1e9
using namespace std;
int n, Ans, K;
int cur, head_p[N], far[N], near[N];
struct Tadj{int next, obj;} Edg[N<<1];
void Insert(int a, int b){
cur ++;
Edg[cur].next = head_p[a];
Edg[cur].obj = b;
head_p[a] = cur;
}
void dfs(int root, int fa){
far[root] = 0; near[root] = oo;
for(int i = head_p[root]; ~ i; i = Edg[i].next){
int v = Edg[i].obj;
if(v == fa) continue;
dfs(v, root);
far[root] = max(far[root], far[v] + 1);
near[root] = min(near[root], near[v] + 1);
}
if(far[root] + near[root] <= K) far[root] = -1;
if(far[root] == K) far[root] = -1, near[root] = 0, Ans ++;
}
int main(){
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d", &n, &K);
cur = -1;
for(int i = 1; i <= n; i++) head_p[i] = -1;
int a, b;
for(int i = 1; i < n; i++){
scanf("%d%d", &a, &b);
Insert(a, b);
Insert(b, a);
}
dfs(1, 0);
if(~ far[1]) Ans ++;
printf("%d\n", Ans);
return 0;
} c 骨牌游戏
题目描述
解(bao)题(ling)思路
留坑待填。
总结
会做的题一定要拿下，不会做的题一定要尽可能水分。平时积累做题经验，考试时不要紧张，要迅速进入状态。
梦话要在睡着的时候说，是这个世界的规则。