恭喜你发现了宝藏！本文写了十种方法来解决 [CSP-J2019] 数字游戏！你值得拥有！

本文同步发表于csdn，本人csdn号：Programmer_1745.

当前版本：Prev-1.

1、字符串扫描法：

我们把读入的内容当作字符串。之后进行判断：如果是 ‘1’ 就计数器加一。本方法也可以分为两种方法，一种用 char 还有一个自然使用 string.

char 类型方法如下：

string 类型方法如下：

2、位运算“与”方法：

输入的内容我们可以通过ASCII码来转换为 int 类型。代码可以这么写：

那么转为整数能干嘛？我们可以使用与运算。位运算 & 符号的含义是：如果两个相应的二进制位都为１，则该位的结果值为1，否则为0。不过这种方法确实多此一举。

3、 万物皆可打表法：

内存限制250MB，空间足够！最大值为11111111，小于60000000。打表干嘛，愣着啊！

4、bitset容器法：

bitset是一个二进制容器。其中有一个函数非常666，就是 count() 函数。它的作用是求容器中有几个1。那么这道题就迎刃而解了。

5、取余法：

这个大佬真厉害，思路很清奇，在线膜拜。不难理解吧？

6、cin.get 法：

其实我也不知道怎么去这种方法名字....

7、线段树法：

输入的内容只含有0和1，那么求出1的个数其实就是求出这个字串里所有数字的和。没错这就是区间和。代码就不贴啦~ 其实我不会写。

8、树状数组法：

思路和法七是一样的，只不过这个我会写。

9、Kruskal最小生成树法：

假设我们有一个树：

如果我们读入的这个串，它的 i 位代表 0 号节点到 i 号节点的距离。输入到 1 我们就建边，反之跳过。最后来一遍 Kruskal 即可。

1. 首先，我们需要一个结构体，对吧？

2.我们要写 cmp 函数作为 sort 函数的比较器。同时还需要写 find 函数作为并查集的算法。（其实他们没有直接逻辑联系，只不过这里放在一起）。

3.这些预备工作写完，该写输入代码了。如果输入的数字为 1 则建边。这里是把 1 当做了字符。输入完继续初始化（不然会出一些很奇怪的错误）

4.这里是 Kruskal 主要程序！

5.最后输出 t 即可（话说我好像把所有代码都贴上了）...

10、（压轴）FFT快速傅里叶变换法：

没错这是一个压轴的方法，特别整活，你值得拥有！

一个大佬教我的——这道题确实可以使用 FFT. 首先这个题目可以转化为给出字符串和 1 这个字符串有多少个点可以匹配，我们可以分别做 3 次 FFT 即可就可以通过此题。我们定义字串 S,T 的“距离”为：

则可以匹配的条件就是：

为了方便，我们定义 c 为：

那么我们令 T 为 1，对于 S 中每个位置都求出一个 c ，那么问题就是这个 c 怎么求。显然可以将距离的式子拆开，变为由三个 ∑ 组成的式子，而这三个式子正好是多项式的形式，那么我们就可以用 FFT 分别做三次来求出每个 c 的值，最后统计一下就可以出解了。这次我真的只贴一部分代码（懒得写）。

update： 

2022.10.04： Prev-1版本发布了！

粉福：

1、满20粉爆C++码风

2、满30粉爆Python3码风

求赞+关注