首页 > 代码库 > USACO 2014 FEB 银组
USACO 2014 FEB 银组
1.自动打字{Silver题1}
【问题描述】
贝西新买了手机，打字不方便，请设计一款应用，帮助她快速发消息。
字典里有W（W<=30000）个小写字母构成的单词，所有单词的字符总数量不超过1,000,000，这些单词是无序的。现在给出N(1 <= N <= 1000)个询问，每个询问i包含一个的字符串s_i（每个字符串最多包含1000个字符）和一个整数K_i，对于所有以s_i为前缀的单词，其中按字典序排序后的第K_i个单词，求该单词在原字典里的序号。
【文件输入】
第一行为两个整数W和N。
接下来2..W+1行，每行一个单词；
接下来W+2..W+N+1行，一个整数和一个字符串，分别表示K_i和s_i。
【文件输出】
输出共N行，每行一个整数，表示位置，如果无解则输出-1。
【输入样例】
10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da
【输出样例】
3
1
-1
【样例说明】
以a为前缀的单词有{aa,aaa,aab,ab,abc,ac}，第4个是ab，它在原字典中的位置是3，以da为前缀的单词有{daa,dab,dadba}，第2个是dab，它在原字典中的位置是1，以da为前缀的第4个单词不存在。
2. 路障{silver题2}
【问题描述】
农民约翰的农场n(1 <= N <= 250)个结点，有M(1 <= M <= 25,000）条带权值的有向边，任意两个结点之间最多有一条边相连，任意两个结点之间都有连通的路径。他的家在结点1，谷仓在结点n，他每天都从家选择最短的路径走到谷仓。
牛们开始捣乱，选择在某一条边上放置路障，使得该边的权值变为原来的2倍。求最大能使约翰多走多少路。
【文件输入】
第一行，两个用空格隔开在整数N和M。
接下来M行，每行3个整数，A_j，B_j和L_j，分别表示一条边的两个结点和权值（权值是1...1,000,000的整数）。
【文件输出】
一个整数，表示最大值。
【输入样例】
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
【输出样例】
2
【样例说明】
原来的最短路径是1-3-4-5，总长为6，将路障放置3和4之间的边上，使得该边的权值变为6，则最短路径变为1-3-5，总长为8，增加了长度2。
第一题字符串处理 排序
var w,i,j,k,m,n,p:longint; a:array[0..30000] of string; num:array[0..30000] of longint; len:longint; s:string; pre:string; ch:char; //t:array[0..26,30000] of string;procedure sort(l,r: longint); var i,j: longint; x,y: string; z:longint;begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; z:=num[i]; num[i]:=num[j]; num[j]:=z; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r);end;begin assign(input,‘auto.in‘); reset(input); assign(output,‘auto.out‘); rewrite(output); readln(N,w); for i:=1 to n do readln(a[i]); for i:=1 to n do num[i]:=i; sort(1,n); for i:=1 to w do begin readln(k,ch,pre); //delete(pre,1,1); for j:=1 to n do begin if a[j][1]=pre[1] then begin s:=copy(a[j+k-1],1,length(pre)); if s=pre then begin writeln(num[j+k-1]); break; end else begin writeln(‘-1‘); break; end; end; end; end;close(input);close(output);end.
第二题
可以知道改变的边一定是在原最短路径上，不然John就可以按原最短路径走了。
先做一边Dijkstra 记下路径，再枚举路径，做Dijkstra。
var i,j,n,m,s,t,p,min,x,y,k,l:longint; a:array[0..1000,0..1000]of longint; d,pre:array[0..1000]of longint; v:array[0..1000]of boolean; a1,b1:longint; ok:boolean;procedure dijkstra(s:longint);begin fillchar(d,sizeof(d),$7f); fillchar(v,sizeof(v),false); d[s]:=0; for j:=1 to n do begin min:=maxlongint; for i:=1 to n do if (not v[i]) and (d[i]<min) then begin p:=i; min:=d[i]; end; v[p]:=true; for i:=1 to n do if (not v[i])and(a[p,i]<>0)and (d[p]+a[p,i]<d[i]) then begin d[i]:=d[p]+a[p,i]; if not ok then pre[i]:=p; end; end;end;beginassign(input,‘rblock.in‘);reset(input);assign(output,‘rblock.out‘);rewrite(output); fillchar(pre,sizeof(pre),0); read(n,m); for j:=1 to m do begin read(a1,b1,l); if (l<a[a1,b1]) or (a[a1,b1]=0) then begin a[a1,b1]:=l; a[b1,a1]:=l; end; end; dijkstra(1); ok:=true; x:=d[n]; k:=n;repeat a[k,pre[k]]:=2*a[k,pre[k]]; a[pre[k],k]:=a[k,pre[k]]; dijkstra(1); if d[n]>y then y:=d[n]; a[k,pre[k]]:=a[k,pre[k]] div 2; a[pre[k],k]:=a[k,pre[k]]; k:=pre[k];until k=0;writeln(y-x);close(input);close(output);end.
USACO 2014 FEB 银组