【真题讲解】 NOIP2014_综合

T1：珠心算测验

题目描述
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？
最近老师出了一些测验题，请你帮忙求出答案。
输入格式
输入文件名为 count.in。
输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。
第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。
输出格式
输出文件名为 count.out。
输出共一行，包含一个整数，表示测验题答案。
样例数据
input
4
1 2 3 4
output
2
样例说明
由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的两个不同的数。
数据规模与约定
对于 100%的数据，3 ≤ n ≤ 100，测验题给出的正整数大小不超过 10,000。
时间限制：1s1s
空间限制：128MB

本题的题意容易产生误解，意为有多少个数可以被其它的数字所加，而不是求加的所有方案。例如，3，1，2，1，2这一串数字，3同时可以同时被答案所加，但是只能算以此，这也是容易得到30分的地方。

此题的做法是：
$1 .$ 读入。
$2 .$ 双重循环枚举两个数，将两数之和进行标记。
$3 .$ 枚举每一个数，看这个数是否已经被标记即可。

因自己代码不变理解，此处放上他人代码，如下：

#include<bits/stdc++.h> using namespace std; int a[10001]={
     },b[10000001]={
     }; int ans=0; int n; int main() {
     freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++)b[a[i]+a[j]]=1;for (int i=1;i<=n;i++) ans+=b[a[i]];printf("%d",ans);fclose(stdin);fclose(stdout);return 0; }

2.比例简化

题目描述
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。
不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质（两个整数的最大公约数是 1）的前提下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值尽可能小。
输入格式
输入文件名为 ratio.in。
输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
输出格式
输出文件名为 ratio.out。
输出共一行，包含两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例。
样例数据
input
1498 902 10
output
5 3
数据规模与约定
对于 100%的数据，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100，A/B ≤ L 。
时间限制：1s1s
空间限制：128MB128MB
思路：
这道题目其实并没有难度，只需要根据题意，枚举 $A^{'}$ 和 $B ’$ 然后各种判断是否合法再求最小值即可。当然尽量不要用实数，~~精度把我卡下了一等线~~ 。

题目上面还说A’和B‘是互质的，那么就说明她们的最大公因数必须是 $1$ 才是一组合法的解。即必须满足 $g c d (a, b) = 1$ ，这里采用辗转相除法（至于实现原理我没怎么理解，只是见多了会背了）
代码如下：

#include<bits/stdc++.h> using namespace std; int gcd(int a,int b) {
     if (b==0) return a;else gcd(b,a%b); } int main() {
     freopen("ratio.in"