#22796: 解法思路


es611543 (afa)

School : 基隆市私立二信高級中學
ID : 93767
IP address : [36.227.72.40]
Last Login :
2024-05-18 09:13:36
b547. 3.巧克力擺盒 -- 102學年度北基區北三區資訊學科能力競賽 | From: [118.167.31.3] | Post Date : 2020-10-02 18:09

口味值P:0,B:3,Y:6,?:{0,3,6}、 形狀值 S:0,C:1,T:2,?:{0,1,2}

每2個字元的 (口味值+形狀值)產生一個數字轉為字元, 每組位置關係可產生 3個字元

我建一個 map<string,int>rela 存 n 組(0~n-1)的所有可能字元,及對應的 關係組別值{關係狀態值}

   rela的 string 部份是3位0~9的字元,其值是 n 筆(0~n-1)關係的所有可能值, 

   rela的 int 部份是 n 組中哪幾組的 二進位 bit值 {我稱為關係狀態}

   假設由 第 i及第j個關係會產生這個 string則就是bit i,bit j皆on 的值

 

然後將 a="012345678"全排列,切三段 由 rela 找出的「關係狀態」bit OR 後是否n個bit全on

 

==============================舉例====================

4

3 B S Y ? ? C

2 B C Y T

3 P S ? ? Y C

3 ? S ? T Y ?

關係組編號為0~3

第0組可能的三個字元為"3{678}{147}"共8 (7重複),其關係狀態值為 2^0:1

  rela會存入{"361":1 , "364":1 , "367":1 , "371":1 , "374":1 , "381":1 , "384":1 , "387":1}

第1組可能的三個字元為 "{0123567}48" 及  "48{0123567}" 共14種,其關係狀態值為 2^1:2

  rela會存入 {"048":2 , "148":2 , "248":2 , "348":2 , "548":2 , "648":2 , "748":2 } 7種,

      以及{"480":2 , "481":2 , "482":2 , "483":2 , "485":2 , "486":2 , "487":2 } 7種, 共14種

第2組可能的三個字元為"0{1234568}7"共7種,其關係狀態值為 2^2:4

  rela會存入{"017":4 , "027":4 , "037":4 , "047":4 , "057":4 , "067":4 , "087":4 } 7種

第3組可能的三個字元為"{036}{258}{678}"共21種,其關係狀態值為 2^3:8

  rela會存入{"026":8 , "027":8 ,"028":8 ,  "056":8 , "057":8 , "058":8 , "086":8 , "087":8 } 8種

       以及 {"326":8 , "327":8 ,"328":8 ,  "356":8 , "357":8 , "358":8 , "386":8 , "387":8 } 8種

       以及 {"627":8 ,"628":8 ,  "657":8 , "658":8 , "687":8 } 5種   共 21種

但是存入 rela 中若已出現過的 「關係狀態」值需 bit OR:

  例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "027":12

     又第0組出現 "387":1 且 第3組再出現"387":8 需改狀態值為 "387":9

 

在 a的全排列 分成的三段,可以使在rela中找到的狀態值 bit OR 後等於 2^4-1(2^n-1):15 就是符合

例如 a="361482057" 第1段的"361":1、第2段的"482":2、第3段的"057":12 , 三段的 bit OR值為 15故符合

 
#26575: Re:解法思路


810416@fhsh.khc.edu.tw (Eric_hung)

School : 國立鳳新高級中學
ID : 118851
IP address : [140.116.118.9]
Last Login :
2022-11-09 15:13:56
b547. 3.巧克力擺盒 -- 102學年度北基區北三區資訊學科能力競賽 | From: [101.9.238.67] | Post Date : 2021-08-14 01:54

口味值P:0,B:3,Y:6,?:{0,3,6}、 形狀值 S:0,C:1,T:2,?:{0,1,2}

每2個字元的 (口味值+形狀值)產生一個數字轉為字元, 每組位置關係可產生 3個字元

我建一個 map<string,int>rela 存 n 組(0~n-1)的所有可能字元,及對應的 關係組別值{關係狀態值}

   rela的 string 部份是3位0~9的字元,其值是 n 筆(0~n-1)關係的所有可能值, 

   rela的 int 部份是 n 組中哪幾組的 二進位 bit值 {我稱為關係狀態}

   假設由 第 i及第j個關係會產生這個 string則就是bit i,bit j皆on 的值

 

然後將 a="012345678"全排列,切三段 由 rela 找出的「關係狀態」bit OR 後是否n個bit全on

 

==============================舉例====================

4

3 B S Y ? ? C

2 B C Y T

3 P S ? ? Y C

3 ? S ? T Y ?

關係組編號為0~3

第0組可能的三個字元為"3{678}{147}"共8 (7重複),其關係狀態值為 2^0:1

  rela會存入{"361":1 , "364":1 , "367":1 , "371":1 , "374":1 , "381":1 , "384":1 , "387":1}

第1組可能的三個字元為 "{0123567}48" 及  "48{0123567}" 共14種,其關係狀態值為 2^1:2

  rela會存入 {"048":2 , "148":2 , "248":2 , "348":2 , "548":2 , "648":2 , "748":2 } 7種,

      以及{"480":2 , "481":2 , "482":2 , "483":2 , "485":2 , "486":2 , "487":2 } 7種, 共14種

第2組可能的三個字元為"0{1234568}7"共7種,其關係狀態值為 2^2:4

  rela會存入{"017":4 , "027":4 , "037":4 , "047":4 , "057":4 , "067":4 , "087":4 } 7種

第3組可能的三個字元為"{036}{258}{678}"共21種,其關係狀態值為 2^3:8

  rela會存入{"026":8 , "027":8 ,"028":8 ,  "056":8 , "057":8 , "058":8 , "086":8 , "087":8 } 8種

       以及 {"326":8 , "327":8 ,"328":8 ,  "356":8 , "357":8 , "358":8 , "386":8 , "387":8 } 8種

       以及 {"627":8 ,"628":8 ,  "657":8 , "658":8 , "687":8 } 5種   共 21種

但是存入 rela 中若已出現過的 「關係狀態」值需 bit OR:

  例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "027":12

     又第0組出現 "387":1 且 第3組再出現"387":8 需改狀態值為 "387":9

 

在 a的全排列 分成的三段,可以使在rela中找到的狀態值 bit OR 後等於 2^4-1(2^n-1):15 就是符合

例如 a="361482057" 第1段的"361":1、第2段的"482":2、第3段的"057":12 , 三段的 bit OR值為 15故符合

首先先感謝一下樓上提供的idea,我再幫他補充一下

"例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "027":12"

這句話應該更正為

"例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "057":12"

此範例解為12

分別是

027361485

057248361

057361248

057361482

057482361

248057361

248361057

361027485

361027548

361057248

361057482

361248057

361482057

361485027

361548027

482057361

482361057

485027361

485361027

548027361

548361027

 

 
#26576: Re:解法思路


810416@fhsh.khc.edu.tw (Eric_hung)

School : 國立鳳新高級中學
ID : 118851
IP address : [140.116.118.9]
Last Login :
2022-11-09 15:13:56
b547. 3.巧克力擺盒 -- 102學年度北基區北三區資訊學科能力競賽 | From: [101.9.238.67] | Post Date : 2021-08-14 01:56

口味值P:0,B:3,Y:6,?:{0,3,6}、 形狀值 S:0,C:1,T:2,?:{0,1,2}

每2個字元的 (口味值+形狀值)產生一個數字轉為字元, 每組位置關係可產生 3個字元

我建一個 map<string,int>rela 存 n 組(0~n-1)的所有可能字元,及對應的 關係組別值{關係狀態值}

   rela的 string 部份是3位0~9的字元,其值是 n 筆(0~n-1)關係的所有可能值, 

   rela的 int 部份是 n 組中哪幾組的 二進位 bit值 {我稱為關係狀態}

   假設由 第 i及第j個關係會產生這個 string則就是bit i,bit j皆on 的值

 

然後將 a="012345678"全排列,切三段 由 rela 找出的「關係狀態」bit OR 後是否n個bit全on

 

==============================舉例====================

4

3 B S Y ? ? C

2 B C Y T

3 P S ? ? Y C

3 ? S ? T Y ?

關係組編號為0~3

第0組可能的三個字元為"3{678}{147}"共8 (7重複),其關係狀態值為 2^0:1

  rela會存入{"361":1 , "364":1 , "367":1 , "371":1 , "374":1 , "381":1 , "384":1 , "387":1}

第1組可能的三個字元為 "{0123567}48" 及  "48{0123567}" 共14種,其關係狀態值為 2^1:2

  rela會存入 {"048":2 , "148":2 , "248":2 , "348":2 , "548":2 , "648":2 , "748":2 } 7種,

      以及{"480":2 , "481":2 , "482":2 , "483":2 , "485":2 , "486":2 , "487":2 } 7種, 共14種

第2組可能的三個字元為"0{1234568}7"共7種,其關係狀態值為 2^2:4

  rela會存入{"017":4 , "027":4 , "037":4 , "047":4 , "057":4 , "067":4 , "087":4 } 7種

第3組可能的三個字元為"{036}{258}{678}"共21種,其關係狀態值為 2^3:8

  rela會存入{"026":8 , "027":8 ,"028":8 ,  "056":8 , "057":8 , "058":8 , "086":8 , "087":8 } 8種

       以及 {"326":8 , "327":8 ,"328":8 ,  "356":8 , "357":8 , "358":8 , "386":8 , "387":8 } 8種

       以及 {"627":8 ,"628":8 ,  "657":8 , "658":8 , "687":8 } 5種   共 21種

但是存入 rela 中若已出現過的 「關係狀態」值需 bit OR:

  例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "027":12

     又第0組出現 "387":1 且 第3組再出現"387":8 需改狀態值為 "387":9

 

在 a的全排列 分成的三段,可以使在rela中找到的狀態值 bit OR 後等於 2^4-1(2^n-1):15 就是符合

例如 a="361482057" 第1段的"361":1、第2段的"482":2、第3段的"057":12 , 三段的 bit OR值為 15故符合

首先先感謝一下樓上提供的idea,我再幫他補充一下

"例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "027":12"

這句話應該更正為

"例如 第2組出現 "057":4 且 第3組再出現"057":8 需改狀態值為 "057":12"

此範例解為12

分別是

027361485

057248361

057361248

057361482

057482361

248057361

248361057

361027485

361027548

361057248

361057482

361248057

361482057

361485027

361548027

482057361

482361057

485027361

485361027

548027361

548361027

 

更正:答案為24

 
ZeroJudge Forum