※ 引述《cutekid (可愛小孩子)》之銘言：
: 解法: 動態規劃, 空間複雜度: 種族數 * (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);
: : 這分別代表什麼意思
: : 非常感謝
不好意思
解完後發現已經有人PO了
但還是貼一下，解法是一樣的但是用c++方式做
input的話為了方便直接改成 vector
int solution2(vector<vector<int>>& w)
{
unordered_map<int, int> race[3];
for (int i = 0; i < w.size(); i++)
race[w[i][0] - 1][w[i][1] << 0 | w[i][2] <<1 | w[i][3] << 2]++;
int c = 0;
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
for (int k = 0; k < 8; k++)
{
if ((i | j | k) < 7) continue;
c += race[0][i] * race[1][j] * race[2][k];
}
return c;
}
我只測了題目上面的case，但思路應該沒錯