恭喜你發(fā)現(xiàn)了寶藏！本文寫了十種方法來解決 [CSP-J2019] 數(shù)字游戲！你值得擁有！

本文同步發(fā)表于csdn，本人csdn號(hào)：Programmer_1745.

當(dāng)前版本：Prev-1.

1、字符串掃描法：

我們把讀入的內(nèi)容當(dāng)作字符串。之后進(jìn)行判斷：如果是 ‘1’ 就計(jì)數(shù)器加一。本方法也可以分為兩種方法，一種用 char 還有一個(gè)自然使用 string.

char 類型方法如下：

string 類型方法如下：

2、位運(yùn)算“與”方法：

輸入的內(nèi)容我們可以通過ASCII碼來轉(zhuǎn)換為 int 類型。代碼可以這么寫：

那么轉(zhuǎn)為整數(shù)能干嘛？我們可以使用與運(yùn)算。位運(yùn)算 & 符號(hào)的含義是：如果兩個(gè)相應(yīng)的二進(jìn)制位都為１，則該位的結(jié)果值為1，否則為0。不過這種方法確實(shí)多此一舉。

3、 萬(wàn)物皆可打表法：

內(nèi)存限制250MB，空間足夠！最大值為11111111，小于60000000。打表干嘛，愣著啊！

4、bitset容器法：

bitset是一個(gè)二進(jìn)制容器。其中有一個(gè)函數(shù)非常666，就是 count() 函數(shù)。它的作用是求容器中有幾個(gè)1。那么這道題就迎刃而解了。

5、取余法：

這個(gè)大佬真厲害，思路很清奇，在線膜拜。不難理解吧？

6、cin.get 法：

其實(shí)我也不知道怎么去這種方法名字....

7、線段樹法：

輸入的內(nèi)容只含有0和1，那么求出1的個(gè)數(shù)其實(shí)就是求出這個(gè)字串里所有數(shù)字的和。沒錯(cuò)這就是區(qū)間和。代碼就不貼啦~ 其實(shí)我不會(huì)寫。

8、樹狀數(shù)組法：

思路和法七是一樣的，只不過這個(gè)我會(huì)寫。

9、Kruskal最小生成樹法：

假設(shè)我們有一個(gè)樹：

如果我們讀入的這個(gè)串，它的 i 位代表 0 號(hào)節(jié)點(diǎn)到 i 號(hào)節(jié)點(diǎn)的距離。輸入到 1 我們就建邊，反之跳過。最后來一遍 Kruskal 即可。

1. 首先，我們需要一個(gè)結(jié)構(gòu)體，對(duì)吧？

2.我們要寫 cmp 函數(shù)作為 sort 函數(shù)的比較器。同時(shí)還需要寫 find 函數(shù)作為并查集的算法。（其實(shí)他們沒有直接邏輯聯(lián)系，只不過這里放在一起）。

3.這些預(yù)備工作寫完，該寫輸入代碼了。如果輸入的數(shù)字為 1 則建邊。這里是把 1 當(dāng)做了字符。輸入完繼續(xù)初始化（不然會(huì)出一些很奇怪的錯(cuò)誤）

4.這里是 Kruskal 主要程序！

5.最后輸出 t 即可（話說我好像把所有代碼都貼上了）...

10、（壓軸）FFT快速傅里葉變換法：

沒錯(cuò)這是一個(gè)壓軸的方法，特別整活，你值得擁有！

一個(gè)大佬教我的——這道題確實(shí)可以使用 FFT. 首先這個(gè)題目可以轉(zhuǎn)化為給出字符串和 1 這個(gè)字符串有多少個(gè)點(diǎn)可以匹配，我們可以分別做 3 次 FFT 即可就可以通過此題。我們定義字串?S,T 的“距離”為：

則可以匹配的條件就是：

為了方便，我們定義 c 為：

那么我們令 T 為 1，對(duì)于 S 中每個(gè)位置都求出一個(gè) c ，那么問題就是這個(gè) c 怎么求。顯然可以將距離的式子拆開，變?yōu)橛扇齻€(gè) ∑ 組成的式子，而這三個(gè)式子正好是多項(xiàng)式的形式，那么我們就可以用 FFT 分別做三次來求出每個(gè) c 的值，最后統(tǒng)計(jì)一下就可以出解了。這次我真的只貼一部分代碼（懶得寫）。

update：?

2022.10.04： Prev-1版本發(fā)布了！

粉福：

1、滿20粉爆C++碼風(fēng)

2、滿30粉爆Python3碼風(fēng)

求贊+關(guān)注