Re: [問題] ICPC 6015

[seanwu (sean)]

※ 引述《lubrige (lubrige)》之銘言：
: 題目: http://ppt.cc/Aogu
: 給予整數 N, R, Q，求一最大的正整數 M，使得
: (1) 將 N 和 M 寫成十進位表示時，M 是 N 的 subsequence
: (2) M 除 Q 會餘 R
: 其中 1 <= N < 10^1000, 0 <= R < Q <= 1000
: 目前的做法是
: 定義狀態 f[i][j]，表示從 N 的最高位開始，考慮過前 i 個數字是否選進 M，且
: 餘 j 的情況時 M 的最大長度 (暫不考慮 value 大小)，其中若為走不到的狀態則填-1
: 轉移為 (d(k) 為 k 從最高位下來第 k 個數字， zero base)
:               / f[i - 1][j]
: f[i][j] = max |
:               \ f[i - 1][j'] + 1, j = (10 * j' + d(i - 1)) % Q,
:                                        if f[i - 1][j'] != 0 or d(i - 1) != 0
: boundary condition:
: 1. f[0][0] = 0
: 2. f[0][i] = -1, for 0 < i < Q

上面長度 f[i][j] 的計算是正確的，沒有問題

: 最大長度的表填完之後，再從 N 的最低位做回來，並且另外開一張表 g[i][j]，
: 記到 f[i][j] 這格所形成的最長 subsequence，最高位數字是多少。

有點看不太懂 "f[i][j] 這格所形成的最長 subsequence" 是指哪一段 sequence

根據你的遞迴式，腦補 g[i][j] 的意思是(?):

    選擇 M 的第 f[i][j] 個數字 (zero base) 最大可行值是 g[i][j]

    並且，這個值是從 d[i-1]~d[n-1] 選來的，

    且 M 的前 i-1 個位模 Q 的餘數是 j


: 對於不是 -1 的格子，取下面裏比較大的數字 (這部份用 buttom up 來說)：
: 1. g[i + 1][j], if f[i + 1][j] == f[i][j]
: 2. d(i), if f[i + 1][j'] == f[i][j] + 1, j' = (10 * j + d(i)) % Q

在算出 g[i][j] 後，應該是要再從高位找下來?

那這邊的找法，應該是從 i=j=0 開始，

    如果 g[i][j] 這格是 case 1. 就 i++; 看下一格就好

    如果是 case 2.， 輸出 g[i][j]; j=(j*10+g[i][j])%Q; i++;

不知道原 po 的做法是不是這樣? 如果是的話就要先判 case 2.

因為數字一樣時先取走一定比較好，反過來雖然之後還是能拿到一樣的數字

但可能會導至之後可以選的數字變小


例如 881 4 7 這個測資，算出 f[][], g[][] 應該是這樣

     f   0 1 2 3 4 5 6
     0   0 * * * * * *
     1   0 1 * * * * *
     2   * 1 * * 2 * *
     3   * * * * 2 * *

     g   0 1 2 3 4 5 6
     0   8 * * * * * *
     1   8 8 * * * * *
     2   * 1 * * X * *

 g[0][0] 的 8 是來自 g[1][0] 或 d[0] (f[1][8%7]==f[0][0]+1, case 2.) 都行

 不過這裡要選 case 2. (i,j)=(0,0)=>(1,1)=>(2,4)=>(3,4)
                                 8      8      X

 選 case 1. 的話， (i,j)=(0,0)=>(1,0)=>(2,1)=>(3,4)
                              X      8      1


: 另外因為這部份倒過來做，所以為了避免抓到不是從 f[length(N)][R] 填回來的數字，
: 上面的計算還考慮是不是從 f[length(N)][R] 填回來的，如果不是的話一樣不考慮
: g[i + 1][j] 或 d(i)，這部份再記一張來解決。
: 不過答案不對，想請問一下有沒有什麼沒有考慮到地方，先謝謝大家 0w0/

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.194
※ 編輯: seanwu          來自: 140.112.4.194        (03/17 18:26)
推 lubrige:抱歉 g[i][j] 那段寫得不好  不過我們想的應該是同一件事
→ lubrige:就是在 dag 上找字典序最大或最小那樣
→ lubrige:然後兩個 case 都存在且平手的話也是抓 case 2 沒問題
→ lubrige:最後再從最高位輸出回來  我覺得應該是哪邊寫爛了
→ lubrige:不過一直看不太出來 QwQ
→ seanwu:方便給source code嗎XD 我想看一下
推 lubrige:f 的第 0 個 column 似乎是整排的 0? 雖然應該是不影響
→ seanwu:嗯對，我標*的位置從g[|N|][R]走回來走不到的點
推 lubrige:http://codepad.org/VwCMbCgU 對不起這樣麻煩 見笑了 QwQ
→ seanwu:第73行的p[i][j][1]有可能是壞的 (如果case 2沒有成功)
→ seanwu:要先檢查 p[i][j] 有沒有填過 (p[i][j][0]==rnd_cnt)
→ seanwu:沒有的話，不用比p[i][j][1],p[i+1][j][1]，直接做74行
→ seanwu:if(p[i][j][0]!=rnd_cnt || p[i][j][1]<p[i + 1][j][1])
→ seanwu:    (line 74)
→ seanwu:p[i][j][0] = rnd_cnt;
推 lubrige:嗯嗯  感謝幫忙  不過還沒有想透什麼情況下這句會出包
→ lubrige:我直覺上令為 -1 應該可以避掉 case 2 的失敗
→ lubrige:可是這樣看起來結果並不是這樣
→ seanwu:我也不太清楚XD 不過我測 1101 1 6 你會印 11 這樣
→ seanwu:可能要 trace 一下發生什麼事
推 lubrige:啊啊  似乎是因為我把 back tracking 的 pointer 也放在
→ lubrige:line 74 裏面  這樣在 case 2 失敗  而且 i + 1 到 L
→ lubrige:之間都沒有選數字的話  會因為同為 -1 使 p[i][j][3]
→ lubrige:沒有被正確的 assign 到  最後在印答案的時候餘數就亂跳
→ lubrige:實際上應該是要 re 的  因為 p[i][j][3] 在這種情況下
→ lubrige:都會是 -1 XDD
推 lubrige:這筆測資太重要了  非常感謝 0 w0b