bzoj 3198: [Sdoi2013]spring 題解

【原題】

Time Limit: 40 Sec  Memory Limit: 256 MB

Submit: 253  Solved: 95

3 3

1 2 3 4 5 6

1 2 3 0 0 0

0 0 0 4 5 6

2

【題解】這道題明明是水題，坑了我兩天！！！真是傷心。發現哈希都不熟練了。

首先很容易想到是2^6枚舉01狀态，使得1的個數不小于K。比如枚舉了0110000，我們就可以用一個哈希來處理個數。然後統計一下結果即可。開始的代碼如下：

【代碼1】

【GO ON】很快就WA了。然後我發現了一個問題：要流量剛好K次。是剛好。也就是說，我多枚舉了很多狀态。那怎麼辦？可以用容斥搞一下，加上等于K的，減去等于K+1的，類推。。。以下是代碼：

【代碼2】

【分析】仔細一想，沒什麼不對的地方啊。唯一不滿的是，我的雙關鍵字哈希可能會被卡！！出于好奇，我就把它挂鍊了。總算A掉了。話說這個資料是什麼心态。。。還有，我自己YY了一個哈希挂鍊的方法，就是類似于邊表的形式（因為以前不怎麼寫哈希，求神犇輕噴）。

【AC代碼】

[Submit][Status]

Dragonite修正資料

Hash