Re: [問題] 高中生解題系統C460一問

[gofigure (平行世界)]

※ 引述《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，但思路應該沒錯


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.3.166
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1537014851.A.147.html
※ 編輯: gofigure (114.24.3.166), 09/15/2018 20:47:20
→ gofigure: 不好意思 我搞錯了 請忽略這篇
※ 編輯: gofigure (114.24.3.166), 09/15/2018 21:01:06
→ gofigure: 哈 耍笨了 我寫了兩個solution 輸出第一個結果
→ gofigure: 以為第二個是對的就貼上來
推 Ori185: 所以忽略這篇看上一篇嗎，謝謝XD
→ alan23273850: 那這樣要不要刪文