这次考试100+100+40+0=240分，制杖的我第四题要是给多2分钟就对了啊( ⊙ o ⊙ )啊！
第一题：
https://61.142.113.109/senior/#main/show/2567
题目描述：
2567. 【NOIP2011模拟9.17】电话时间 (StandardIO)
某人总是花很多时间给父母打电话。有一次他记录了打电话的开始时间和结束时刻t1和t2，请你帮他算算此次通话一共用了多少秒。又有一次，他记录了打电话的开始时刻t1和通话的时间长度len，请你帮他计算他在什么时刻结束通话。 已知每次通话时间小于24个小时。
Input
输入文件phone.in的第一行为一个正整数T，表示了数据组数。 接下来T行，每行第一个数为k： 如果k = 0，接下来包含两个时间t1和t2，表示了打电话的开始时间和结束时刻，用一个空格隔开，时间格式为HH:MM:SS，其中0≤HH≤23,0≤MM,SS≤59。HH、MM和SS都是两位数字，因此0:1:2是不合法的时间（应写作00:01:02）。你应该对这个询问输出通话时间长度，答案一定为区间[0,86400)之内的非负整数。 如果k=1，接下来包含一个时间t1和一个非负整数len，表示了打电话的开始时刻与通话时间长度，用一个空格隔开，时间格式同为HH:MM:SS，同样时间小于24个小时，即len<86400。你应该对这个询问输出结束通话的时刻，同为HH:MM:SS格式。
Output
输出文件phone.out包含T个整数或者时间，对于每个询问输出对应的答案。
Sample Input
4
0 01:02:03 04:05:06
0 23:59:59 00:00:00
1 00:00:03 3
1 23:59:58 4
Sample Output
10983
1
00:00:06
00:00:02
对于20%的数据，T ≤ 10； 对于40%的数据，T ≤ 100； 对于100%的数据，T ≤ 100000。
这是一道很容易WA的水题，好多细节要注意处理，
其实只要用字符串输入后把时间转化成秒数，之后如果k=0就输出两个秒数和相减，
否则就按格式输出把两个秒数和相加后化成小时：分钟：秒钟的格式，
如果大于等于24小时还要减去24小时
参考程序：
var t,i,hh,mm,ss,x1,x2,len:longint; s:string; begin readln(t); for i:=1 to t do begin readln(s); if s[1]='0' then begin hh:=(ord(s[3])-48)*10+ord(s[4])-48; mm:=(ord(s[6])-48)*10+ord(s[7])-48; ss:=(ord(s[9])-48)*10+ord(s[10])-48; x1:=ss+mm*60+hh*3600; delete(s,1,11); hh:=(ord(s[1])-48)*10+ord(s[2])-48; mm:=(ord(s[4])-48)*10+ord(s[5])-48; ss:=(ord(s[7])-48)*10+ord(s[8])-48; x2:=ss+mm*60+hh*3600; if x2<x1 then x2:=x2+24*3600; writeln(x2-x1); end else begin hh:=(ord(s[3])-48)*10+ord(s[4])-48; mm:=(ord(s[6])-48)*10+ord(s[7])-48; ss:=(ord(s[9])-48)*10+ord(s[10])-48; x1:=ss+mm*60+hh*3600; delete(s,1,11); val(s,x2); x1:=x1+x2; if x1 div 3600 mod 24 div 10>0 then write(x1 div 3600 mod 24,':') else write(0,x1 div 3600 mod 24,':'); x1:=x1 mod 3600; if x1 div 60 div 10>0 then write(x1 div 60,':') else write(0,x1 div 60,':'); x1:=x1 mod 60; if x1 div 10>0 then writeln(x1) else writeln(0,x1); end; end; end.
第二题：
https://61.142.113.109/senior/#main/show/2568
题目描述：
2568. 【NOIP2011模拟9.17】地铁建设 (StandardIO)
某地铁沿线共设N站，可分为U（地面式）、D（地下式）和C（复合式）三种类型。为避免单调，相邻地铁站的类型不能重复。同时，由于地铁站所处环境和地质条件有所差异，每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本，请计算出该地铁线的最低总造价。
Input
输入文件subway.in包含N+1行： 第1行为一个正整数，表示地铁站的总数N。 第2行到第N+1行分别包含用空格分隔的三个正整数U，D和C。其中第i+1行表示第i个地铁站按U、D 或C 类型的建设成本，1≤i≤N。
Output
输出文件subway.out只包含一个正整数，表示建成这N个地铁站所需要的最低成本。
Sample Input
3
1 99 99
99 1 99
99 99 1
Sample Output
3
对于20%的数据，N≤10； 对于40%的数据，N≤1000； 对于100%的数据，N≤200000，1≤U, D, C≤10000。
很明显是一道动态规划（or 递推？）问题，设f[i,j]表示第1~i个火车站，其中第i个火车站建第j（j=1~3）种类型的最小值；
那么：
f[i,1]:=min(f[i-1,2],f[i-1,3])+a[i,1];
f[i,2]:=min(f[i-1,1],f[i-1,3])+a[i,2];
f[i,3]:=min(f[i-1,1],f[i-1,2])+a[i,3];
参考程序：
var n,i:longint; a,f:array[0..200000,1..3]of longint; function min(x,y:longint):longint; begin if x<y then exit(x) else exit(y); end; begin readln(n); for i:=1 to n do readln(a[i,1],a[i,2],a[i,3]); for i:=1 to n do begin f[i,1]:=min(f[i-1,2],f[i-1,3])+a[i,1]; f[i,2]:=min(f[i-1,1],f[i-1,3])+a[i,2]; f[i,3]:=min(f[i-1,1],f[i-1,2])+a[i,3]; end; writeln(min(min(f[n,1],f[n,2]),f[n,3])); end. 第三题： https://61.142.113.109/senior/#main/show/2569 题目描述：2569. 【NOIP2011模拟9.17】旅行 (StandardIO)
X先生来到了一个奇怪的国家旅行。这个国家有N个城市，每个城市均有且仅有一个机场，但是这机场所有航班只飞往一个城市。每个城市有一个游览价值，第i个城市的游览价值为A[i]。 现在他想知道，从第i个城市出发，并只坐飞机飞往下一个城市，游览价值之和最多是多少（一个城市游览多次只计算1次游览价值）
Input
输入文件travel.in的第1行为一个正整数N。 第2行有N个非负整数A[i]，表示了每个城市的游览价值。 第3行有N个正整数F[i]，表示第i个城市的航班飞往的城市为F[i]，可能出现F[i] = i的情况。
Output
输出文件travel.out包括N行，第i行包含一个非负整数，表示从第i个城市出发游览价值之和的最大值为多少。
Sample Input
8
5 4 3 2 1 1 1 1
2 3 1 1 2 7 6 8
Sample Output
12
12
12
14
13
2
2
1
对于20%的数据，N≤10； 对于40%的数据，N≤1000； 对于100%的数据，N≤200000，A[i]≤10000，F[i]≤N。
很明显的，这题如果暴力找每个数的循环算答案的话，只能得到40~50分
那么，我们可以先用拓扑找出所有环里面的点（就是每次把没有父亲的节点杀掉，那么最后剩下的点一定是互相成一个环或多个环），
同一个环的节点一定结果相同，
所以当我们枚举一个节点时，如果他在环内，且没有算过值，那么我们就暴力找它的环，每次到它的孩子节点，并把节点记录下来，直到重复为止，之后把计算到的值赋值到每个环内的数
如果它不在环内，就要把它向它的孩子节点 一直这样找，直到当前的孩子节点为环内的为止，那么结果就是每次找的节点和+环内的节点和
参考程序：
var n,i,t,s,j:longint; ff:Array[0..200000] of boolean; a,b,f,c,d:array[0..200000]of longint; bz:boolean; function dfs(x:longint):longint; begin if b[x]>0 then exit(c[x]); b[x]:=1; c[x]:=c[x]+a[x]+dfs(f[x]); exit(c[x]); end; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do begin read(f[i]); inc(b[f[i]]); end; bz:=true; while bz do begin bz:=false; for i:=1 to n do if b[i]=0 then begin dec(b[i]); dec(b[f[i]]); bz:=true; end; end; fillchar(ff,sizeof(ff),1); for i:=1 to n do begin if (b[i]>0) and ff[i] then begin ff[i]:=false; d[0]:=0; t:=i; s:=0; repeat inc(d[0]); d[d[0]]:=t; s:=s+a[t]; t:=f[t]; ff[t]:=false; until (t=i); for j:=1 to d[0] do c[d[j]]:=s; end; end; for i:=1 to n do if b[i]<1 then begin b[i]:=1; c[i]:=c[i]+a[i]+dfs(f[i]); end; for i:=1 to n do writeln(c[i]); end.
第四题：
https://61.142.113.109/senior/#main/show/2570
题目描述：
2570. 【NOIP2011模拟9.17】数字生成游戏 (StandardIO)
小明完成了这样一个数字生成游戏，对于一个不包含0的数字s来说，有以下3种生成新的数的规则： 1.将s的任意两位对换生成新的数字，例如143可以生成341，413，134； 2.将s的任意一位删除生成新的数字，例如143可以生成14，13，43 3.在s的相邻两位之间s[i]，s[i + 1]之间插入一个数字x，x需要满足s[i]<x<s[i + 1]，即比它插入位置两边的数小。例如143可以生成1243，1343，但是不能生成1143，1543等。 现在小明想知道，在这个生成法则下，从s开始，每次生成一个数，可以用新生成的数生成另外一个数，不断生成直到生成t至少需要多少次生成操作。 另外，小明给规则3又加了一个限制，即生成数的位数不能超过初始数s的位数。若s是143，那么1243与1343都是无法生成的；若s为1443，那么可以将s删除4变为143，再生成1243或1343。
Input
输入文件gen.in的第一行包含1个正整数，为初始数字s。 第2行包含一个正整数m，为询问个数。 接下来m行，每行一个整数t（t不包含0），表示询问从s开始不断生成数字到t最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字s。
Output
输出文件gen.out包括m行，每行一个正整数，对每个询问输出最少操作数，如果无论也变换不成，则输出-1。
Sample Input
143 3 134 133 32
Sample Output
1 -1 4
Data Constraint
【样例说明】 143->134 133无法得到 143->13->123->23->32 【数据规模与约定】 对于20%的数据，s<100； 对于40%的数据，s<1000； 对于40%的数据，m<10； 对于60%的数据，s<10000； 对于100%的数据，s<100000，m≤50000。
先进行一次暴力宽搜，把所有初始值可能生成的数都枚举出来，输入的时候就判断这个输入的数是否生成过，生成过就输出需要几步生成，否则输出-1
参考代码：
var s,i,j,k,l,r,t,len,q,lens,m,x:longint; data:array[0..2000000,1..2]of longint; bz:array[0..100000]of longint; p:array[1..6]of longint=(1,10,100,1000,10000,100000); st,st2:string; begin readln(s); str(s,st); lens:=length(st); l:=0; r:=1; data[1,1]:=s; while l<r do begin inc(l); str(data[l,1],st); len:=length(st); t:=0; for i:=1 to len do t:=t+p[len-i+1]*(ord(st[i])-48); for i:=1 to len-1 do for j:=i+1 to len do begin q:=t-p[len-i+1]*(ord(st[i])-48)-p[len-j+1]* (ord(st[j])-48)+p[len-i+1]*(ord(st[j])-48)+ p[len-j+1]*(ord(st[i])-48); if bz[q]=0 then begin inc(r); bz[q]:=data[l,2]+1; data[r,1]:=q; data[r,2]:=data[l,2]+1; end; end; if len>1 then for i:=1 to len do begin st2:=st; delete(st2,i,1); val(st2,q); if bz[q]=0 then begin inc(r); bz[q]:=data[l,2]+1; data[r,1]:=q; data[r,2]:=data[l,2]+1; end; end; if len<lens then begin for i:=1 to len-1 do begin for j:=ord(st[i])-47 to ord(st[i+1])-49 do begin if j=0 then continue; st2:=copy(st,1,i)+chr(j+48)+ copy(st,i+1,len-i+1); val(st2,q); if bz[q]=0 then begin inc(r); bz[q]:=data[l,2]+1; data[r,1]:=q; data[r,2]:=data[l,2]+1; end; end; end; end; end; readln(m); for i:=1 to m do begin readln(x); if x=s then writeln(0) else if bz[x]=0 then writeln(-1) else writeln(bz[x]); end; end.