主題

ZeroJudge - f647: 撲克牌 解題心得

Not In My Back Yard | 2021-03-18 22:40:52 | 巴幣 2 | 人氣 53

題目連結:


題目大意:
現在有一副撲克牌有 52 張牌,其由上至下編號為 1 ~ N 且花色為 SA、S2、……、HA、H2、……、HK、DA、D2、……、DK、FA、F2、……、FK(總之就是黑桃、愛心、方塊以及不知道為啥用 F 代表的梅花(通常會是 C)各自的 1 ~ 10 、 J 、 Q 、 K)。

方便起見,以下已經用陣列表示撲克牌(以 C/C++ 之格式):
string A[53]={
    "XX",
    "SA","S2","S3","S4","S5","S6","S7","S8","S9","S10","SJ","SQ","SK",
    "HA","H2","H3","H4","H5","H6","H7","H8","H9","H10","HJ","HQ","HK",
    "DA","D2","D3","D4","D5","D6","D7","D8","D9","D10","DJ","DQ","DK",
    "FA","F2","F3","F4","F5","F6","F7","F8","F9","F10","FJ","FQ","FK"
};

輸入第一列給定一正整數 N (N ≦ 100000),代表有 N 個指令。接著有 N 列輸入,每列給定一個指令,指令的種類如下:
1 a b,代表從上面數的第 a 張牌(含)到第 b 張牌(含)移到牌組的最上面;
2 a b,代表從上面數的第 a 張牌(含)到第 b 張牌(含)移到牌組的最下面;
3 k   ,代表牌組最下面 k 張牌移到牌組最上面;
4 k   ,代表牌組最上面 k 張牌移到牌組最下面;
其中 1 ≦ a ≦ b ≦ 52 , 1 ≦ k ≦ 52。

試問 N 個指令都執行完後,牌組最上面五張牌為何?



範例輸入:
範例輸入 #1
3
1 14 14
1 27 27
1 40 40

範例輸入 #2
10
4 10
1 17 18
2 2 29
2 3 14
2 4 16
1 40 40
1 4 4
1 5 5
1 4 4
1 5 5


範例輸出:
範例輸出 #1
FA DA HA SA S2

範例輸出 #2
FA DA HA SA S2


解題思維:
模擬即可。不過雖說如此,我們並不需要為了四種操作寫四種函式,題目給定的四種操作通通屬於同一種操作——即將指定的從上面數來第 L 張(含)~第 R 張(含)牌向牌組上方移動到位置 P。而我們定義該操作為 M(L, R, P)

因此,題目定義的四種操作可以轉換為以下:
1 a b,變為 M(a, b, 1),基本上沒什麼變;
2 a b,變為 M(b + 1, 52, a),因為 a ~ b 往下移到 52 等價於 b + 1 ~ 52 往上移到 a;
3 k   ,變為 M(52 - a + 1, 52, 1),基本上就是最下面 k 張牌的編號套用 1 a b 之寫法;
4 k   ,變為 M(k + 1, 52, 1),最上面 k 張牌移到最下面等價於下面 52 - k 張牌移到最上面。

因此我們只需要撰寫 M(L, R, P) 即可完成所有操作。不過如果直接使用字串進行交換會比較耗時,因此我們可以將原本的撲克牌(即題目給定的陣列 A)的編號 1 ~ 52 直接拿來進行移動或交換的動作,最後再根據最前面(上面)的編號即可找到最後最上面的五張牌為何。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作