題目連結:
題目大意:
輸入第一列給定一正整數 N(1 ≦ N ≦ 5000),代表接下來有第二列有著長度為 N × N 的密文。解密方式為將密文重新排列為 N 列 N 行的字元矩陣,然後取其主對角線(左上到右下)上的字元並輸出即是解密後的文字。
記憶體限制:16 MB。
範例輸入:
5
HDNOWEEIOWWELWDDWWLOPODWO
範例輸出:
HELLO
解題思維:
因為記憶體限制的緣故,使得我們不可能真的將整個密文存起來並重新排列(因為 N 可以到 5000,而 5000 × 5000 個字元約為 24 MB 的資料)。
因此我們可以觀察一下主對角線,發現每兩個相鄰的主對角線元素在原本的密文上將間隔 N 個字元。所以我們可以先輸出第一個字元,然後每隔 N 個字元之後再輸出一個,重複此步驟直到我們輸出了 N 個字元為止。此時輸出之內容即為解密後的文字。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。