※ 引述《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，但思路应该没错