作者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/cn.aspx?n=bbs/C_and_CPP/M.1537011057.A.A63.html
1F：→ Ori185: 解法已了解，非常感谢！ 09/16 10:41