【模拟】L2-4 哲哲打游戏 (25 分)【2021天梯赛】

你的名字 2023-01-17 07:54 180阅读 0赞

**n个剧情点，对每个剧情点有k种操作可以选择，进行操作可以跳到该数字所对应的剧情点；m个游戏操作，每次操作输入两个数字x，y，x==0跳到对应剧情点；x ==1，存档；x ==2，读取存档，跳到y对应的剧情点；最后输出每一次存档的剧情点和最后到达的剧情点。**

**vector二维数组a\[n+1\]，存放在每个剧情点进行对应操作可以跳到哪个剧情点；b\[n+1\]记录每次存档操作，方便进行读取存档；t代表每次操作时所在的剧情点，游戏默认从剧情点1开始，所以t初始化为1。**

注意：如果不加`std::ios::sync_with_stdio(false);`会超时

#include <iostream>
    #include <vector>
    using namespace std;
    int main() {
        
    	int n, m;
    	std::ios::sync_with_stdio(false);
    	cin >> n >> m;
    	vector<int> a[n+1];
    	for(int i = 1; i <= n; i++) {
        
    		int k;
    		cin >> k;
    		a[i].push_back(-1);    //因为剧情点从1开始，为方便以后操作，随便放进去一个数字，让下标从1开始
    		for(int j = 0; j < k; j++) {
        
    			int t;
    			cin >> t;
    			a[i].push_back(t);
    		}
    	}
    	int t = 1;
    	int b[n+1] = {
        0};
    	for(int i = 0; i < m; i++) {
        
    		int x, y;
    		cin >> x >> y;
    		if(x == 0) {
                  //跳到对应剧情点
    			t = a[t][y];
    		}
    		else if(x == 1) {
              //存档输出
    			cout << t << endl;
    			b[y] = t;
    		}
    		else if(x == 2) {
               //读取存档，跳到y对应的剧情点
    			t = b[y];
    		}
    	}
    	cout << t;
    }

**题目描述**  
哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！

为简化模型，我们不妨假设游戏有 N 个剧情点，通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行操作或者选择，到达不同的剧情点。

为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏操作，请你输出哲哲的游戏进度。

**输入格式：**  
输入第一行是两个正整数 N 和 M (1≤N,M≤10^5 )，表示总共有 N 个剧情点，哲哲有 M 个游戏操作。

接下来的 N 行，每行对应一个剧情点的发展设定。第 i 行的第一个数字是 Ki ，表示剧情点 i 通过一些操作或选择能去往下面 Ki 个剧情点；接下来有 Ki 个数字，第 k 个数字表示做第 k 个操作或选择可以去往的剧情点编号。

最后有 M 行，每行第一个数字是 0、1 或 2，分别表示：

0 表示哲哲做出了某个操作或选择，后面紧接着一个数字 j，表示哲哲在当前剧情点做出了第 j 个选择。我们保证哲哲的选择永远是合法的。  
1 表示哲哲进行了一次存档，后面紧接着是一个数字 j，表示存档放在了第 j 个档位上。  
2 表示哲哲进行了一次读取存档的操作，后面紧接着是一个数字 j，表示读取了放在第 j 个位置的存档。  
约定：所有操作或选择以及剧情点编号都从 1 号开始。存档的档位不超过 100 个，编号也从 1 开始。游戏默认从 1 号剧情点开始。总的选项数（即 ∑Ki ）不超过 106 。

**输出格式：**  
对于每个 1（即存档）操作，在一行中输出存档的剧情点编号。

最后一行输出哲哲最后到达的剧情点编号。

**输入样例：**

10 11
    3 2 3 4
    1 6
    3 4 7 5
    1 3
    1 9
    2 3 5
    3 1 8 5
    1 9
    2 8 10
    0
    1 1
    0 3
    0 1
    1 2
    0 2
    0 2
    2 2
    0 3
    0 1
    1 1
    0 2

**输出样例：**

1
    3
    9
    10

**样例解释：**  
简单给出样例中经过的剧情点顺序：

1 -> 4 -> 3 -> 7 -> 8 -> 3 -> 5 -> 9 -> 10。

档位 1 开始存的是 1 号剧情点；档位 2 存的是 3 号剧情点；档位 1 后来又存了 9 号剧情点。