1.好人(vector)
题目描述
圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。
输入
多组数据，每组数据输入两个整数n，m 数据范围：1<=n,m<=10000
输出
对每组数据，输出一行，包括2n个大写字母，‘G’表示好人，‘B’表示坏人。
样例输入
2 3
2 4
样例输出
GBBG
BGGB
题解
#include<bits/stdc++.h> using namespace std; vector<int> table; int n, m; int main() { while (cin >> n >> m) { table.clear(); for (int i = 1; i <= 2 * n; i++) { table.push_back(i); } auto pos = table.begin(); int p = 0; for (int i = 0; i < n; i++) { p = (p + m - 1) % table.size(); pos = table.begin() + p; table.erase(pos); } p = 0; for (int i = 1; i <= 2 * n; i++) { if (p < table.size() && i == table[p]) { cout << "G"; p++; } else cout << "B"; } cout << "\n"; } }
2.赫夫曼树的构建(vector)
题目描述
Huffman树在编码中有着广泛的应用。 在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
重复步骤1，直到{pi}中只剩下一个数。 在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。 本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。 例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
(注：必须使用vector容器)
输入
输入的第一行包含一个正整数n（n<=100）。 接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59
题解
#include<bits/stdc++.h> using namespace std; int main() { int n, w; cin >> n; vector<int> tree; for (int i = 0; i < n; i++) { cin >> w; tree.push_back(w); } int ans = 0; while (tree.size() > 1) { int tmp = 0; auto p = min_element(tree.begin(), tree.end()); tmp += *p; tree.erase(p); p = min_element(tree.begin(), tree.end()); tmp += *p; tree.erase(p); ans += tmp; tree.push_back(tmp); } cout << ans << endl; return 0; }
3.城市名称处理（vector+泛型）
题目描述
用vector和泛型算法实现一个城市名称集合的处理
城市名称用拼音表示
输入
先输入多个城市名称，每个城市名称输入一行，以00作为结束符号，按输入顺序尾插入到vector中
接着输入一个城市名称，查询它是否在集合中并做相应输出，如果它不在集合还要插入vector
最后输入位置x,y，输出按输入顺序的第x个位置的城市, 再输出按字典序的第y个位置城市
输出
看输入说明和样例，其中城市查询，如果在集合则输出 xxx found，不在则输出xxx not found
样例输入
guangzhou
shanghai
beijing
shenzhen
00
dalian
3 3
样例输出
dalian not found
beijing
guangzhou
题解
#include<bits/stdc++.h> using namespace std; int main() { vector<string> a; string s = ""; while (s != "00") { getline(cin, s); if (s != "00") a.push_back(s); } getline(cin, s); int flag = 0; for (int i = 0; i < a.size(); i++) { if (a[i] == s) { flag = 1; break; } } if (!flag) { cout << s << " not found\n"; a.push_back(s); } else cout << s << " found\n"; int x, y; cin >> x >> y; x--; y--; cout << a[x] << endl; sort(a.begin(), a.end()); cout << a[y]; return 0; }
4.幸运数(vector)
题目描述
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。
首先从1开始写出自然数1,2,3,4,5,6,…
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除，变为：
1 _ 3 _ 5 _ 7 _ 9 …
把它们缩紧，重新记序，为：
1 3 5 7 9 … 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, …
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,…)
最后剩下的序列类似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …
（必须用vector容器）
输入
输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
输出
程序输出 位于m和n之间的幸运数的个数（不包含m和n）。
样例输入
1 20
样例输出
5
题解
#include<bits/stdc++.h> using namespace std; int main() { int num, n, m; vector<int> a; cin >> m >> n; a.clear(); a.push_back(0); for (int i = 1; i < n; i++) { a.push_back(i); } int stp = 2, sz = a.size(), pos = 0; auto p = a.begin(); while (1) { sz = a.size(); if (pos == 0) stp = a[2]; else stp = a[pos]; if (stp - 1 > a.size()) break; if (stp == 2) a.erase(p + 1); for (int i = 1; i * stp - i < a.size(); i++) { a.erase(p + stp * i - i); } pos++; } int cnt = 0; for (int i = 0; i < a.size(); i++) { if (m < a[i] && a[i] < n) cnt++; } cout << cnt; return 0; }
