一、卡牌游戲

1. 審題

題目描述

$A,B,C$ 三人在玩一個卡牌游戲，規則如下：
游戲開始時，$3$ 人分別會得到若干張手牌, 每張牌上寫著 'a'，'b'，'c' 中某一個字母。手牌的順序嚴格按照輸入順序排列，不允許改變順序。
游戲從 $A$ 開始出牌。如果輪到某人的回合，且這個人手上有牌，他必須出自己手上的第 $1$ 張牌，之后輪到這張牌的寫著的字母同名的人出牌（例如出 'a' 牌之后就輪到 $A$ 的回合）。
如果輪到某人的回合，且這個人手沒有牌，這個人就是贏家。
三人的起始手牌以字符串 $S_A$，$S_B$，$S_C$ ?的形式給出，字符串開頭是第1張牌。

輸入描述

三行，分別是字符串 $S_A$，$S_B$，$S_C$ ?。

輸出描述

輸出勝出者

樣例1

輸入

aca
accc
ca

輸出

A

樣例2

輸入

abcb
aacc
bbcc

輸出

C

提示

所有字符長度 $<100$。

2. 思路

2.1 暴力模擬

首先，我們應該想到的是用數組或者 string 存儲每個人手上的牌。為了更方便，我們用 string 存儲。

然后，我們就要開始模擬游戲的過程了。我們可以分析一下樣例 $1$ 的游戲過程：

• $A$ 出牌 'a'，之后輪到 $A$
• $A$ 出牌 'c'，之后輪到 $C$
• $C$ 出牌 'c'，之后輪到 $C$
• $C$ 出牌 'a'，之后輪到 $A$
• $A$ 出牌 'a'，之后輪到 $A$

此時 $A$ 手上已經沒有牌了，$A$ 是贏家。

最后，我們寫出初始的代碼。

2.2 技巧模擬

暴力模擬得到 $TLE$ 的結果，我們嘗試換一種思路作答。

我們要定義六個變量，分別是三個人手上的牌和三個人出牌的下標。

每次出牌的時候，將出牌的下標都 $+1$，表示應該出哪一張牌，這樣下一次出牌可以直接寫 ?[l?]。

3. 參考答案

3.1 初試

#include <iostream>
#include <string>
using namespace std;string card[5];
char now;
int player;int main()
{// 輸入每個人手上的牌cin >> card[1] >> card[2] >> card[3];// 模擬打牌while (card[1] != "" && card[2] != "" && card[3] != ""){if (now == 'a'){player = 1;}if (now == 'b'){player = 2;}if (now == 'c'){player = 3;}card[player].erase(0, 1);now = card[player][0];}// 輸出最后一個玩家cout << toupper(now);return 0;
}

結果：$TLE$（$CPU?Time?Limit?Exceeded$）

3.2 死循環思路

#include <iostream>
#include <string>
using namespace std;string a, b, c;
int la = -1, lb = -1, lc = -1;int main()
{// 輸入每個人手上的牌cin >> a >> b >> c;// 模擬打牌la++;char card = c[la];while (true){if (card == 'a'){if (la + 1 == a.length()) // A沒有牌了{cout << "A";break;}la++;card = a[la];}else if (card == 'b'){if (lb + 1 == b.length()) // B沒有牌了{cout << "B";break;}lb++;card = b[lb];}else{if (lc + 1 == c.length()) // C沒有牌了{cout << "C";break;}lc++;card = c[lc];}}return 0;
}

結果：

AC: 90%

WA: 10%

錯誤樣例：

二、移動距離

題目描述

$X$ 星球居民小區的樓房全是一樣的，并且按矩陣樣式排列。其樓房的編號為 $1,2,3,?$。當排滿一行時，從下一行相鄰的樓往反方向排號。
比如：當小區排號寬度為6時，開始情形如下：

1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 .....

我們的問題是：已知了兩個樓號 $m$ 和 $n$，需要求出它們之間的最短移動距離。（不能斜線方向移動）

輸入描述

輸入為 $3$ 個整數 $w,m,n$，空格分開，都在 $1$ 到 $10^4$ 范圍內。$w$ 為排號寬度 $m,n$ 為待計算的樓號。

輸出描述

要求輸出一個整數，表示 $m$ 與 $n$ 兩樓間最短移動距離。

樣例1

輸入

6 8 2

輸出

4

二、思路

$w=6$ 求 $m?n$的最短移動距離，在數學中也就是求 $m$ 和 $n$ 的曼哈頓距離。

也就是說，我們要將 $m$ 的 $x_1$、$y_1$ 求出，并將 $n$ 的 $x_2$、$y_2$ 求出，再做一次運算：

$$ans=|x_1?x_2|+|y_1?y_2|$$

求行方法：

if (m % w == 0)
{x = m / w;
}
else
{x = m / w + 1;
}

求列方法：

if (x % 2 == 0) // 偶數行 右→左排列
{if (m % w == 0){y = 1;}else{y = w - m % w + 1;}
}
else // 奇數行 左→右排列
{if (m % w == 0){y = w;}else{y = m % w;}
}

3. 參考答案

#include <iostream>
#include <cmath>
using namespace std;int findx(int w, int m)
{int x;if (m % w == 0){x = m / w;}else{x = m / w + 1;}return x;
}int findy(int w, int m, int x)
{int y;if (x % 2 == 0){if (m % w == 0){y = 1;}else{y = w - m % w + 1;}}else{if (m % w == 0){y = w;}else{y = m % w;}}return y;
}int main()
{int w, m, n;int x1, y1, x2, y2;cin >> w >> m >> n;x1 = findx(w, m);x2 = findx(w, n);y1 = findy(w, m, x1);y2 = findy(w, n, x2);cout << abs(x1-x2) + abs(y1-y2);return 0;
}