2012-2018普及组第一题题解

noip2018 标题统计【题目描述】凯凯刚写了一篇美妙的作文请问这篇作文的标题中有多少个字符注意标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时空格和换行符不计算在内。【输入】输入文件只有一行一个字符串 s。【输出】输出文件只有一行包含一个整数即作文标题的字符数不含空格和换行符。【输入样例】234【输出样例】3【提示】【样例1说明】标题中共有 3 个字符这 3 个字符都是数字字符。【样例输入2】Ca 45【样例输出2】4解析gets()的头文件为#includestdio.h,它是C语言里面的函数。#includeiostream #includecstring #includestdio.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输入可能包含大、小写英文字母、数字字符、空格和行末换行符。【来源】Nonoip2017 成绩测试地址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\%20304090100×20%100×30%80×50%20304090。输入输出样例2说明牛牛的作业成绩是6060分小测成绩是9090分期末考试成绩是8080分总成绩是60 \times 20\%90 \times 30\%80 \times 50\%1227407960×20%90×30%80×50%12274079。数据说明对于30\%30%的数据AB0AB0。对于另外30\%30%的数据AB100AB100。对于100\%100%的数据0≤A,B,C≤1000≤A,B,C≤100且A,B,CA,B,C都是1010的整数倍。#includeiostream 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.2b*0.3c*0.5; return 0; }#includecstdio int main() { int a,b,c; scanf(%d%d%d,a,b,c); printf(%d,a*2/10b*3/10c*5/10); return 0; }注意用printf输出时不可以直接输出a*0.2b*0.3c*0.5这样结果一直是0.因为相当于a、b、c都是和0相乘。#includeiostream #includecstdio using namespace std; int main() { int a,b,c; scanf(%d%d%d,a,b,c); printf(%.0f,a*0.2b*0.3c*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×2958支需要花费的钱为2 \times 29 582×2958。实际上P老师会选择购买第三种包装这样需要买22份。虽然最后买到的铅笔数 量更多了为30 \times 2 6030×260支但花费却减少为27 \times 2 5427×254比第一种少。对于第二种包装虽然每支铅笔的价格是最低的但要够发必须买22份实际的花费达到了 30 \times 2 6030×260因此P老师也不会选择。所以最后输出的答案是5454。【子任务】子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难可以尝试 只解决一部分测试数据。每个测试点的数据规模及特点如下表上表中“整倍数”的意义为若为KK表示对应数据所需要的铅笔数量nn—定是每种包装铅笔数量的整倍数这意味着一定可以不用多买铅笔)。解析因为不允许将铅笔的包装拆开所以要买够至少n支铅笔最少需要花费的费用应该是全部都买一种铅笔时的最少费用只需要算出全部买一种铅笔时的费用然后输出3种费用中最少的费用即可。#includecstdio #includecmath #includeiostream 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枚金币后骑士会在之后的连续N1N1天里每天收到N1N1枚金币。请计算在前KK天里骑士一共获得了多少金币。输入格式一个正整数KK表示发放金币的天数。输出格式一个正整数即骑士收到的金币数。输入输出样例输入 #1复制6输出 #1复制14输入 #2复制1000输出 #2复制29820说明/提示【输入输出样例 1 说明】骑士第一天收到一枚金币第二天和第三天每天收到两枚金币第四、五、六天每天收到三枚金币。因此一共收到 1223331412233314 枚金币。对于 100\%100%的数据1 ≤ K ≤ 10,0001≤K≤10,000。解析本题相当于12345……n的变形形式此时sumsumi.只用一重循环即可解决。本题在这个的基础上多加一层循环处理每个数字出现的次数。#includecstdio int main() { int n,sum0,count0; bool flag 0; scanf(%d,n); for(int i 1; i n; i) { if(flag0) { for(int j 1; j i; j) { count; sumi; if(countn) //当到达n个数后就不再计算了 { flag 1; break; } } } } printf(%d,sum); return 0; }#includeiostream 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; }#includeiostream 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; }#includeiostream using namespace std; int main() { int k,sum0,day0,j1; cink; for(int i1;ik;i) { sumj; day; if(dayj) { j; day0; } } coutsum; }noip2014 珠心算测验链接https://www.luogu.org/problem/P2141题目描述珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练既能够开发智力又能够为日常生活带来很多便利因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合集合中的数各不相同然后要求学生回答其中有多少个数恰好等于集合中另外两个不同的数之和最近老师出了一些测验题请你帮忙求出答案。(本题目为2014NOIP普及T1)输入格式共两行第一行包含一个整数nn表示测试题中给出的正整数个数。第二行有nn个正整数每两个正整数之间用一个空格隔开表示测试题中给出的正整数。输出格式一个整数表示测验题答案。输入输出样例输入 #1复制4 1 2 3 4输出 #1复制2说明/提示【样例说明】由123,134123,134故满足测试要求的答案为22。注意加数和被加数必须是集合中的两个不同的数。【数据说明】对于100\%100%的数据3 ≤ n ≤ 1003≤n≤100测验题给出的正整数大小不超过10,00010,000。解析比如样例61 3 5 7 8 9此时输出结果为2.134 156 17818919103583710 3811 39125712 5813 59147816此时有8、9两个数是刚好等于集合中另外两个数的和。#includecstdio #includeiostream #includealgorithm using namespace std; int a[10005],b[10005]; int main() { int n,m0; scanf(%d,n); for(int i 1; i n; i) scanf(%d,a[i]); sort(a1,a1n);//先对输入的数进行排序 for(int i 1; i n; i)//先让第一个数依次和第2-n个数相加看结果是否有和集合中相同的数 { for(int j i1; j n; j) { for(int k 1; k n; k) { if(a[i]a[j]a[k]) { b[m]a[k];//b数组中存储集合中存在与两个数之和 的值相等的数 } } } } sort(b1,b1m); //对集合b中的数进行排序 int l m; for(int i 1; i m; i)//由于相等的数可能重合所以需要去重 { if(b[i] b[i1]) l--; } printf(%d,l); return 0; }本题可以优化当两个数之和最大的一个数时就不再进行判断了。#includecstdio #includeiostream #includealgorithm using namespace std; int a[10005],b[10005]; int main() { int n,m0; scanf(%d,n); for(int i 1; i n; i) scanf(%d,a[i]); sort(a1,a1n);//先对输入的数进行排序 for(int i 1; i n; i)//先让第一个数依次和第2-n个数相加看结果是否有和集合中相同的数 { for(int j i1; 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(b1,b1m); //对集合b中的数进行排序 int l m; for(int i 1; i m; i)//由于相等的数可能重合所以需要去重 { if(b[i] b[i1]) l--; } printf(%d,l); return 0; }还有一种巧妙地解法有点运用桶排序的思想#includeiostream #includecstdio using namespace std; int t[200005],g[200005];//t是桶t[i]表示值为i的数在集合中两两相加出现了几次g[i]表示值为i的数是否在集合中1为在0为不在 int n,a[105],ans; int main(){ cinn; for (int i1;in;i){ cina[i];//读入 g[a[i]]1;//在集合中赋值为1 } for (int i1;in;i){//枚举 for (int ji1;jn;j){ t[a[i]a[j]];//被加出来了 } } for (int i1;i200002;i){ if (t[i]0g[i]) ans;//判断是否满足满足ans } coutansendl; 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。#includecstdio int main() { int n,x,count0; scanf(%d%d,n,x); for(int i 1; i n; i) { int k i,k10;//这里不能直接用i来计算否则iwhile循环后一直是0ii一直是1就会无限循环下去 while(k0)//拆分每一个数 { k1k%10;//需要用k1来记录每次拆分的结果不能直接用kk%10,不然计算kk/10时运算逻辑会出错 if(k1 x) count; kk/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×109NOIP 2012 普及组 第一题本题需要注意如果是从n-1~2循环会超时适合从小的开始运算起走。#includecstdio #includecmath int main() { int n; scanf(%d,n); for(int i 2; i sqrt(n); i) { if(n%i0) { printf(%d,n/i); return 0; } } return 0; }