[CSP-J2019] 数字游戏题解（正经与不正经的都有，十种方法）

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

先看目录吧。正经的解法适合新手参考，整活方法适合大佬阅读！

目录

 我们先来正经的解法

1、字符串扫描法

2、位运算“与”方法

3、 万物皆可打表法

4、bitset容器法

5、取余法

6、cin.get 法

不正经的解法

7、线段树法

8、树状数组法

9、Kruskal最小生成树法

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

update 

粉福

 我们先来正经的解法。

这些解法都比较基础。可供新手参考。

1、字符串扫描法：

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

char 类型方法如下：

#include
using namespace std;
int ans=0;
char s[10];
int main(){
	cin>>s;
	for(int i=0;i<8;i++){//模拟
		if(s[i]=='1'){//判断是否为1
			ans++;//计数器++
		}
	}
	cout<

string 类型方法如下：

#include
using namespace std;
int main(){
	string s1;
	int cnt;
	cin>>s1;
	for(int i=0;i 
2、位运算“与”方法： 
输入的内容我们可以通过ASCII码来转换为 int 类型。代码可以这么写：
 
int x=s1[i]-'0';
 
那么转为整数能干嘛？我们可以使用与运算。位运算 & 符号的含义是：如果两个相应的二进制位都为１，则该位的结果值为1，否则为0。不过这种方法确实多此一举。
 
#include
using namespace std;
int main(){
    string s1;
    cin>>s1;
    int cnt=0;
    for(int i=0;i 
3、 万物皆可打表法： 
内存限制250MB，空间足够！最大值为11111111，小于60000000。打表干嘛，愣着啊！
 
#include 
using namespace std;
int a[11111115];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
			for(int k=0;k<=1;k++)
				for(int l=0;l<=1;l++)
					for(int m=0;m<=1;m++)
						for(int n=0;n<=1;n++)
							for(int o=0;o<=1;o++)
								for(int p=0;p<=1;p++)
									a[i*10000000+j*1000000+k*100000+l*10000+m*1000+n*100+o*10+p]=i+j+k+l+m+n+o+p;
	cout<
 
4、bitset容器法： 
bitset是一个二进制容器。其中有一个函数非常666，就是 count() 函数。它的作用是求容器中有几个1。那么这道题就迎刃而解了。
 
#include
using namespace std;
int main(){
    bitset<8> k; //题目说长度8，那就来吧
    cin>>k;
    cout< 
5、取余法： 

 这个大佬真厉害，思路很清奇，在线膜拜。不难理解吧？
 
#include
using namespace std; 
int main(){
    int f;
    cin>>f;
    cout< 
6、cin.get 法： 
其实我也不知道怎么去这种方法名字....
 
#include
using namespace std;
int cnt;//计数器 
int main(){
	for(int i=0;i<8;i++) if(cin.get()=='1') cnt++;
	//用cin.get代替字符——其实可以用getchar.
	cout< 
不正经的解法： 
我们为什么要正常思路解？我们可以不正常一点。
 
7、线段树法： 
输入的内容只含有0和1，那么求出1的个数其实就是求出这个字串里所有数字的和。没错这就是区间和。代码就不贴啦~ 其实我不会写。
 
8、树状数组法： 
思路和法七是一样的，只不过这个我会写。
 
#include
using namespace std;
int i,a[500005],c[500005];
char chr;
int lowbit(int x){
	return x&-x;
}//lowbit
void add(int x,int k){
	while(x<=8){
		c[x]+=k;
		x+=lowbit(x);
	}
}//更新c数组
int sum(int x){//求和 
	int t=0;
	while(x!=0){
		t+=c[x];
		x-=lowbit(x);
	}
    return t;
}
int main(){
	for(i=1;i<=8;i++){
		chr=getchar();
		a[i]=chr-'0';
		add(i,a[i]);
	}//输入
	printf("%d",sum(8)-sum(0));//输出
	return 0;
}
 
这份代码很简单，不过就 x&-x 这里难以理解点，可以看看这个
 
 
9、Kruskal最小生成树法： 
假设我们有一个树：
 
 
 
如果我们读入的这个串，它的 i 位代表 0 号节点到 i 号节点的距离。输入到 1 我们就建边，反之跳过。最后来一遍 Kruskal 即可。
 
1. 首先，我们需要一个结构体，对吧？
 
#include
using namespace std;
struct A{
    int a,b,s;
}a[200005];
 
2.我们要写 cmp 函数作为 sort 函数的比较器。同时还需要写 find 函数作为并查集的算法。（其实他们没有直接逻辑联系，只不过这里放在一起）。
 
bool cmp(A x,A y){
    return x.s 
3.这些预备工作写完，该写输入代码了。如果输入的数字为 1 则建边。这里是把 1 当做了字符。输入完继续初始化（不然会出一些很奇怪的错误）
 
for(i=1;i<=8;i++){
    c=getchar()；
    c=='1'?a[++m].a=0,a[m].b=i,a[m].s=1:c=c;
}//建边
for(i=0;i<=8;i++) f[i]=i;//初始化
 
4.这里是 Kruskal 主要程序！
 
for(i=1;i<=m;i++){
    int p=find(a[i].a),q=find(a[i].b);
	if(p==q) continue;
	f[q]=p,t+=a[i].s,s++;
    if(s==n-1) break;
}
 
5.最后输出 t 即可（话说我好像把所有代码都贴上了）...
 
 
10、（压轴）FFT快速傅里叶变换法： 
没错这是一个压轴的方法，特别整活，你值得拥有！
 
一个大佬教我的——这道题确实可以使用 FFT. 首先这个题目可以转化为给出字符串和 1 这个字符串有多少个点可以匹配，我们可以分别做 3 次 FFT 即可就可以通过此题。我们定义字串 S,T 的“距离”为：
 
 
则可以匹配的条件就是：
 
 
为了方便，我们定义 c 为：
 
那么我们令 T 为 1，对于 S 中每个位置都求出一个 c ，那么问题就是这个 c 怎么求。显然可以将距离的式子拆开，变为由三个 ∑ 组成的式子，而这三个式子正好是多项式的形式，那么我们就可以用 FFT 分别做三次来求出每个 c 的值，最后统计一下就可以出解了。这次我们真的只贴一部分代码（懒得写）。
 
//FFT主代码
inline void FFT(reg Complex *A,reg int opt){
    for(reg int i=0;i 
//运算符重载
struct Complex{
    db x,y;
    friend Complex operator + (const Complex &a,const Complex &b){
        return ((Complex){a.x+b.x,a.y+b.y});
    }
    friend Complex operator - (const Complex &a,const Complex &b){
        return ((Complex){a.x-b.x,a.y-b.y});
    }
    friend Complex operator * (const Complex &a,const Complex &b){
        return ((Complex){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x});
    }
    friend Complex operator * (const Complex &a,const db &val){
        return ((Complex){a.x*val,a.y*val});
    }
}f[2000005],g[2000005],p[2000005];
//注：这里的 db 指的是 double.
 
update：  
2022.08.09： 文章发布了！
 
同日：修改了一处笔误并添加了粉福和update区。
 
同日：增加了两个标签。
 
 
粉福： 
1、满10粉爆C++码风
 
2、满15粉爆Python3码风
 
3、满20粉爆H5码风
 
（待补充中....）
 
 
求赞+关注