#29167: 解題方向


NADPH39 (NADPH39)

學校 : 國立中興大學
編號 : 180361
來源 : [211.21.205.196]
最後登入時間 :
2022-02-12 11:41:45
a224. 明明愛明明 | From: [39.9.126.241] | 發表日期 : 2022-02-03 00:32

1. 題意理解:

    唯有當隨機排列( 「不是單純平移」!! )完成時,

    順著讀與反著讀皆為相同者,方謂之為「迴文字串」;

 

   < case1 > : 原字串為 " ababa " , 明顯便可看出順著讀與反著讀皆為相同。

 

   < case2 > : 原字串為  " aaab " , 其他三種調整後的型態為 "aaba" 、 "abaa" 、 "baaa" ,

                     注意如果誤認因為最後一者反著讀,會跟原字串一致,便判定原字串為迴文,

             此係錯誤而不符定義的 ! 

 

               正確的解讀是將這四個字串「自己」順著反著念 ,

                             結果發現此四者( 4! / (3!*1!) )都不會前後一致,

                             因此判定原字串 "aaab" 為「非迴文字串」。

 

 

2. 字串的奇偶數:(參見 https://kknews.cc/zh-tw/tech/ngl4ae8.html )

    明顯地,「回文」與否牽涉到「對稱性」,即「字串的長度」與「字母個數之奇偶」;  合法情況歸納如下 : 

           

           (1)  字串長度為0。

 

   (2)  字串長度是偶數,每個字母都存在偶數個。

 

   (3)  字串長度是奇數,除了最中間的那個字符出現奇數次以外,其他字母都必須出現偶數次。

 >>>  即「有且只有」一個字母,其個數為奇數個 !

 

 
 
ZeroJudge Forum