7-9 h0039. 平方数
平方数是一个整数，它的平方根也是一个整数。例如1、4、81是
一些平方数。给定两个数字a和b，请你在a和b之间(包括a和b)找出有多少平方数?
输入格式:
输入文件最多包含201行输入。每一行包含两个整数a和b (0<a≤
b≤100000)。输入以包含两个零的行结束。这一行不用处理。
输出格式:
每一行输入产生一行输出。这一行包含一个表示在a和b之间有多少个平方数(包括a和b)。
输入样例:
1 4 1 10 0 0
输出样例:
2 3
方法一： 前缀和
#include<bits/stdc++.h> using namespace std; const int N = 100100; int check(int x) { int r = pow(x,0.5); return r*r == x; } int a[N], l, r; int main() { for(int i=1; i<=100000; i++) if(check( i )) a[i] ++; for(int i=1; i<=100000; i++) a[i]+=a[i-1]; while(cin>>l>>r && l!=0&&r!=0) cout<<a[r] - a[l-1] << endl; return 0; }
方法二： 朴素做法
#include <bits/stdc++.h> using namespace std; int main() { int a,b; while(cin >> a >> b && a || b) { int cnt = 0; for(int i=a;i<=b;i++) { double x = sqrt(i); int y = (int)x * x; if(i == y) cnt ++; } cout << cnt << endl; } return 0; }
7-10 h0040. 丑数
丑陋数是指那些质因数只有2、3或5的数。序列
1、2、3、4、5、6、8、9、10、12、15、……
显示前11个丑陋的数字。按照惯例，包含1。
输入的每一行给出一个正整数n(1≤n≤1500), 编写程序求第 n 个丑数的值。
输入格式:
输入的每一行给出一个正整数n(1≤n≤1500), 以n=0为结束标志。
输出格式:
对每一组输入，在一行中输出第 n 个丑数的值。
输入样例:
1 2 5 0
输出样例:
1 2 5
#include<bits/stdc++.h> using namespace std; bool check( int x ) { while(x%2 == 0) x/=2; while(x%3 == 0) x/=3; while(x%5 == 0) x/=5; return x == 1; } vector<long long> res; void find(int x) { int a2=0, a3=0, a5=0, r; while(res[a2]*2 <= x) a2++; while(res[a3]*3 <= x) a3++; while(res[a5]*5 <= x) a5++; r = res[a2]*2<res[a3]*3 ? res[a2]*2:res[a3]*3; r = r<res[a5]*5 ? r:res[a5]*5; res.push_back( r ); } int n; int main() { for(int i=1; res.size()<=500; i++) if( check( i ) ) res.push_back(i); while(res.size() <= 1500) find( res.back() ); while( cin>>n && n!=0) cout << res[n-1] << endl; return 0; }
7-11 阶乘末尾0的个数
从输入中读取一个数n，求出n！中末尾0的个数。
输入格式:
输入有若干行。第一行上有一个整数m，指明接下来的数字的个数。然后是m行，每一行包含一个确定的正整数n，1<=n<=1000000000。
输出格式:
对输入行中的每一个数据n，输出一行，其内容是n！中末尾0的个数。
输入样例:
3 3 100 1024
输出样例:
0 24 253
#include<bits/stdc++.h> using namespace std; int T, n; int main() { cin >> T; while( T-- ) { int res=0; cin >> n; while(n/5){ res+=n/5; n/=5; } cout << res << endl; } return 0; }
7-12 2017Final 圆周率山
为了参加学校的社团风采展，怡山小学数学组的同学们决定画一座圆周率山，以宣传圆周率。
已知圆周率为：3.
1415926535 8979323846 2643383279 5028841971 6939937510
5820974944 5923078164 0628620899 8628034825 3421170679
8214808651 3282306647 0938446095 5058223172 5359408128
4811174502 8410270193 8521105559 6446229489 5493038196
输入格式:
输入山的高度，为一个不超过10的正整数。
输出格式:
以上尖下宽，左右对称的三角形形式，给出圆周率的前若干位（不含小数点）。注意：每行均以数字结尾，即数字右边无空格。
输入样例1:
1
输出样例1:
3
输入样例2:
4
输出样例2:
3 141 59265 3589793
#include<bits/stdc++.h> using namespace std; string s = {"314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"}; int n, k; int main() { cin >> n; int l = (2 * n - 1) / 2; for(int i = 1; i <= n; i ++ ) { for(int j = 1; j <= l + 1 - i; j ++ ) cout << " "; for(int j = 1; j <= 2 * i - 1; j ++ ,k ++ ) cout << s[k]; cout << endl; } return 0; }
7-13 h0057. 平衡
Iyo Kiffa Australis 女士有一个天平，但只有两种砝码可以用来称量一剂药物。例如，用 300 毫克和 700 毫克的砝码来测量 200 毫克阿司匹林，她就要将 1 个 700 毫克的砝码和药物放在天平的一边，并将 3 个 300 毫克的砝码放在天平的另一边，如图 1 所示。虽然她也可以将 4 个 300 毫克的砝码放和药物放在天平的一边，两个 700 毫克的砝码放在天平的另一边，如图 2 所示，但她不会选择这个方案，因为使用更多的砝码不太方便。
请您帮助 Iyo Kiffa Australis 女士，帮她计算要用多少的砝码
输入格式:
输入是一系列的测试用例。每个测试用例一行，给出 3 个用空格分隔的正整数 a, b 和 d ，并满足以下关系： a<=b ， a<=10000 ，b<=10000 ，而且 d<=50000 。本题设定，您可以使用 a 毫克和 b 毫克的砝码组合来称量 d 毫克；也就是说，您不需要考虑 “ 无解 ” 的情况。
输入结束由一行表示，该行给出 3 个由空格分隔的零。这一行不是测试用例。
输出格式:
输出由一系列的行组成，每行对应一个测试用例 (a, b, d) 。一个输出行给出两个由空格分隔的非负整数 x 和 y ，且 x 和 y 要满足以下三个条件：
• 使用 x 个 a 毫克的砝码和 y 个 b 毫克的砝码可以称量 d 毫克。
• 在满足上述条件的非负整数对中，砝码总数 (x + y) 最小。
• 在满足前两个条件的非负整数对中，砝码的总的质量 (ax + by) 最小。
• 输出中不能出现额外的字符（例如，额外的空格）。
输入样例:
700 300 200 500 200 300 500 200 500 275 110 330 275 110 385 648 375 4002 3 1 10000 0 0 0
输出样例:
1 3 1 1 1 0 0 3 1 1 49 74 3333 1
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL a,b,d,x,y; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x = 1, y = 0; return a; } LL d = exgcd(b, a%b, y, x); y -= a / b * x; return d; } int main() { while (cin >> a >> b >> d && a || b || b) { LL gcd = exgcd(a,b,x,y); LL dx = b / gcd; // 当特解x>0时 LL x1 = (x * d / gcd % dx + dx) % dx; // 将x降至最小且大于0 LL y1 = abs(d - a * x1) / b; LL dy = a / gcd; // 当特解y>0时 LL y2 = (y * d / gcd % dy + dy) % dy; // 将y降至最小且大于0 LL x2=abs(d-b*y2)/a; // 只有这两种情况 |x|+|y| 是最小的，若相等再判断下乘积即可 if(x1 + y1 > x2 + y2 || (x1 + y1 == x2 + y2 && a * x1 + b * y1 > a * x2 + b * y2)) { x1 = x2; y1 = y2; } cout << x1 << " " << y1 << endl; } return 0; }
7-14 机工士姆斯塔迪奥
在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里，BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。
你需要处理这个副本其中的一个机制：N×M 大小的地图被拆分为了 N×M 个 1×1 的格子，BOSS 会选择若干行或/及若干列释放技能，玩家不能站在释放技能的方格上，否则就会被击中而失败。
给定 BOSS 所有释放技能的行或列信息，请你计算出最后有多少个格子是安全的。
输入格式:
输入第一行是三个整数 N,M,Q (1≤N×M≤105，0≤Q≤1000)，表示地图为 N 行 M 列大小以及选择的行/列数量。
接下来 Q 行，每行两个数 Ti ,C i ，其中 Ti =0 表示 BOSS 选择的是一整行，Ti=1 表示选择的是一整列，Ci为选择的行号/列号。行和列的编号均从 1 开始。
输出格式:
输出一个数，表示安全格子的数量。
输入样例:
5 5 3 0 2 0 4 1 3
输出样例:
12
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int f1[N],f2[N]; int main() { int n,m,q; cin >> n >> m >> q; while(q -- ) { int a,b; cin >> a >> b; if(a == 0) f1[b] = 1; else f2[b] = 1; } int res = 0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!f1[i] && !f2[j]) res ++ ; } } cout << res; return 0; }
7-15 扫描与筛选
本题目要求编写程序，给出多个非空字符串，再给出一篇文章，统计每个字符串在文章中出现的次数（字母不分大小写）。然后按照字符串的出现次数降序输出，若字符串的出现次数相等，则按照字符串的字典序升序输出。所谓的“字符串”是指连续不含空格的非空字符串。
输入格式:
第一行首先输入一个N(≤10⁴),即字符串的数量，紧接着输入N个字符串，随后每一行输入一串字符。当读到某一行只有一个英文句子.时，输入结束，此行不算在文章内。
输出格式:
如果在文章当中没有出现任何一个给出的字符串输出“No string ever appeared”，否则每一行输出给出的字符串以及它出现的次数。
输入样例:
在这里给出一组输入。例如：
4 A for like look Can I buy you a drink? Actually I’d rather have the money. I’m a photographer. I’ve been look for a face like yours. I’m a plastic surgeon. I’ve been looking for a face like yours.
输出样例:
在这里给出相应的输出。例如：
A 5 for 2 like 2 look 1
#include<bits/stdc++.h> using namespace std; typedef pair<string,int> PII; bool cmp(PII x, PII y) { if(x.second!=y.second) return x.second > y.second; else return x.first < y.first; } string zhuang( string s ) { for(int i=0; s[i]; i++) if(s[i]>='A' && s[i]<='Z') s[i] = s[i]-'A'+'a'; return s; } map< string, string> id; map< string, int> q; vector< PII > w; string s; int N, F; int main() { cin >> N; while( N-- ) { cin >> s; q[s] = 0; id[zhuang(s)] = s; } getchar(); while(getline(cin,s) && s!=".") { s = zhuang( s ); int l = s.size(); for(int i=0; i<l; i++) { while(i<l && s[i]==' ') i++; int j = i; while(j<l && s[j]!=' ') j++; if(i < l ) { string r = s.substr( i, j-i); if(id.find(r)!=id.end()) q[id[r]] ++, F = 1; } i = j; } } for(auto i=q.begin(); i!=q.end(); i++) w.push_back({i->first,i->second}); sort( w.begin(), w.end(), cmp); for(int i=0; i<w.size()&&F; i++) cout<<w[i].first<<" "<<w[i].second<<endl; if(!F) cout<<"No string ever appeared"<<endl; return 0; }
7-16 插松枝
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：
每人手边有一只小盒子，初始状态为空。
每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。
输入格式：
输入在第一行中给出 3 个正整数：N（≤103 ），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。
随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。
输出格式：
每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
8 3 4 20 25 15 18 20 18 8 5
输出样例：
20 15 20 18 18 8 25 5
#include <bits/stdc++.h> using namespace std; stack<int>S; queue<int>Q; int n, m, k; int cnt, res, t; void init() // 初始化 { cnt = 0; res = 1010; } int main() { cin >> n >> m >> k; init(); while(n -- ) { int x; cin >> x; Q.push(x); } while(Q.size() || S.size()) { while(S.size() && cnt < k && S.top() <= res) // 栈不为空 { res = S.top(); S.pop(); if(cnt ++ ) cout << ' '; cout << res; } if(Q.size() && cnt < k) // 不超过最大数量 { if(Q.front() <= res) // 可以插入松针片 { res = Q.front(); Q.pop(); if(cnt ++ ) cout << ' '; cout << res; } else { if(S.size() == m) init(); // 栈满，初始化 else // 放入推送器 { S.push(Q.front()); Q.pop(); } } } else init(); if(cnt == k) init(); // 不能再插入了，初始化 if(cnt == 0) cout << endl; } return 0; }
