NOIP2014年普及组T1 珠心算测验

【题目描述】

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？
最近老师出了一些测验题，请你帮忙求出答案

【输入】

输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。
第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

【输出】

输出共一行，包含一个整数，表示测验题答案。

【输入样例】

4
1 2 3 4

【输出样例】

2

【样例说明】

由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的

两个不同的数。

【数据说明】

对于 100%的数据，3  ≤  n  ≤  100，测验题给出的正整数大小不超过 10,000。

---

---

【分析】

题目主要是要完成一些去重操作，原题当中描述“其中有多少个数，恰好等于集合中另外两个（不同的）数之和？”

例如下面这组数据

1 2 3 4 5

在这组数据中，1+4 =5 ， 2 +3 =5 ，这样能不能算两个数呢?当然不能，也就是说如果一个数被多次加出，那么不会增加计数的结果。所以我们可以通过一个flag数组用来标记这个被加出来的和有没有被重复标记过。

【参考代码1】

#include<bits/stdc++.h>
using namespace std;
int books[1010];   //定义图书编号数组
int main(){
	int n,q;  
	cin>>n>>q;  //读入书的数量和读者的数量
	for(int i=0;i<n;i++)
		cin>>books[i]; 
 
	sort(books,books+n);   //对书的编号进行排序

	int x,y;
	while(q--)   
	{
		cin>>x>>y;    //读入需求码长度和需求码
		int ans=-1;   //先让结果为-1，如果没有给ans赋过值，直接输出就行
		for(int i=0;i<n;i++) 
		{
			int cnt = pow(10,x);  //求10的x次方
			int temp=books[i]%cnt;  //取余
			if(temp == y )
				{
				   ans=books[i];  //取余后的结果和需求码相同，则赋值
				   break;	
				}	 
		} 
		cout<<ans<<endl; 
	} 
	return 0;
}

---

返回目录：NOIP/CSP信息学奥赛复赛

---