当前位置:首页 >> IT/计算机 >>

Time Travel 解题报告


=====文件名:Time Travel 解题报告.pas===== 《Time Travel》解题报告 [题目描述] Farmer John has purchased an Acme Time Machine. He can now travel forward in time normally (without using the machine) or else jump

back to an arbitrary point in the past, at which point time will start to go forward again, but potentially with events unfolding in a new, different way. FJ can never travel forward in time in his time machine. FJ wants to raise the best possible cow herd, so he is going to try several different ideas, keeping track of various statistics of his cow herd through different possible time and event paths. One statistic FJ cares about is the ID number of the cow he has had for the shortest period of time. Please help him out by writing a program to keep track of his herd and, after each command, reporting the ID of the most recently acquired cow of the cows he owns (or -1 if he has no cows). FJ has a set of N (1 ≤ N ≤ 80,000) queries Qi, conveniently numbered 1..N, which represent consecutive updates from the point of view of FJ's personal timeline. Each query is a single line of input. The line begins with a single character c (one of 'a', 's', or 't'). If c = 'a' or c = 't', then c is followed by a space and an integer K (1 ≤ K ≤ 1,000,000). * If c = 'a', then FJ acquires a cow with ID K; add the cow to the herd. * If c = 's', then FJ sold his most recently acquired cow (it is guaranteed that FJ will have at least one cow whenever this type of query appears); remove the cow from the herd. * If c = 't', then FJ traveled back in time to just before the K-th query. Note that this means that FJ can potentially travel between parallel time paths (see sample input for clarification). Revert to the herd that was present just before query K. By way of example, consider a series of 12 queries, shown below along with the cow name list and the resulting output for each query. Q# Query Owned Cows Output Comments 1 a 5 -> [5] => 5 Add a new cow with ID 5

2 a 3 -> [5,3] => 3 Add a new cow with ID 3 3 a 7 -> [5,3,7] => 7 Add a new cow with ID 7 4 s -> [5,3] => 3 Sell recent cow 7 5 t 2 -> [5] => 5 Revert time to before query 2 6 a 2 -> [5,2] => 2 Add a new cow with ID 2 7 t 4 -> [5,3,7] => 7 Revert time to before query 4 8 a 4 -> [5,3,7,4] => 4 Add a new cow with ID 4 9 s -> [5,3,7] => 7 Sell recent cow 4 10 t 7 -> [5,2] => 2 Revert time to before query 7 11 s -> [5] => 5 Sell recent cow 2 12 s -> [] => -1 Sell recent cow 5 Input * Line 1: A single integer: N * Lines 2..N+1: Line i+1: query Qi Output * Lines 1..N: Line i: The ID of the most recently purchased cow after query i takes effect (-1 if no cows are owned). Sample Input 12 a5 a3 a7 s t2 a2 t4 a4 s t7 s s Sample Output 5 3 7 3 5 2 7

4 7 2 5 -1 [思路] 纯模拟的思路: 开一个巨大无比的数组,把每一步都记录下来。 哈哈~!这样,想跳就跳,想删除就删除~! 就是……空间消耗巨大…… 估计一下 80000×80000 的 longint 数组的大小…… 另外小小重复一下:指定内存:128M…… 先不管那么多,敲出来再说 [程序] { ID: jinyu121 PROG: Time Travel LANG: PASCAL } const filename='ttravel'; inf=filename+'.in'; ouf=filename+'.out'; var i,k:longint; n:longint; a:array[0..5000,-1..5000] of longint; //每一行的 0 是容错用的,-1 是记录当前有多少个数字(相当于 指针) t:char; procedure cza;//操作 a:添加数据 var x,j:longint; begin readln(x); for j:=-1 to a[i-1,-1] do a[i,j]:=a[i-1,j]; inc(a[i,-1]);a[i,a[i,-1]]:=x;//把新的数字加进去 writeln(x); end; procedure czt;//操作 t:回到某一操作之前 var x,j:longint;

begin readln(x); for j:=-1 to a[x-1,-1] do a[i,j]:=a[x-1,j]; writeln(a[i,a[i,-1]]); end; procedure czs;//操作 s:删除最后一个数 var j:longint; begin readln(t); for j:=-1 to a[i-1,-1] do a[i,j]:=a[i-1,j]; a[i,a[i-1,-1]]:=0; dec(a[i,-1]); writeln(a[i,a[i,-1]]); end; begin assign(input,inf);reset(input); assign(output,ouf);rewrite(output); a[0,0]:=-1; readln(n); for i:=1 to n do //i 是当前的操作序号,永远递增 begin read(t); case t of 'a':cza;//插入数字 't':czt;//回到第 n 步操作之前 's':czs;//删除最后一个 end; end; close(input); close(output); end. [运行结果] A 掉 1 个点,其他要么是错误答案,要么是 101:内存访问出错。 肯定的,我开的才 2000×2000 的,用 80000 的数据,绝对出错 [更改思路] 经过以一晚上的推理,终于得出 3 组状态转移方程……^……^…… 用动态规划的思想。 开一个数组 C,存放每部操作后的“最后一头牛”。 再开一个数组 F,存放“这一步是由哪一步推过来的” 所以

添加: read(x), c[i]=x, f[i]=i-1,添加数肯定是从紧挨着的前一个状态推过来的 跳转: read(x), c[i]=c[x-1],因为要找“跳到这步的前一步的数” f[i]=f[x-1],理由同上 删除: c[i]:=c[f[i-1]],没有理由。 f[i]:=f[f[i-1]],没有理由。 按照这样的思路,举个例子 a 10 a 20 t1 a 40 s 然后看看我们的数组里面都存了点什么 操作序号 0 1 2 3 4 5 操作命令 a 10 a 20 t 1 a 40 s 数组 C -1 10 20 -1 40 -1 数组 F -1 0 1 0 3 0 这样下来,80000 的数据时间复杂度就可以是 O(n)了。 [程序] { ID: jinyu121 PROG: Time Travel LANG: PASCAL } const filename='ttravel'; inf=filename+'.in'; ouf=filename+'.out'; var i,k,n:longint; t:char; c,f:array[0..80000] of longint; //C:最后一头牛是几号,F:从 那个状态推过来的 procedure cza; //操作 a:添加数据

var x:longint; begin readln(x); //把数字读进去 //赋值 c[i]:=x; f[i]:=i-1; //记录从哪里推过来 writeln(c[i]); end; procedure czt; //操作 t:回到某一操作之前 var x:longint; begin //要跳到哪里 readln(x); c[i]:=c[x-1]; //把以前的数字找出来 f[i]:=f[x-1]; //记录从哪里推过来 writeln(c[i]); end; procedure czs; //操作 s:删除最后一个数 begin readln; c[i]:=c[f[i-1]]; f[i]:=f[f[i-1]]; writeln(c[i]); end; begin assign(input,inf);reset(input); assign(output,ouf);rewrite(output); fillchar(c,sizeof(c),0); fillchar(f,sizeof(f),0); c[0]:=-1; f[0]:=-1; readln(n); for i:=1 to n do begin read(t); case t of 'a':cza;//插入数字 't':czt;//回到第 n 步操作之前 's':czs;//删除最后一个 end; end; close(input); close(output);

end. [运行结果] AC,不超时,不爆内存。


相关文章:
更多相关标签: