计蒜客： T2077 珠心算测验以及T1195和数

短命女 2023-07-08 06:59 67阅读 0赞

题目链接：[珠心算测验][Link 1]

解题思路：枚举所有符合条件的，但是要注意去重。比如测试样例有四种符合条件的数据，但是其中有重复的，虽然满足：加数和被加数必须是集合中的两个不同的数。有两种方法，其实思路差不多。但是注意题目中说集合中的数各不相同，如果将条件改为集合中的数可以相同（比如这个题目[计蒜客T1195：和数][T1195]）那么第一种方法就不再适用，因为如果测试样例是2 2 1 1，那么两个2都满足条件，第一种方法就不适用了，只能用第二种方法解决。

![20200225153803233.png][]

第一种方法需要开一个数组（注意数组的大小，太小了容易被卡数据。）将相同的结果出现的次数保存在数组中方便去重。最后输出去重之后的结果。解题的方法有很多，如果有更好的解题方法欢迎评论！

第一种写法（只适合T2077）

#include<iostream>
    using namespace std;
    
    int main(){
    	
    	int n,arr[101] = {0},sum[10001] = {0};
    	//注意数组的范围大小，不要开的太小被卡测试样例     
    	int s;
    	int count = 0;    //用来计数有多少个符合条件的 
    	cin>>n;
    	
    	for(int i=0;i<n;i++){
    		cin>>arr[i];
    	}
    	
    	//枚举，注意去重 
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			for(int k=0;k<n;k++){
    				if(arr[i] == arr[j]+arr[k] && i!=j && i!=k && j!=k){
    					//cout<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<endl;
    					s =  arr[j]+arr[k];
    					sum[s]++;    //将相同的结果出现的次数保存在数组中方便去重 
    					
    				}
    			}
    		}
    	}
    	for(int i=0;i<10001;i++){
    		if(sum[i]!=0){
    			count++;
    		}
    	}
    	cout<<count;
    	
    	return 0;
    	
    }

另一种写法(两个题目都可以AC)：

#include<iostream>
    using namespace std;
    
    int main(){
    	
    	int n,arr[101] = {0},sum[101] = {0};    
    	int s;
    	int count = 0;    //用来计数有多少个符合条件的 
    	cin>>n;
    	
    	for(int i=0;i<n;i++){
    		cin>>arr[i];
    	}
    	
    	//枚举
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			for(int k=0;k<n;k++){
    				if(sum[i] != 1 && arr[i] == arr[j]+arr[k] && i!=j && i!=k && j!=k){
    					//cout<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<endl;
    					count++; 
    					sum[i] = 1;    //如果符合条件，就将该位置标记 
    				}
    			}
    		}
    	}
    	cout<<count; 
    	return 0;
    	
    }

[Link 1]: https://nanti.jisuanke.com/t/T2077
[T1195]: https://nanti.jisuanke.com/t/T1195
[20200225153803233.png]: https://img-blog.csdnimg.cn/20200225153803233.png