切換
舊版
前往
大廳
主題

ZeroJudge - e596: 12335 - Lexicographic Order　解題心得

Not In My Back Yard | 2020-01-10 15:19:53 | 巴幣 0 | 人氣 190
題目連結：
題目大意：
給定一正整數 T （T ≦ 5000），代表有 T 筆測試資料，每筆佔一列。每列給定一字串 s 以及一正整數 k （1 ≦ n ≦ 20，n 為字串 s 的長度且1 ≦ k ≦ n!），代表字串 s 是字典中的照字典序排的第 k 個字。（雖然 s 的符號只會是小寫字母，但這裡的字典序不是原本英文字母的字典序）

求排在字典裡的第一個字為何？

範例輸入：
3
bdac 11
abcd 5
hjbrl 120
範例輸出：
Case 1: abcd
Case 2: acdb
Case 3: lrbjh
解題思維：
用與此題的過程恰好相反的程序——原本是求第 k 個排列，現在是給定第 k 個排列求第一個排列。

以範例測資 bdac 11 為例：
可以看到 11 ＞ 6 ＝ 3! ，因此前面已經先排完一輪長度為 3 的字典序了（即順序第二～順序第四的符號之排列）。所以，可以推導出 b 為該字典第二順位的符號。順便將 11 減去 6 ，以便等等做判斷。

接著對於剩下的三個符號 dac 其序位為 5，而 5 ＞ 4 ＝ 2 × 2! ，代表剩下的三個符號中已經排到要以剩下的符號中第三順位（即原本的第四順位）為開頭。因此推導出 d 為第四順位。並將 5 減去 4 。

接著剩下 ac，而該排列序號為 1 ，因此是第一個排列。所以可以推得 a 為第一順位、 c 為三順位。

因此，所求的第一個排列為 abcd 。


其他的情況同理。都是一位一位慢慢看，去推出哪個符號應該是第幾順位。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

經典不敗

看更多

更多創作

追蹤 創作集
其他創作
作品資料夾