Description
约翰得到了一台时光机，他可以用这台机器回到过去（但不能到未来），改变他家的牛群。约翰 打算依次进行 N 步操作，每步操作分为三种：
• 买入操作以 a 表示，后接一个参数 i，表示约翰新买了一头编号为 i 的奶牛，将其放入牛棚
• 卖出操作以 s 表示，表示约翰会将牛棚中最近买入的一头奶牛卖掉
• 时光倒流的操作以 t 表示，后接一个参数 k，表示约翰将发动时光机，牛棚将返回到第 k 步操 作之前的状态
请帮助约翰记录牛棚里的奶牛信息，每当执行完一步操作后，输出目前在牛棚里的最近买入的奶牛， 如果当时牛棚里没有奶牛了，输出 −1。
Input Format
第一行：单个整数 N ，1 ≤ N ≤ 80000
• 第二行到 N + 1 行：每行代表一步操作，开头有一个小写字母
– 如果是 a，表示买入操作，后接一个参数 i，1 ≤ i ≤ 1000000
– 如果是 s，表示卖出操作
– 如果是 t，表示时光倒流的操作操作，后接一个参数 k，若这是第 i + 1 行，则 1 ≤ k ≤ i
Output Format
• 第一行到第 N 行：第 i 行有一个整数，表示在第 i 步操作后，在牛棚里最近买入的奶牛，如果 当时牛棚里没有奶牛，输出 −1
Sample Input
12a 5a 3a 7st 2a 2t 4a 4st 7ss
Sample Output
53735274725-1
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 这道题如果没有t操作就是模拟出栈入栈过程，但现在却多了一个时光倒流操作，问题明显没有那么简单了。你不能记录每个时刻的操作然后真的模拟时光回溯。 但可以发现每次查询只关注栈顶元素，所以我们可以采用链表来实现时光回溯，开两个数组q[i]表示i时刻栈顶元素，s[i]表示i时刻由s[i]时刻过来的。 最后附上代码。
#include#include #include #include #include using namespace std;int q[80001];int s[800001];int n;char c[10];int x;int main(){ scanf("%d",&n); q[0]=-1; for(int i=1;i<=n;i++) { scanf("%s",c); if(c[0]=='a') { scanf("%d",&x); q[i]=x; s[i]=i-1; } if(c[0]=='s') { q[i]=q[s[i-1]]; s[i]=s[s[i-1]]; } if(c[0]=='t') { scanf("%d",&x); q[i]=q[x-1]; s[i]=s[x-1]; } printf("%d\n",q[i]); }}