2012-2018普及组第一题题解

noip2018 标题统计

【题目描述】

凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？

注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。

【输入】

输入文件只有一行，一个字符串 s。

【输出】

输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

【输入样例】

234

【输出样例】

3

【提示】

【样例1说明】

标题中共有 3 个字符，这 3 个字符都是数字字符。

【样例输入2】

Ca 45

【样例输出2】

4

解析：gets()的头文件为#include<stdio.h>,它是C语言里面的函数。

#include<iostream> #include<cstring> #include<stdio.h> //#include <bits/stdc++.h> using namespace std; char a[50]; int main() { gets(a); int sum = 0; int l = strlen(a); for(int i = 0; i < l; ++i) { if(a[i] != ' ' && a[i] != '\n') { sum++; } } cout << sum << endl; return 0; }

【样例2说明】

标题中共有 5 个字符，包括 1 个大写英文字母，1 个小写英文字母和 2 个数字字符，还有 1 个空格。由于空格不计入结果中，故标题的有效字符数为 4 个。

【数据规模与约定】

规定 |s|表示字符串 s 的长度（即字符串中的字符和空格数）。

对于 40%的数据，1 ≤ |s| ≤ 5，保证输入为数字字符及行末换行符。

对于 80% 的数据，1 ≤ |s| ≤ 5，输入只可能包含大、小写英文字母、数字字符及行末换行符。

对于 100% 的数据，1 ≤ |s| ≤ 5，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。

【来源】

No

noip2017 成绩

测试地址：https://www.luogu.org/problem/P3954

题目描述

牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：

总成绩=作业成绩\times 20\%+×20%+小测成绩×30\%+×30%+期末考试成绩\times 50\%×50%

牛牛想知道，这门课程自己最终能得到多少分。

输入格式

三个非负整数A,B,CA,B,C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是100100分。

输出格式

一个整数，即牛牛这门课程的总成绩，满分也是100100分。

输入输出样例

输入 #1复制

100 100 80

输出 #1复制

90

输入 #2复制

60 90 80

输出 #2复制

79

说明/提示

输入输出样例1说明

牛牛的作业成绩是100100分，小测成绩是100100分，期末考试成绩是8080分，总成绩是100 \times 20\%+100 \times 30\%+80 \times 50\%=20+30+40=90100×20%+100×30%+80×50%=20+30+40=90。

输入输出样例2说明

牛牛的作业成绩是6060分，小测成绩是9090分，期末考试成绩是8080分，总成绩是60 \times 20\%+90 \times 30\%+80 \times 50\%=12+27+40=7960×20%+90×30%+80×50%=12+27+40=79。

数据说明

对于30\%30%的数据，A=B=0A=B=0。

对于另外30\%30%的数据，A=B=100A=B=100。

对于100\%100%的数据，0≤A,B,C≤1000≤A,B,C≤100且A,B,CA,B,C都是1010的整数倍。

#include<iostream> using namespace std; int main() { // freopen("score.in","r",stdin); // freopen("score.out","w",stdout); int a,b,c; cin >> a >> b >> c; cout << a*0.2+b*0.3+c*0.5; return 0; }

#include<cstdio> int main() { int a,b,c; scanf("%d%d%d",&a,&b,&c); printf("%d",a*2/10+b*3/10+c*5/10); return 0; }

注意：用printf输出时，不可以直接输出a*0.2+b*0.3+c*0.5，这样结果一直是0.因为相当于a、b、c都是和0相乘。

#include<iostream> #include<cstdio> using namespace std; int main() { int a,b,c; scanf("%d%d%d",&a,&b,&c); printf("%.0f",a*0.2+b*0.3+c*0.5); return 0; }

p2016 买铅笔

网址：https://www.luogu.org/problem/P1909

题目描述

P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有 33种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过nn支铅笔才够给小朋 友们发礼物。

现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少nn支铅笔最少需要花费多少钱。

输入格式

第一行包含一个正整数nn，表示需要的铅笔数量。

接下来三行，每行用22个正整数描述一种包装的铅笔：其中第11个整数表示这种 包装内铅笔的数量，第22个整数表示这种包装的价格。

保证所有的77个数都是不超过1000010000的正整数。

输出格式

11个整数，表示P老师最少需要花费的钱。

输入输出样例

输入 #1复制

57 2 2 50 30 30 27

输出 #1复制

54

输入 #2复制

9998 128 233 128 2333 128 666

输出 #2复制

18407

输入 #3复制

9999 101 1111 1 9999 1111 9999

输出 #3复制

89991

说明/提示

铅笔的三种包装分别是：

• 22支装，价格为22;
• 5050支装，价格为3030;
• 3030支装，价格为2727。

P老师需要购买至少5757支铅笔。

如果她选择购买第一种包装，那么她需要购买2929份，共计2 \times 29 = 582×29=58支，需要花费的钱为2 \times 29 = 582×29=58。

实际上，P老师会选择购买第三种包装，这样需要买22份。虽然最后买到的铅笔数 量更多了，为30 \times 2 = 6030×2=60支，但花费却减少为27 \times 2 = 5427×2=54，比第一种少。

对于第二种包装，虽然每支铅笔的价格是最低的，但要够发必须买22份，实际的花费达到了 30 \times 2 = 6030×2=60，因此P老师也不会选择。

所以最后输出的答案是5454。

【子任务】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试 只解决一部分测试数据。

每个测试点的数据规模及特点如下表：

上表中“整倍数”的意义为：若为KK，表示对应数据所需要的铅笔数量nn—定是每种包装铅笔数量的整倍数（这意味着一定可以不用多买铅笔)。

解析：因为不允许将铅笔的包装拆开，所以要买够至少n支铅笔最少需要花费的费用应该是全部都买一种铅笔时的最少费用，只需要算出全部买一种铅笔时的费用，然后输出3种费用中最少的费用即可。

#include<cstdio> #include<cmath> #include<iostream> using namespace std; int main() { int n,a1,b1,a2,b2,a3,b3; scanf("%d",&n); scanf("%d%d%d%d%d%d",&a1,&b1,&a2,&b2,&a3,&b3); int c1 = ceil(n*1.0/a1);//计算全部买a时，需要买几包 int c2 = ceil(n*1.0/a2); int c3 = ceil(n*1.0/a3); // printf("%d %d %d\n",c1,c2,c3); int d1 = c1*b1;//计算全部买a时，最少需要多少钱 int d2 = c2*b2; int d3 = c3*b3; int min = d1; if(d1 >= d2) min = d2;//计算3种包装买够至少n只铅笔至少需要多少钱 else min = d1; if(min >= d3) min = d3; else min = min; printf("%d",min); return 0; }

p2015 金币

网址：https://www.luogu.org/problem/P2669

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1N+1天里，每天收到N+1N+1枚金币。

请计算在前KK天里，骑士一共获得了多少金币。

输入格式

一个正整数KK，表示发放金币的天数。

输出格式

一个正整数，即骑士收到的金币数。

输入输出样例

输入 #1复制

6

输出 #1复制

14

输入 #2复制

1000

输出 #2复制

29820

说明/提示

【输入输出样例 1 说明】

骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 1+2+2+3+3+3=141+2+2+3+3+3=14 枚金币。

对于 100\%100%的数据，1 ≤ K ≤ 10,0001≤K≤10,000。

解析：本题相当于1+2+3+4+5+……n的变形形式，此时sum=sum+i.只用一重循环即可解决。本题在这个的基础上多加一层循环，处理每个数字出现的次数。

#include<cstdio> int main() { int n,sum=0,count=0; bool flag = 0; scanf("%d",&n); for(int i = 1; i <= n; ++i) { if(flag==0) { for(int j = 1; j <= i; ++j) { count++; sum+=i; if(count>=n) //当到达n个数后就不再计算了 { flag = 1; break; } } } } printf("%d",sum); return 0; }

#include<iostream> using namespace std; int main() { int k,sum = 0,m = 0; cin >> k; for(int i = 1; i <= k; ++i) { for(int j = 1; j <= i; ++j) { sum += i; m++; if(m == k) break; } if(m == k) break; } cout << sum << endl; return 0; }

#include<iostream> using namespace std; int main() { int k;//天数 cin >> k; int sum = 0,c = 0;//累积求和 for(int i = 1; i <= k; ++i) { for(int j = 1; j <= i; ++j) { sum = sum + i;//金币的数量 c++;//已经经过的天数 if(c == k) { cout << sum << endl; return 0; } } // if(c == k) break; } //cout << sum << endl; return 0; }

#include<iostream> using namespace std; int main() { int k,sum=0,day=0,j=1; cin>>k; for(int i=1;i<=k;i++) { sum+=j; day++; if(day==j) { j++; day=0; } } cout<<sum; }

noip2014 珠心算测验

链接：https://www.luogu.org/problem/P2141

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

(本题目为2014NOIP普及T1)

输入格式

共两行，第一行包含一个整数nn，表示测试题中给出的正整数个数。

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

输出格式

一个整数，表示测验题答案。

输入输出样例

输入 #1复制

4 1 2 3 4

输出 #1复制

2

说明/提示

【样例说明】

由1+2=3,1+3=41+2=3,1+3=4，故满足测试要求的答案为22。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

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

解析：比如样例：

6

1 3 5 7 8 9

此时输出结果为2.

1+3=4 1+5=6 1+7=81+8=91+9=10

3+5=83+7=10 3+8=11 3+9=12

5+7=12 5+8=13 5+9=14

7+8=16

此时有8、9两个数是刚好等于集合中另外两个数的和。

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int a[10005],b[10005]; int main() { int n,m=0; scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%d",&a[i]); sort(a+1,a+1+n);//先对输入的数进行排序 for(int i = 1; i <= n; ++i)//先让第一个数依次和第2-n个数相加，看结果是否有和集合中相同的数 { for(int j = i+1; j <= n; ++j) { for(int k = 1; k<= n; ++k) { if(a[i]+a[j]==a[k]) { b[++m]=a[k];//b数组中存储集合中存在与两个数之和 的值相等的数 } } } } sort(b+1,b+1+m); //对集合b中的数进行排序 int l = m; for(int i = 1; i <= m; ++i)//由于相等的数可能重合，所以需要去重 { if(b[i] == b[i+1]) l--; } printf("%d",l); return 0; }

本题可以优化，当两个数之和>=最大的一个数时，就不再进行判断了。

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int a[10005],b[10005]; int main() { int n,m=0; scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%d",&a[i]); sort(a+1,a+1+n);//先对输入的数进行排序 for(int i = 1; i <= n; ++i)//先让第一个数依次和第2-n个数相加，看结果是否有和集合中相同的数 { for(int j = i+1; j <= n; ++j) { for(int k = 1; k<= n; ++k) { if(a[i]+a[j]==a[k]) { b[++m]=a[k];//b数组中存储集合中存在与两个数之和 的值相等的数 } if(a[i]+a[j] > a[n]) break; } } } sort(b+1,b+1+m); //对集合b中的数进行排序 int l = m; for(int i = 1; i <= m; ++i)//由于相等的数可能重合，所以需要去重 { if(b[i] == b[i+1]) l--; } printf("%d",l); return 0; }

还有一种巧妙地解法，有点运用桶排序的思想

#include<iostream> #include<cstdio> using namespace std; int t[200005],g[200005];//t是桶，t[i]表示值为i的数在集合中两两相加出现了几次，g[i]表示值为i的数是否在集合中，1为在，0为不在 int n,a[105],ans; int main(){ cin>>n; for (int i=1;i<=n;i++){ cin>>a[i];//读入 g[a[i]]=1;//在集合中赋值为1 } for (int i=1;i<n;i++){//枚举 for (int j=i+1;j<=n;j++){ t[a[i]+a[j]]++;//被加出来了 } } for (int i=1;i<=200002;i++){ if (t[i]>0&&g[i]) ans++;//判断是否满足，满足ans++ } cout<<ans<<endl; return 0; }

noip2013 记数问题

链接：https://www.luogu.org/problem/P1980

题目描述

试计算在区间 11 到 nn的所有整数中，数字x(0 ≤ x ≤ 9)x(0≤x≤9)共出现了多少次？例如，在 11到1111中，即在 1,2,3,4,5,6,7,8,9,10,111,2,3,4,5,6,7,8,9,10,11 中，数字 11 出现了 44 次。

输入格式

22个整数n,xn,x，之间用一个空格隔开。

输出格式

11个整数，表示xx出现的次数。

输入输出样例

输入 #1复制

11 1

输出 #1复制

4

说明/提示

对于 100\%100%的数据，1≤ n ≤ 1,000,000,0 ≤ x ≤ 91≤n≤1,000,000,0≤x≤9。

#include<cstdio> int main() { int n,x,count=0; scanf("%d%d",&n,&x); for(int i = 1; i <= n; ++i) { int k = i,k1=0;//这里不能直接用i来计算，否则iwhile循环后一直是0，++i，i一直是1，就会无限循环下去 while(k>0)//拆分每一个数 { k1=k%10;//需要用k1来记录每次拆分的结果，不能直接用k=k%10,不然计算k=k/10时运算逻辑会出错 if(k1 == x) count++; k=k/10; } } printf("%d",count); return 0; }

noip2012 质因数分解

链接：https://www.luogu.org/problem/P1075

题目描述

已知正整数nn是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

一个正整数nn。

输出格式

一个正整数pp，即较大的那个质数。

输入输出样例

输入 #1复制

21

输出 #1复制

7

说明/提示

n\le 2\times 10^9n≤2×109

NOIP 2012 普及组 第一题

本题需要注意，如果是从n-1~2循环会超时，适合从小的开始运算起走。

#include<cstdio> #include<cmath> int main() { int n; scanf("%d",&n); for(int i = 2; i <= sqrt(n); ++i) { if(n%i==0) { printf("%d",n/i); return 0; } } return 0; }