#36613: C++解題思路及實作細節


ck1110675 (一笑落塵)

School : 臺北市立建國高級中學
ID : 228469
IP address : [1.162.31.27]
Last Login :
2024-04-25 11:57:54
b547. 3.巧克力擺盒 -- 102學年度北基區北三區資訊學科能力競賽 | From: [1.162.82.6] | Post Date : 2023-07-28 10:43

這題的大方向是要我們列出9!=362880種排列方式,每一種都丟到由k組指定關係組成的漏斗裡面看能不能順利通過,可以的話count++,但實作上有很多細節需要解決。

一、如何列出所有的排列?我是用一個class來定義chocolate這個型態,包含了int num,char flavor,char size三個變數,其中num是作為排列的工具。建立一個chocolate一維陣列。這樣我們就可以使用<algorithm>中的next_permutation函數自動排列了。

二、要怎麼建立漏斗?依據題目我們知道他所指定的k組指定關係,每一組只需要「上、中、下」其中一層滿足就算是成功了,滿足的條件是在這一層的六個字元中,「他需要的字元」剛好等於「我們排出來的字元」或是「‘?’」。

三、要怎麼處理關係二?我們可以分析輸入說明的一個細節「除了形式3的中間巧克力為 ? ?,每個巧克力可能同時指定口味及形狀,也可能只指定口味或形狀,但不會兩種皆不指定」,也就是說靠左及靠右的巧克力測資不會給你「??」,所以我們可以利用這個訊息,放心的在讀測資的時候把那組關係當成靠左,把右邊巧克力設成「??」,後面漏斗再多給他一次機會,如果右邊的巧克力是「??」,就把它改成靠右再判斷一次。

以下是我的程式碼,如果有更好的寫法歡迎指教!

#include<iostream>

#include<utility>

#include<algorithm>

using namespace std;

class chocolate{

public:

int num;

char flavor;

char size;

};

bool cmp(chocolate a,chocolate b){

return a.num<b.num;

}

int main(){

int n;cin>>n;

char test[10][6];

int k;

chocolate arr[9]={

{0,'P','S'},{1,'P','C'},{2,'P','T'},{3,'B','S'},{4,'B','C'},

{5,'B','T'},{6,'Y','S'},{7,'Y','C'},{8,'Y','T'}};

for(int i=0;i<n;i++){

cin>>k;

if(k==2){

for(int j=0;j<4;j++){

cin>>test[i][j];

}

test[i][4]='?';

test[i][5]='?';

}else{

for(int j=0;j<6;j++){

cin>>test[i][j];

}

}

}

int cnt=0;

do{

bool correct=true;

for(int i=0;i<n;i++){

bool candoit=false;

for(int j=0;j<3;j++){

if((test[i][0]==arr[3*j].flavor||test[i][0]=='?')&&

(test[i][1]==arr[3*j].size||test[i][1]=='?')&&

(test[i][2]==arr[3*j+1].flavor||test[i][2]=='?')&&

(test[i][3]==arr[3*j+1].size||test[i][3]=='?')&&

(test[i][4]==arr[3*j+2].flavor||test[i][4]=='?')&&

(test[i][5]==arr[3*j+2].size||test[i][5]=='?')){

candoit=true;

}

}

if(test[i][4]=='?'&&test[i][5]=='?'){

for(int j=0;j<3;j++){

if((test[i][4]==arr[3*j].flavor||test[i][4]=='?')&&

(test[i][5]==arr[3*j].size||test[i][5]=='?')&&

(test[i][0]==arr[3*j+1].flavor||test[i][0]=='?')&&

(test[i][1]==arr[3*j+1].size||test[i][1]=='?')&&

(test[i][2]==arr[3*j+2].flavor||test[i][2]=='?')&&

(test[i][3]==arr[3*j+2].size||test[i][3]=='?')){

candoit=true;

}

}

}

if(!candoit){

correct=false;

break;

}

 

}

if(correct){

cnt++;

}

}while(next_permutation(arr,arr+9,cmp));

cout<<cnt;

}

 
ZeroJudge Forum