作者cutekid (可愛小孩子)
看板C_and_CPP
標題Re: [問題] 高中生解題系統C460一問
時間Sat Sep 15 19:30:53 2018
解法: 動態規劃, 空間複雜度: 種族數 * (2^特性數), 時間複雜度: (2^特性數)^種族數
以下程式碼(約15行):
#include<stdio.h>
int main(){
int n,c,c1,c2,c3,a,r,d;
long long int sum = 0, mask[4][8]={0};
for(scanf("%d",&n);scanf("%d%d%d%d",&c,&a,&r,&d) != EOF;){
++mask[c][4 * a + 2 * r + d];
}
for(c1 = 0; c1 <= 7; ++c1)
for(c2 = 0; c2 <=7; ++c2)
for(c3 = 0; c3 <=7; ++c3)
if((c1 | c2 | c3) == 7)
sum += mask[1][c1] * mask[2][c2] * mask[3][c3];
printf("%lld\n",sum);
return 0;
}
※ 引述《Ori185 (Ori185)》之銘言：
: 問題(Question)：
: https://zerojudge.tw/ShowProblem?problemid=c460
: 各位好，10月底要考APCS，最近大概會很常來問問題了...
: 這題給的條件基本上我認為就是三個種族交叉測試
: 符合就把答案遞增
: 但是遇上 N>= 10000 就不管用了
: 一定會超過0.5s
: 想請問有什麼可以判斷的方法，不會像我這樣判斷超久
: 附上程式碼，非常感謝
: 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
: https://glot.io/snippets/f4tm0yiuoj/raw
: 補充說明(Supplement)：
: 我有看過下面分享的解法，真的非常厲害
: 不過我目前還沒學到位元運算
: 可能沒辦法像這樣運用熟練
: 另外也想請問
: ios::sync_with_stdio (false);
: cin.tie(0);
: cout.tie(0);
: 這分別代表什麼意思
: 非常感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.168.16.245
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1537011057.A.A63.html
1F：→ Ori185: 解法已了解，非常感謝！ 09/16 10:41