[NOIP2016 提高組] 玩具謎題 題目背景 NOIP2016 提高組 D1T1 題目描述 小南有一套可愛的玩具小人，它們各有不同的職業。 有一天，這些玩具小人把小南的眼鏡藏了起來。小南發現玩具小人們圍成了一個圈，它們有的面朝圈內，有的面朝圈外。如下圖： 這時 singer 告訴小南一個謎題：“ ...
[NOIP2016 提高組] 玩具謎題
題目背景
NOIP2016 提高組 D1T1
題目描述
小南有一套可愛的玩具小人，它們各有不同的職業。
有一天，這些玩具小人把小南的眼鏡藏了起來。小南發現玩具小人們圍成了一個圈，它們有的面朝圈內，有的面朝圈外。如下圖：
這時 singer 告訴小南一個謎題：“眼鏡藏在我左數第 3 個玩具小人的右數第 1 個玩具小人的左數第 2 個玩具小人那裡。”
小南發現，這個謎題中玩具小人的朝向非常關鍵，因為朝內和朝外的玩具小人的左右方向是相反的：面朝圈內的玩具小人，它的左邊是順時針方向，右邊是逆時針方向；而面向圈外的玩具小人，它的左邊是逆時針方向，右邊是順時針方向。
小南一邊艱難地辨認著玩具小人，一邊數著:
singer 朝內，左數第 3 個是 archer。
archer 朝外，右數第 1 個是 thinker。
thinker 朝外，左數第 2 個是 writer。
所以眼鏡藏在 writer 這裡！
雖然成功找回了眼鏡，但小南並沒有放心。如果下次有更多的玩具小人藏他的眼鏡，或是謎題的長度更長，他可能就無法找到眼鏡了。所以小南希望你寫程式幫他解決類似的謎題。這樣的謎題具體可以描述為：
有 n 個玩具小人圍成一圈，已知它們的職業和朝向。現在第 1 個玩具小人告訴小南一個包含 m 條指令的謎題，其中第 z 條指令形如“向左數/右數第 s 個玩具小人”。你需要輸出依次數完這些指令後，到達的玩具小人的職業。
輸入格式
輸入的第一行包含兩個正整數 n,m，表示玩具小人的個數和指令的條數。
接下來 n 行，每行包含一個整數和一個字元串，以逆時針為順序給出每個玩具小人的朝向和職業。其中 0 表示朝向圈內，1表示朝向圈外。保證不會出現其他的數。字元串長度不超過 10 且僅由英文字母構成，字元串不為空，並且字元串兩兩不同。整數和字元串之間用一個空格隔開。
接下來 m 行，其中第 i 行包含兩個整數 ai,si，表示第 i 條指令。若 ai=0，表示向左數 si 個人；若 ai=1，表示向右數 si個人。 保證ai不會出現其他的數，1<=si<n。
輸出格式
輸出一個字元串，表示從第一個讀入的小人開始，依次數完 m 條指令後到達的小人的職業。
樣例 #1
樣例輸入 #1
7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2
樣例輸出 #1
writer
樣例 #2
樣例輸入 #2
10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4
樣例輸出 #2
y
提示
樣例 1 說明
這組數據就是【題目描述】中提到的例子。
子任務
子任務會給出部分測試數據的特點。如果你在解決題目中遇到了困難，可以嘗試只解決一部分測試數據。
每個測試點的數據規模及特點如下表:
思路：
這題題目敘述特別長！我們應該如何去思考呢？——首先，我們可以通讀題乾，發現題目大致只分為了四種情況：
- 當前這個人面朝內，向左數若幹個人
- 當前這個人面朝內，向右數若幹個人
- 當前這個人面朝外，向左數若幹個人
- 當前這個人面朝內，向右數若幹個人
其實我們認真思考一下，四種情況可以演變為兩種情況！——1、4為一組，2、3為一組。當它們朝向不同並且向左數和向右數相反時，它們所達到的效果是一樣的！
枚舉所有情況
經過上面的分析，我們其實可以直接枚舉完當前所有的情況，不過我們還有一個難題，就是如何構成一個環呢？？————在數組中，我們想在物理意義上構成一個環，我們可以採取取模運算！，這樣可以使得我們的數組在
物理意義上看起來類似環形！這樣我們就可以枚舉所有情況了，不過在此之前，我們還得計算一下數學關係,假設當前這個人處於now位置：
- 當人物面朝內時，向左數y個人，得到的結果應該是now = (now + n - y) % n;
- 當人物面朝內時，向右數y個人，得到的結果應該是now = (now + y) % n;
這個數學關係並不是太難想明白，我們只需要在草稿紙上多畫圖模擬一下就可以得出數學關係，那麼我們可以推出以下代碼：
int now = 0; // 當前所在位置
while (m--) {
cin >> x >> y; // x 為方向（0 表示左，1 表示右），y 為步數
// 判斷當前人物的朝向，並據此移動
if (a[now].num == 0) { // 面朝圈內
if (x == 0) { // 左數（順時針）
now = (now + n - y) % n;
}
else { // 右數（逆時針）
now = (now + y) % n;
}
}
else { // 面朝圈外
if (x == 0) { // 左數（逆時針）
now = (now + y) % n;
}
else { // 右數（順時針）
now = (now + n - y) % n;
}
}
}
cout << a[now].name << endl; // 輸出最終所在位置的人物名字
程式最終的AC代碼如下：
#include <iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10;
struct person {
int num; // 0 表示面朝圈內，1 表示面朝圈外
string name;
} a[N];
int n, m, x, y;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i].num >> a[i].name;
}
int now = 0; // 當前所在位置
while (m--) {
cin >> x >> y; // x 為方向（0 表示左，1 表示右），y 為步數
// 判斷當前人物的朝向，並據此移動
if (a[now].num == 0) { // 面朝圈內
if (x == 0) { // 左數（順時針）
now = (now + n - y) % n;
}
else { // 右數（逆時針）
now = (now + y) % n;
}
}
else { // 面朝圈外
if (x == 0) { // 左數（逆時針）
now = (now + y) % n;
}
else { // 右數（順時針）
now = (now + n - y) % n;
}
}
}
cout << a[now].name << endl; // 輸出最終所在位置的人物名字
return 0;
}
