7-1 懂的都懂 (20 分)_懂的都懂c

输入样例：
5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11

输出样例：
Yes
No
Yes

基于考试时写的代码做了一点小修改，总体而言还是最简单的暴力算法。

//注意求平均除4不可取，对所要比较的数进行乘法运算，不然会出现浮点错误 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
int a[55],pi[maxn];
int n,j=0;
//打表算一下不同数的组合和 
void p(){ 
	for(int a1=1;a1<=n-3;a1++){
		for(int a2=a1+1;a2<=n-2;a2++){
			for(int a3=a2+1;a3<=n-1;a3++){
				for(int a4=a3+1;a4<=n;a4++){
					pi[++j]=a[a1]+a[a2]+a[a3]+a[a4];//注意这里除以4会出现浮点错误 
				}
			}
		}
	} 
}
//进行一个二分查找，或许直接用函数也可以但是考试的时候没有想到 
int cmp(int mi){
	mi=mi*4;//避免浮点错误的出现 
	int l=1,r=j;
	while(l<=r){
		int mid=(l+r)/2;
		if(mi==pi[mid])return 1;
		else if(mi<pi[mid])r=mid-1;
		else if(mi>pi[mid])l=mid+1;
	}
	return 0;
}
int main(){
	int k,m,mi,flag;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	p();
	sort(pi+1,pi+j+1);
	while(k){
		k--;
		flag=1;
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			scanf("%d",&mi);
			if(!cmp(mi)){
				flag=0; 
			}
		}
		if(flag)printf("Yes");
		else printf("No");
		if(k!=0)printf("\n");
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54