vector
1：对称排序
你供职于由一群丑星作为台柱子的信天翁马戏团。你刚完成了一个程序编写，它按明星们姓名字符串的长度非降序（即当前姓名的长度至少与前一个姓名长度一样）顺序输出他们的名单。然而，你的老板不喜欢这种输出格式，提议输出的首、尾名字长度较短，而中间部分长度稍长，显得有对称性。老板说的具体办法是对已按长度排好序的名单逐对处理，将前者放于当前序列的首部，后者放在尾部。如输入样例中的第一个案例，Bo和Pat是首对名字，Jean和Kevin是第二对，余此类推。
输入格式:
输入包含若干个测试案例。每个案例的第一行含一个整数n（n>=1），表示名字串个数。接下来n行每行为一个名字串，这些串是按长度排列的。名字串中不包含空格，每个串至少包含一个字符。n=0为输入结束的标志。
输出格式:
对每一个测试案例，先输出一行“Set n”，其中n从1开始取值，表示案例序号。接着是n行名字输出，如输出样例所示。
输入样例:
7 Bo Pat Jean Kevin Claude William Marybeth 6 Jim Ben Zoe Joey Frederick Annabelle 5 John Bill Fran Stan Cece 0
输出样例:
SET 1 Bo Jean Claude Marybeth William Kevin Pat SET 2 Jim Zoe Frederick Annabelle Joey Ben SET 3 John Fran Cece Stan Bill
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; int main() { int n, cnt = 0; while (cin >> n && n) { cnt ++; cout << "SET " << cnt << endl; vector<string>ans; for (int i = 0; i < n; i ++ ) { string s; cin >> s; ans.push_back(s); } for (int i = 0; i < n; i += 2) cout << ans[i] << endl; if(n % 2 == 1) n --; for (int i = n - 1; i >= 1; i -= 2) cout << ans[i] << endl; } return 0; }
2：AcWing 791. 高精度加法
给定两个正整数（不含前导 0），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
输入样例：
12 23
输出样例：
35
#include <iostream> #include <vector> using namespace std; vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) return add(B, A); vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); auto C = add(A, B); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
3：AcWing 792. 高精度减法
给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤105
输入样例：
32 11
输出样例：
21
#include <iostream> #include <vector> using namespace std; bool cmp(vector<int> &A, vector<int> &B) { if (A.size() != B.size()) return A.size() > B.size(); for (int i = A.size() - 1; i >= 0; i -- ) if (A[i] != B[i]) return A[i] > B[i]; return true; } vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); vector<int> C; if (cmp(A, B)) C = sub(A, B); else C = sub(B, A), cout << '-'; for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
4：AcWing 793. 高精度乘法
给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000,
0≤B≤10000
输入样例：
2 3
输出样例：
6
#include <iostream> #include <vector> using namespace std; bool cmp(vector<int> &A, vector<int> &B) { if (A.size() != B.size()) return A.size() > B.size(); for (int i = A.size() - 1; i >= 0; i -- ) if (A[i] != B[i]) return A[i] > B[i]; return true; } vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); vector<int> C; if (cmp(A, B)) C = sub(A, B); else C = sub(B, A), cout << '-'; for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
5：AcWing 794. 高精度除法
给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0
输入样例：
7 2
输出样例：
3 1
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a; vector<int> A; int B; cin >> a >> B; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); int r; auto C = div(A, B, r); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl << r << endl; return 0; }
6：大数的乘法
输入一个大正整数和一个非负整数，求它们的积。
输入格式:
测试数据有多组，处理到文件尾。每组测试输入1个大正整数A（位数不会超过1000）和一个非负整数B（int范围）。
输出格式:
对于每组测试，输出A与B的乘积。
输入样例:
1 1 123 100 12345678910 8 123456789101234567891012345678910 7
输出样例:
1 12300 98765431280 864197523708641975237086419752370
出处:
ZJUTOJ 1027
说明:
原题的B是一位数，本题修改为int范围内的整数
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long LL; vector<LL> mul(vector<LL>&A, int b) { vector<LL>C; for (LL i = 0, t = 0; i < A.size() || t; i ++ ) { if(i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string s; LL b; while (cin >> s >> b) { vector<LL>A; for (int i = s.size() - 1; i >= 0; i -- ) A.push_back(s[i] - '0'); auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; } return 0; }
7：两个有序序列的中位数
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1 ,⋯,A N−1 的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。
输入格式:
输入分三行。第一行给出序列的公共长度N（0
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
5 1 3 5 7 9 2 3 4 5 6
输出样例1:
4
输入样例2:
6 -100 -10 1 1 1 1 -50 0 2 3 4 5
输出样例2:
1
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; int main() { int n; vector<int>ans; int x; cin >> n; while (cin >> x) ans.push_back(x); sort(ans.begin(), ans.end()); cout << ans[n - 1]; return 0; }
8：大整数乘法
求两个不超过200位的非负整数的积。
输入格式:
输入有多组测试数据，每组有两行，每行是一个不超过200位的非负整数，没有多余的前导0。
输出格式:
每个乘积一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
输入样例:
1 2 12345678900 98765432100
输出样例:
2 1219326311126352690000
#include <bits/stdc++.h> using namespace std; const int N = 1010; int ans[N]; int main() { string s1, s2; while (cin >> s1 >> s2) { memset(ans, 0, sizeof ans); vector<int>A, B; for (int i = s1.size() - 1; i >= 0; i -- ) A.push_back(s1[i] - '0'); for (int i = s2.size() - 1; i >= 0; i -- ) B.push_back(s2[i] - '0'); for (int i = 0; i < A.size(); i ++ ) for (int j = 0; j < B.size(); j ++ ) ans[i + j] += A[i] * B[j]; for (int i = 0; i < A.size() + B.size(); i ++ ) if(ans[i] > 9) { ans[i + 1] += ans[i] / 10; ans[i] %= 10; } int len = A.size() + B.size(); while (ans[len - 1 ] == 0 && len > 1) len --; for (int i = len - 1; i >= 0; i -- ) cout << ans[i]; cout << endl; } return 0; }
map
1：气球升起来
程序设计竞赛时，赛场升起各色气球多么激动人心呀！志愿者送气球忙得不亦乐乎，观战的某人想知道目前哪种颜色的气球送出最多。
输入格式:
测试数据有多组，处理到文件尾。每组数据先输入一个整数n（0
输出格式:
对于每组测试，输出出现次数最多的颜色。若出现并列的情况，则只需输出ASCII码值最小的那种颜色。
输入样例:
3 pink red pink
输出样例:
pink
#include <iostream> #include <map> #define x first #define y second using namespace std; int main() { int n; while (cin >> n) { map<string, int>mp; string s; int maxx = 0; for (int i = 0; i < n; i ++ ) { cin >> s; mp[s] ++; if(maxx < mp[s]) maxx = mp[s]; } for (auto p = mp.begin(); p != mp.end(); p ++ ) if(p -> y == maxx) { cout << p ->x << endl; break; } } return 0; }
2：统计英文单词个数
给出一篇英文文章，现在需要统计文章中出现英文单词的数量。
输入格式:
第一行一个T，代表数据组数
对于每组数据，第一行一个n，代表文章中单词的个数，其后n行每行一个只包含小写字母的长度为1到10的字符串
输出格式:
每组数据输出若干行，每行输出单词以及它出现的次数（中间空格隔开），不同单词按单词字典序从小到大输出
保证单词出现的总次数<=1e5
输入样例:
1 8 it is a pen it is a dog
输出样例:
a 2 dog 1 is 2 it 2 pen 1
#include <iostream> #include <map> #define x first #define y second using namespace std; int main() { int T; string s; map<string, int>mp; cin >> T; while (T -- ) { int n; scanf("%d", &n); while (n -- ) { cin >> s; mp[s] ++; } for (auto p = mp.begin(); p != mp.end(); p ++ ) cout << p->x << ' ' << p->y << endl; mp.clear(); } return 0; }
3：笨小猴
笨小猴的词汇量很少，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设max是单词中出现次数最多的字母的出现次数，min是单词中出现次数最少的字母的出现次数，如果max-min是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
输入格式:
一个单词，其中只可能出现小写字母，并且长度小于100。
输出格式:
共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出No Answer；
第二行是一个整数，如果输入单词是Lucky Word，输出max-min的值，否则输出0。
输入样例1:
error
输出样例1:
Lucky Word 2
输入样例2：
olympic
输出样例2:
No Answer 0
#include <iostream> #include <map> using namespace std; int f(int n) { if(n < 2) return 0; for (int i = 2; i <= n / i; i ++ ) if(n % i == 0) return 0; return 1; } int main() { string s; int maxx = 0, minn = 1e9; getline(cin, s); map<char, int>mp; for (auto c : s) mp[c] ++; for (auto c : s) { if(maxx < mp[c]) maxx = mp[c]; if(minn > mp[c]) minn = mp[c]; } int x = maxx - minn; if(!f(x)) cout << "No Answer" << endl << 0; else cout << "Lucky Word" << endl << x; return 0; }
4：sdut-Collection(Map)-1 读中国载人航天史，汇航天员数量，向航天员致敬
1986年，中国实施“863”计划，航天技术列入其中。以载人飞船开始起步，最终建成我国的空间站。 1992年9月21日，中国实施载人航天工程，并确定了三步走的发展战略：第一步，发射载人飞船，建成初步配套的试验性载人飞船工程。第二步，突破载人飞船和空间飞行器的交会对接技术，利用载人飞船技术改装、发射一个空间实验室。第三步，建造载人空间站。
在长期的奋斗中，我国航天工作者不仅创造了非凡的业绩，而且铸就了特别能吃苦、特别能战斗、特别能攻关、特别能奉献的载人航天精神。载人航天精神，是“两弹一星”精神在新时期的发扬光大，是我们伟大民族精神的生动体现，永远值得全党、全军和全国人民学习。
截至2021年4月，历任航天英雄名字如下：
杨利伟（神舟五号） 费俊龙、聂海胜（神舟六号） 翟志刚、景海鹏、刘伯明（神舟七号） 景海鹏、刘旺、刘洋（神舟九号） 聂海胜、张晓光、王亚平（神舟十号） 景海鹏、陈东（神舟十一号）
会编程的小伙伴们，请以他们姓名中的拼音字母排序，统计一下航天英雄们出征太空的次数，以实际行动向航天员们致敬！
输入格式:
每次航天飞船的编号为一行读入数据，分别读入每次飞上太空的航天英雄的姓名，名字中间有若干个空格分隔。
最后一行为“end“，表示输入结束。
输出格式:
以他们姓名中的拼音字母排序，统计航天英雄们出征太空的次数。
每位航天员占一行，航天员姓名与出征次数中间有一个空格。
输入样例:
YangLiWei杨利伟 FeiJunLong费俊龙 NieHaiSheng聂海胜 Zhaizhigang翟志刚 JingHaiPeng景海鹏 LiuBoMing刘伯明 JingHaiPeng景海鹏 LiuWang刘旺 LiuYang刘洋 NieHaiSheng聂海胜 Zhangxiaoguang张晓光 WangYaPing王亚平 JingHaiPeng景海鹏 ChenDong陈东
end
输出样例:
ChenDong陈东 1 FeiJunLong费俊龙 1 JingHaiPeng景海鹏 3 LiuBoMing刘伯明 1 LiuWang刘旺 1 LiuYang刘洋 1 NieHaiSheng聂海胜 2 WangYaPing王亚平 1 YangLiWei杨利伟 1 Zhaizhigang翟志刚 1 Zhangxiaoguang张晓光 1
#include <iostream> #include <map> #define x first #define y second using namespace std; int main() { string s; map<string, int>mp; while (cin >> s && s != "end") mp[s] ++; for (auto p = mp.begin(); p != mp.end(); p ++ ) cout << p->x << ' ' << p->y << endl; return 0; }
5：树种统计
随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。
输入格式:
输入首先给出正整数N（≤105），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（大小写不区分）。
输出格式:
按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，保留小数点后4位。
输入样例:
29 Red Alder Ash Aspen Basswood Ash Beech Yellow Birch Ash Cherry Cottonwood Ash Cypress Red Elm Gum Hackberry White Oak Hickory Pecan Hard Maple White Oak Soft Maple Red Oak Red Oak White Oak Poplan Sassafras Sycamore Black Walnut Willow
输出样例:
Ash 13.7931% Aspen 3.4483% Basswood 3.4483% Beech 3.4483% Black Walnut 3.4483% Cherry 3.4483% Cottonwood 3.4483% Cypress 3.4483% Gum 3.4483% Hackberry 3.4483% Hard Maple 3.4483% Hickory 3.4483% Pecan 3.4483% Poplan 3.4483% Red Alder 3.4483% Red Elm 3.4483% Red Oak 6.8966% Sassafras 3.4483% Soft Maple 3.4483% Sycamore 3.4483% White Oak 10.3448% Willow 3.4483% Yellow Birch 3.4483%
#include <iostream> #include <map> #define x first #define y second using namespace std; int main() { string s; map<string, int>mp; int n; scanf("%d", &n); getchar(); for (int i = 0; i < n; i ++ ) { getline(cin, s); mp[s] ++; } for (auto p = mp.begin(); p != mp.end(); p ++ ) { cout << p->x; printf(" %.4f%%\n",p->y * 100.0 / n); } return 0; }
