前往
大廳
主題

ZeroJudge - c356: Justin 愛加密 解題心得

Not In My Back Yard | 2021-07-04 00:00:01 | 巴幣 110 | 人氣 233

題目連結:


題目大意:
輸入第一列給定一正整數 N(1 ≦ N ≦ 5000),代表接下來有第二列有著長度為 N × N 的密文。解密方式為將密文重新排列為 N 列 N 行的字元矩陣,然後取其主對角線(左上到右下)上的字元並輸出即是解密後的文字。

記憶體限制:16 MB。



範例輸入:
5
HDNOWEEIOWWELWDDWWLOPODWO


範例輸出:
HELLO


解題思維:
因為記憶體限制的緣故,使得我們不可能真的將整個密文存起來並重新排列(因為 N 可以到 5000,而 5000 × 5000 個字元約為 24 MB 的資料)。

因此我們可以觀察一下主對角線,發現每兩個相鄰的主對角線元素在原本的密文上將間隔 N 個字元。所以我們可以先輸出第一個字元,然後每隔 N 個字元之後再輸出一個,重複此步驟直到我們輸出了 N 個字元為止。此時輸出之內容即為解密後的文字。




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

創作回應

更多創作