發表新討論
#34900: 想確認題目的意思


kaeteyaruyo@gmail.com (kinoe_T)

學校 : 國立成功大學
編號 : 81196
來源 : [140.113.136.221]
最後登入時間 ：
2024-01-31 16:39:28
e828. 3.猴子打字遊戲 (Typing) -- 2019年10月TOI練習賽潛力組 | From: [163.32.57.133] | 發表日期 : 2023-04-25 10:41

想確認本題當中的新增、刪除是否都只能在字串的尾端進行？就是不可以在中間插入一個字，然後把後面的字都往後推，也不可以在中間刪掉一個字，所有的字都往前移對嗎？

我的想法是位移字串比較距離，假設猴子打的字串是 xxx，目標字串是 yyyyy，那麼就是看：

xxx
  yyyyy

 xxx
  yyyyy

  xxx
  yyyyy

   xxx
  yyyyy

    xxx
  yyyyy

     xxx
  yyyyy

      xxx
  yyyyy

       xxx
  yyyyy

哪一種的距離最短，距離的計算方式是：重疊部份前方有 i 個字，就 +2i；重疊部份有 j 個字不一樣，就 +3j；重疊部份後方有 k 個字，就 +2k。

算出來之後 index 大概都是對的，但距離總是比正確答案還要多。不知道是不是我對題目中距離的定義有理解錯誤？

 
#45164: Re: 想確認題目的意思


kk20180820@gmail.com (Wayne Yang)

學校 : 國立鳳山高級中學
編號 : 172018
來源 : [39.9.35.5]
最後登入時間 ：
2025-01-17 22:02:10
e828. 3.猴子打字遊戲 (Typing) -- 2019年10月TOI練習賽潛力組 | From: [49.159.255.92] | 發表日期 : 2025-01-19 00:32

想確認本題當中的新增、刪除是否都只能在字串的尾端進行？就是不可以在中間插入一個字，然後把後面的字都往後推，也不可以在中間刪掉一個字，所有的字都往前移對嗎？

我的想法是位移字串比較距離，假設猴子打的字串是 xxx，目標字串是 yyyyy，那麼就是看：

xxx
  yyyyy

 xxx
  yyyyy

  xxx
  yyyyy

   xxx
  yyyyy

    xxx
  yyyyy

     xxx
  yyyyy

      xxx
  yyyyy

       xxx
  yyyyy

哪一種的距離最短，距離的計算方式是：重疊部份前方有 i 個字，就 +2i；重疊部份有 j 個字不一樣，就 +3j；重疊部份後方有 k 個字，就 +2k。

算出來之後 index 大概都是對的，但距離總是比正確答案還要多。不知道是不是我對題目中距離的定義有理解錯誤？

有考慮到插入和刪除中間字元這兩功能嗎?

試試

bab

bacb

 
#45180: Re: 想確認題目的意思


kaeteyaruyo@gmail.com (kinoe_T)

學校 : 國立成功大學
編號 : 81196
來源 : [140.113.136.221]
最後登入時間 ：
2024-01-31 16:39:28
e828. 3.猴子打字遊戲 (Typing) -- 2019年10月TOI練習賽潛力組 | From: [163.32.57.142] | 發表日期 : 2025-01-21 14:22

想確認本題當中的新增、刪除是否都只能在字串的尾端進行？就是不可以在中間插入一個字，然後把後面的字都往後推，也不可以在中間刪掉一個字，所有的字都往前移對嗎？

我的想法是位移字串比較距離，假設猴子打的字串是 xxx，目標字串是 yyyyy，那麼就是看：

xxx
  yyyyy

 xxx
  yyyyy

  xxx
  yyyyy

   xxx
  yyyyy

    xxx
  yyyyy

     xxx
  yyyyy

      xxx
  yyyyy

       xxx
  yyyyy

哪一種的距離最短，距離的計算方式是：重疊部份前方有 i 個字，就 +2i；重疊部份有 j 個字不一樣，就 +3j；重疊部份後方有 k 個字，就 +2k。

算出來之後 index 大概都是對的，但距離總是比正確答案還要多。不知道是不是我對題目中距離的定義有理解錯誤？

有考慮到插入和刪除中間字元這兩功能嗎?

試試

bab

bacb

通過了！所以果然是我沒有考慮到中間插入和刪除的狀況，感謝回應~

 
ZeroJudge Forum