为准备浙江理工大学复试C语言程序设计机试，自己找的模拟练习题，需要的同学可自行挑选题目练习。
文章不含任何复试内容及题目，仅限模拟练习题。均为个人题解，有问题可以在评论区提出来，我会及时解答。
快速复习
C++算法之旅、03 语法篇 | 全内容 – 小能日记 – 博客园 (cnblogs.com)
C++算法之旅、04 基础篇 | 第一章 基础算法 – 小能日记 – 博客园 (cnblogs.com)
C++算法之旅、05 基础篇 | 第二章 数据结构 – 小能日记 – 博客园 (cnblogs.com)
C++算法之旅、06 基础篇 | 第三章 图论 – 小能日记 – 博客园 (cnblogs.com)
浙江工商大学复试_若无忧的博客-CSDN博客
暴力求解枚举
| 题目 | 地址 | |
|---|---|---|
| 例题2.1 | abc（清华大学复试上机题） | http://t.cn/E9WMRTE |
| 例题2.2 | 反序数（清华大学复试上机题） | http://t.cn/E9WBrut |
| 例题2.3 | 对称平方数1（清华大学复试上机题） | http://t.cn/E9lUYRn |
| 习题2.4 | 与7无关的数（北京大学复试上机题） | http://t.cn/E9lOOZQ |
| 习题2.5 | 百鸡问题（北京哈尔滨工业大学复试上机题） | http://t.cn/E9ldhru |
| 习题2.6 | old bill（上海交通大学复试上机题） | http://t.cn/E9jqijR |
2.1
#include using namespace std;int main() { for (int a = 0; a <= 9; a++) for (int b = 0; b <= 9; b++) for (int c = 0; c <= 9; c++) { // int x = a * 100 + b * 10 + c; // int y = b * 100 + c * 10 + c; if (a * 100 + b * 110 + 12 * c == 532) cout << a << " " << b << " " << c << endl; }}2.2
#include using namespace std;int main() { for (int i = 1000; i <= 1111; i++) { int k = 9 * i; if (k % 10 == i / 1000 && k / 10 % 10 == i / 100 % 10 && k / 100 % 10 == i / 10 % 10 && k / 1000 == i % 10) cout << i << endl; } return 0;}2.3
#include using namespace std;// 还有一种方式，计算相反数：每次截取x的个位加给res然后x/=10，res进位，直至x为0，返回resbool DC(int x) { string s = to_string(x); int n = s.size(); for (int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) return false; } return true;}int main() { for (int i = 0; i <= 256; i++) { if (DC(i * i)) cout << i << endl; } return 0;}2.4
#include using namespace std;int main() { int n; while (cin >> n) { int sum = 0; for (int i = 1; i <= n; i++) { if (i % 7 != 0 && i % 10 != 7) { sum += i * i; } } cout << sum << endl; } return 0;}2.5
#include using namespace std;int main() { int x, y, z; int n; while (cin >> n) { for (int x = 0; x <= 100; x++) for (int y = 0; y <= 100 - x; y++) for (int z = 0; z <= 100 - x - y; z++) if (5 * x + 3 * y + ceil(1.0 / 3 * z) <= n && x + y + z == 100) printf("x=%d,y=%d,z=%d\n", x, y, z); } return 0;}2.6
#include using namespace std;int main() { int n, x, y, z; while (cin >> n >> x >> y >> z) { bool flag = true; for (int i = 9; i >= 1; i--) { for (int j = 9; j >= 0; j--) { int k = i * 10000 + x * 1000 + y * 100 + z * 10 + j; if (k % n == 0) { cout << k / 10000 << " " << k % 10 << " " << k / n << endl; flag = false; break; } } if (!flag) break; } if (flag) cout << 0 << endl; } return 0;}模拟
| 题目 | 地址 | |
|---|---|---|
| 例题2.7 | 今年的第几天？（清华大学复试上机题） | http://t.cn/E9jXK5A |
| 例题2.8 | 打印日期（华中科技大学复试上机题） | http://t.cn/E9YP2a8 |
| 例题2.9 | 剩下的树（清华大学复试上机题） | http://t.cn/E9ufYo5 |
| 例题2.10 | XXX定律（浙江大学复试上机题） | http://t.cn/E937wDs |
| 习题2.11 | Grading（浙江大学复试上机题） | http://t.cn/E9rDPSq |
2.7
#include #include using namespace std;int days[2][12] = {{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};bool isLerpYear(int y) { if (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)) return true; else return false;}int main() { int y, m, d; while (cin >> y >> m >> d) { int state = 0; if (isLerpYear(y)) state = 1; int sum = 0; for (int i = 0; i < m - 1; i++) sum += days[state][i]; sum += d; cout << sum << endl; } return 0;}2.8
#include using namespace std;int days[2][12] = { {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},};bool isLerpYear(int y) { if (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)) return true; else return false;}int main() { int y, d; while (cin >> y >> d) { int state = 0; if (isLerpYear(y)) state = 1; int m = 0; for (; m days[state][m]; m++) { d -= days[state][m]; } printf("%04d-%02d-%02d\n", y, m + 1, d); } return 0;}2.9
#include using namespace std;int const N = 1e2 + 10;typedef pair PII;PII segs[N];int main() { int l, n; while (cin >> l >> n) { for (int i = 0; i > segs[i].first >> segs[i].second; if (segs[i].first > segs[i].second) swap(segs[i].first, segs[i].second); } sort(segs, segs + n); int sum = l + 1, start = segs[0].first, end = segs[0].second; for (int i = 0; i end) { sum -= (end - start + 1); start = segs[i].first; end = segs[i].second; } else if (segs[i].second > end) end = segs[i].second; } // 最后一段未减去 sum -= (end - start + 1); cout << sum << endl; } return 0;}2.10
#include using namespace std;int main() { int n; while (cin >> n) { int count = 0; while (n != 1) { count++; if (n % 2 == 0) n /= 2; else if (n % 2) n = (3 * n + 1) / 2; } cout << count << endl; } return 0;}2.11
#include using namespace std;void grade(int T, int G1, int G2, int G3, int GJ) { if (fabs(G1 - G2) <= T) { printf("%.1f\n", 1.0 * (G1 + G2) / 2); } else { if (fabs(G1 - G3) <= T && fabs(G1 - G3) <= T) { printf("%.1f\n", max(max(G1, G2), G3)); } else if (fabs(G1 - G3) <= T) { printf("%.1f\n", 1.0 * (G1 + G3) / 2); } else if (fabs(G2 - G3) > P >> T >> G1 >> G2 >> G3 >> GJ) { grade(T, G1, G2, G3, GJ); } return 0;}排序与查找排序
| 题目 | 地址 | |
|---|---|---|
| 例题3.1 | 排序（清华大学复试上机题） | http://t.cn/E9dLx5K |
| 例题3.2 | 成绩排序（清华大学复试上机题） | http://t.cn/E9d3ysv |
| 例题3.3 | 成绩排序2（清华大学复试上机题） | http://t.cn/E9gyHM1 |
| 习题3.4 | 特殊排序（华中科技大学复试上机题） | http://t.cn/E9gio39 |
| 习题3.5 | 整数奇偶排序（北京大学复试上机题） | http://t.cn/E9glPvp |
| 习题3.6 | 小白鼠排队（北京大学复试上机题） | http://t.cn/E9gXh9Z |
3.1
#include using namespace std;int main() { int n; int a[101]; while (cin >> n) { for (int i = 0; i > a[i]; sort(a, a + n); for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl; } return 0;}//所有基本的排序方法了，桶排序、基数排序暂不写了#includeusing namespace std;const int N = 110, MAX = 1e8;int a[N];int n;int h[N], idx;//heap_sort用int tmp[N];//merge_sort用int bkt[MAX];//counting_sort用void buble_sort(){ for(int i = 0; i < n - 1; i ++) for(int j = 0; j a[j+1]) swap(a[j], a[j + 1]); }}void quick_sort(int l, int r){ if(l>=r) return; int x = a[(l + r) / 2]; int i = l - 1, j = r + 1; while(i<j){ do i ++; while(a[i] x); if(i < j) swap(a[i], a[j]); } quick_sort(l, j); quick_sort(j+1, r);}void selection_sort(){ for(int i = 0; i < n - 1;i ++){ int min_pos = i; for(int j = i + 1; j < n; j ++) if(a[j]<a[min_pos]) min_pos = j; swap(a[i], a[min_pos]); }}void down(int u){ int t = u; if(u*2<=idx&&h[u*2]<h[t]) t = u*2; if(u*2+1<=idx&&h[u*2+1]<h[t]) t= u*2+1; if(t!=u){ swap(h[t], h[u]); down(t); }}void heap_sort(){ for(int i = 1; i 0; i --) down(i); for(int i = 0; i < n; i ++){ a[i] = h[1]; h[1] = h[idx--]; down(1); }}void insertion_sort(){ for(int i = 1; i =0 && a[j]>cur_idx; j --){ a[j+1] = a[j]; } a[j+1] = cur_idx; }}void binary_insertion_sort(){ for(int i = 1; i < n; i ++){ int cur_idx = a[i]; int l = 0, r = i - 1; while(l<r){ int mid = (l + r + 1) / 2; if(a[mid]cur_idx) l = -1; int j; for(j = i - 1; j>l ;j --) a[j+1] = a[j]; a[j+1] = cur_idx; }}void shell_sort(){ for(int gap = n/2; gap>=1; gap /= 2){ for(int i = gap; i =0 && a[j]>cur_idx; j -= gap){ a[j+gap] = a[j]; } a[j + gap] = cur_idx; } }}void merge_sort(int l, int r){ if(l>=r) return; int mid = (l + r) / 2; merge_sort(l, mid), merge_sort(mid + 1, r); int k = 0, i = l, j = mid + 1; while(i<=mid&&j<=r){ if(a[i]<=a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while(i<=mid) tmp[k++] = a[i++]; while(j<=r) tmp[k++] = a[j++]; for(int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];}void counting_sort(){ int max = 0; for(int i = 0 ; i max) max = a[i]; } int j = 0; for(int i = 0; i < max+1; i ++){ while(bkt[i]){ a[j++] = i; bkt[i]--; } }}int main(){ scanf("%d", &n); for(int i = 0; i < n; i ++) scanf("%d", &a[i]);// buble_sort();// quick_sort(0, n - 1);// selection_sort();// heap_sort();// insertion_sort();// binary_insertion_sort();// shell_sort();// merge_sort(0, n - 1); counting_sort(); for(int i = 0; i < n; i ++) printf("%d ", a[i]); return 0;}3.2
#include using namespace std;struct Student { int p; int q;} s[101];int main() { int n; cin >> n; for (int i = 0; i > s[i].p >> s[i].q; sort(s, s + n, [](Student x, Student y) { if (x.q == y.q) return x.p < y.p; else return x.q < y.q; }); for (int i = 0; i < n; i++) cout << s[i].p << " " << s[i].q << endl; return 0;}3.3
#include using namespace std;struct Student { string name; int score;};int mode;bool cmp(Student a, Student b) { if (mode == 0) return a.score > b.score; else return a.score > n) { cin >> mode; Student s[n]; for (int i = 0; i > s[i].name >> s[i].score; stable_sort(s, s + n, cmp); for (int i = 0; i < n; i++) cout << s[i].name << " " << s[i].score << endl; } return 0;}3.4
#include using namespace std;int n;int a[1010];int main() { while (cin >> n) { for (int i = 0; i > a[i]; sort(a, a + n); cout << a[n - 1] << endl; for (int i = 0; i < n - 1; i++) cout << a[i] << " "; if (n - 1 == 0) cout << -1; cout << endl; } return 0;}3.5
#include using namespace std;int main() { int a[10]; while (cin >> a[0]) { for (int i = 1; i > a[i]; sort(a, a + 10); for (int i = 9; i >= 0; i--) if (a[i] % 2) cout << a[i] << " "; for (int i = 0; i <= 9; i++) if (a[i] % 2 == 0) cout << a[i] << " "; cout << endl; } return 0;}3.6
#include using namespace std;struct Rat { int w; string color;} r[101];int main() { int n; while (cin >> n) { for (int i = 0; i > r[i].w >> r[i].color; sort(r, r + n, [](Rat x, Rat y) { return x.w > y.w; }); for (int i = 0; i < n; i++) cout << r[i].color << endl; } return 0;}查找
| 题目 | 地址 | |
|---|---|---|
| 例题3.7 | 找x（哈尔滨工业大学复试上机题） | http://t.cn/E9gHFnS |
| 例题3.8 | 查找（北京邮电大学复试上机题） | http://t.cn/E9g8aaR |
| 习题3.9 | 找最小数（北京邮电大学复试上机题） | http://t.cn/E9gekWa |
| 习题3.10 | 打印极值点下标（北京大学复试上机题） | http://t.cn/E9ehDw4 |
| 习题3.11 | 找位置（华中科技大学复试上机题） | http://t.cn/E9eh4jY |
3.7
#include using namespace std;int main() { int n, x, a[201]; while (cin >> n) { for (int i = 0; i > a[i]; cin >> x; int ans = -1; for (int i = 0; i < n; i++) if (a[i] == x) ans = i; cout << ans << endl; } return 0;}3.8 ⭐ map、二分
\(O(n)\)
#include using namespace std;int n, m;int main() { while (cin >> n) { unordered_map hash; for (int i = 0; i > x; hash[x] = true; } cin >> m; for (int i = 0; i > x; if (hash.find(x) != hash.end()) cout << "YES" << endl; else cout << "NO" << endl; } } return 0;}\(O(nlogn)\)
#include using namespace std;int n, m;int a[101], b;int main() { while (cin >> n) { for (int i = 0; i > a[i]; cin >> m; sort(a, a + n); for (int i = 0; i > b; if (binary_search(a, a + n, b)) cout << "YES" << endl; else cout << "NO" << endl; } } return 0;}3.9
#include using namespace std;typedef pair PII;bool compare(PII x, PII y) { if (x.first == y.first) return x.second < y.second; else return x.first > n) { for (int i = 0; i > a[i].first >> a[i].second; sort(a, a + n, compare); cout << a[0].first << " " << a[0].second << endl; } return 0;}3.10
#include using namespace std;int n;int a[101];int main() { while (cin >> n) { for (int i = 0; i > a[i]; for (int i = 0; i < n; i++) { if (i == 0) { if (a[i] != a[i + 1]) cout << i << " "; } else if (i == n - 1) { if (a[i] != a[i - 1]) cout << i < a[i + 1] && a[i] > a[i - 1] || a[i] < a[i + 1] && a[i] < a[i - 1]) cout << i << " "; } } cout << endl; } return 0;}3.11
#include using namespace std;vector arr[128];bool visited[128];void Init(string str) { // 将字符串所有字符统计一遍 for (int i = 0; i > str) { memset(arr, 0, sizeof arr); memset(visited, false, sizeof visited); // 初始化为没访问过 Init(str); for (int i = 0; i 1) { // 如果是没有访问过的字符 且 是重复的字符 for (int j = 0; j < arr[str[i]].size(); j++) { if (j == 0) { // 输出控制 printf("%c:%d", str[i], arr[str[i]][j]); } else { printf(",%c:%d", str[i], arr[str[i]][j]); } } printf("\n"); visited[str[i]] = true; // 置访问过 } } } return 0;}字符串
| 题目 | 地址 | |
|---|---|---|
| 例题4.1 | 特殊乘法（清华大学复试上机题） | http://t.cn/Ai8by9vW |
| 例题4.2 | 密码翻译（北京大学复试上机题） | http://t.cn/Ai8bGaIx |
| 例题4.3 | 简单密码（北京大学复试上机题） | http://t.cn/Ai8bih2z |
| 例题4.4 | 统计字符（浙江大学复试上机题） | http://t.cn/Ai8fvq4I |
| 例题4.5 | 字母统计（上海交通大学复试上机题） | http://t.cn/Ai8VB72e |
| 习题4.6 | skew数（北京大学复试上机题） | http://t.cn/Ai8IALKI |
| 习题4.7 | 单词替换（北京大学复试上机题） | http://t.cn/Ai8Iycp6 |
| 习题4.8 | 首字母大写（北京大学复试上机题） | http://t.cn/Ai8I2hco |
4.1
#include using namespace std;int sum(int n) { int sum = 0; while (n) { sum += n % 10; n /= 10; } return sum;}int main() { int a, b; while (cin >> a >> b) { cout << sum(a) * sum(b) << endl; } return 0;}4.2
#include using namespace std;// char change(char x) {// if (!(x >= 'a' && x = 'A' && x <= 'Z')) return x;// if (x == 'z')// return 'a';// else if (x == 'Z')// return 'A';// else// return (char)x + 1;// }int main() { string s; while (getline(cin, s)) { // for (int i = 0; i < s.size(); i++) s[i] = change(s[i]); for (int i = 0; i = 'A' && s[i] = 'a' && s[i] <= 'z') { s[i] = (s[i] - 'a' + 1) % 26 + 'a'; } } cout << s << endl; } return 0;}4.3
#include using namespace std;int main() { char a[30] = {'V', 'W', 'X', 'Y', 'Z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U'}; string s; while (getline(cin, s)) { if (s == "START" || s == "END" || s == "ENDOFINPUT") continue; for (int i = 0; i = 'A' && s[i] <= 'Z') s[i] = a[s[i] - 'A']; cout << s << endl; } return 0;}4.4
#include using namespace std;int main() { string s1, s2; while (getline(cin, s1), getline(cin, s2)) { int count[128] = {0}; for (int i = 0; i < s2.size(); i++) count[s2[i]]++; for (int i = 0; i < s1.size(); i++) cout << s1[i] << " " << count[s1[i]] << endl; } return 0;}4.5
#include using namespace std;int main() { string s; while (getline(cin, s)) { unordered_map hash; for (int i = 0; i < s.size(); i++) hash[s[i]]++; for (int i = 'A'; i <= 'Z'; i++) cout << (char)i << ":" << hash[i] << endl; } return 0;}4.6
#include using namespace std;int main() { string s; while (getline(cin, s)) { int sum = 0; int n = s.size(); for (int i = 0; i < s.size(); i++) { sum += (s[i] - '0') * (pow(2, n) - 1); n--; } cout << sum << endl; } return 0;}4.7 ⭐
先按空格将句子分成一个一个单词，这样就非常方便替换了。直接检查单词即可了
#include #include #include using namespace std; vector split(string &s){ int i = 0, j = 0; vector a; while (i < s.size()) { while (s[j] != ' ' && j > a >> b; auto res = split(s); for (int i = 0; i < res.size(); ++i) if (res[i] == a) cout << b << ' '; else cout << res[i] << ' '; return 0;}因为直接使用 find 的话不是单词也可能匹配到，所以在 a，b 前面加了空格，主要使用了 C++ 库函数的 erase(pos, len)，清除 pos 开始的长度为 len 的子串，insert(pos, b) 在 pos 位置插入字符串 b
#include #include using namespace std; int main(){ string s,a,b; getline(cin,s); getline(cin,a); getline(cin,b); s = " " + s + " "; a = " " + a + " "; b = " " + b + " "; int start; while(1){ start=s.find(a); if(start == string::npos) break; else{ s.erase(start,a.length()); s.insert(start,b); } } int n = s.size(); cout<<s.substr(1, n - 2); return 0;}4.8
#include using namespace std;// bool isK(char x) {// return x == ' ' || x == '\t' || x == '\r' || x == '\n' ||// x == '\0'; // 注意 \0// }int main() { string s; while (getline(cin, s)) { // for (int i = 0, j = 0; i < s.size() && j < s.size();) { // if (s[i] = 'a') s[i] -= 32; // while (!isK(s[j])) j++; // i = ++j; // } if (s[0] >= 'a' && s[0] <= 'z') s[0] -= 32; for (int i = 1; i = 'a' && s[i + 1] <= 'z') s[i + 1] -= 32; } } cout << s; } return 0;}数据结构 I
| 题目 | 地址 | |
|---|---|---|
| 例题5.1 | 完数与盈数（清华大学复试上机题） | http://t.cn/AiKEyQWW |
| 例题5.2 | 约瑟夫问题NO.2 | http://bailian.openjudge.cn/practice/3254 |
| 例题5.3 | Zero-complexity Transposition（上海交通大学复试上机题） | http://t.cn/AiKa20bt |
| 例题5.4 | 括号匹配问题 | http://ccnu.openjudge.cn/practice/1978/ |
| 习题5.5 | 堆栈的使用（吉林大学复试上机题） | http://t.cn/AiKKM6F6 |
5.1
#include using namespace std;vector ans1;vector ans2;int sum(int x) { int sum = 1; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { sum += i; if (x / i != i) sum += x / i; } } return sum;}int main() { for (int i = 2; i i) ans2.push_back(i); } cout << "E: "; for (auto c : ans1) cout << c << " "; cout << endl; cout << "G: "; for (auto c : ans2) cout << c << " "; cout << endl; return 0;}5.2
#include using namespace std;int main() { queue q; int n, p, m; while (cin >> n >> p >> m, n && p && m) { for (int i = 1; i <= n; i++) q.push(i); while (q.front() != p) { int t = q.front(); q.pop(); q.push(t); } int count = 1; while (!q.empty()) { if (count != m) { count++; int t = q.front(); q.pop(); q.push(t); } else if (count == m) { int t = q.front(); q.pop(); cout << t; if (!q.empty()) cout << ','; count = 1; } } cout << endl; } return 0;}5.3
#include using namespace std;int main() { int n; while (cin >> n) { stack stk; int x; for (int i = 0; i > x; stk.push(x); } while (!stk.empty()) { cout << stk.top() << " "; stk.pop(); } cout << endl; } return 0;}5.4 ⭐
#include using namespace std;int main() { string s; while (cin >> s) { stack stk; // ^ 动态实例化一个字符串，非常好的方法 string ans(s.size(), ' '); for (int i = 0; i < s.size(); i++) { if (s[i] == '(') stk.push(i); else if (s[i] == ')') { if (!stk.empty()) { stk.pop(); } else ans[i] = '?'; } } while (!stk.empty()) { ans[stk.top()] = '$'; stk.pop(); } cout << s << endl; cout << ans << endl; } return 0;}5.5
#include using namespace std;int main() { int n; while (cin >> n) { stack stk; char op; for (int i = 0; i > op; int x; if (op == 'P') { cin >> x; stk.push(x); } else if (op == 'O') { if (!stk.empty()) stk.pop(); } else if (op == 'A') { if (!stk.empty()) cout << stk.top() << endl; else cout << "E" << endl; } } } return 0;}数学问题进制转换
| 题目 | 地址 | |
|---|---|---|
| 例题6.1 | 二进制数（北京邮电大学复试上机题） | http://t.cn/AiCuKTOv |
| 例题6.2 | 进制转换（清华大学复试上机题） | http://t.cn/AiCuoPRO |
| 例题6.3 | 十进制与二进制（清华大学复试上机题） | http://t.cn/AiCuoHKg |
| 例题6.4 | 进制转换2（清华大学复试上机题） | http://t.cn/AiCuKG7E |
| 习题6.5 | 八进制（华中科技大学复试上机题） | http://t.cn/AiCu0lHe |
| 习题6.6 | 又一版A+B（浙江大学复试上机题） | http://t.cn/AiCuOSWv |
| 习题6.7 | 进制转换（北京大学复试上机题） | http://t.cn/AiCuig9B |
| 习题6.8 | 数制转换（北京大学复试上机题） | http://t.cn/AiCu6ne4 |
6.1
#include using namespace std;int main() { unsigned int n; while (cin >> n) { vector ans; while (n) { ans.push_back(n % 2); n /= 2; } reverse(ans.begin(), ans.end()); for (auto c : ans) cout << c; cout << endl; } return 0;}6.2 ⭐ 模拟竖式除法
#include using namespace std;string s;int main() { while (cin >> s) { int n = s.size(); vector ans; for (int i = 0; i < n;) { int remain = 0; for (int j = i; j = 0; i--) cout << ans[i]; cout << endl; } return 0;}6.3 ⭐
#include using namespace std;string convert(string s, int n, int m) { string ans = ""; int len = s.size(); for (int i = 0; i < len;) { int remain = 0; for (int j = i; j > s) { string temp = convert(s, 10, 2); string ans = convert(temp, 2, 10); reverse(ans.begin(), ans.end()); cout << ans << endl; } return 0;}6.4
#include #include #include using namespace std;int CharToInt(char c) { if (c >= '0' && c <= '9') { return c - '0'; // 数字型字符转数字 } else { return c - 'A' + 10; // 字符型字符转数字 }}char IntToChar(int target) { if (target < 10) { return target + '0'; } else { return target + 'a' - 10; }}long long ConvertM2T(string str, int current) { // current为当前需转换的目标的当前进制 long long number = 0; for (int i = 0; i < str.size(); ++i) { number *= current; number += CharToInt(str[i]); } return number;}void ConvertT2N(long long number, int target) { // target为目标进制 stack myStack; if (number == 0) { myStack.push('0'); } while (number != 0) { myStack.push(IntToChar(number % target)); number /= target; } while (!myStack.empty()) { printf("%c", myStack.top()); myStack.pop(); } printf("\n");}int main() { int m, n; while (cin >> m >> n) { string str; cin >> str; long long number = ConvertM2T(str, m); // 先转换成十进制 ConvertT2N(number, n); // 再将十进制转n进制 } return 0;}6.5
#include using namespace std;int main() { int n; while (cin >> n) { stack stk; if (n == 0) stk.push(0); while (n) { stk.push(n % 8); n /= 8; } while (!stk.empty()) { cout << stk.top(); stk.pop(); } cout << endl; } return 0;}6.6
#include using namespace std;string add(string s1, string s2) { string s; while (s1.size() > s2.size()) s2 = "0" + s2; while (s1.size() = 0; i--) { t = t + s1[i] + s2[i] - '0' - '0'; char c = t % 10 + '0'; s.insert(0, 1, c); t = t / 10; } if (t) { char c = t % 10 + '0'; s.insert(0, 1, c); t = t / 10; } return s;}string div(string s, int n) { int len = s.size(); string ans = ""; for (int i = 0; i < len;) { int remain = 0; for (int j = i; j > n >> s1 >> s2) { string temp = add(s1, s2); temp = div(temp, n); reverse(temp.begin(), temp.end()); cout << temp << endl; } return 0;}6.7
#include using namespace std;int main() { long long n; while (~scanf("%llx", &n)) { cout << n << endl; } return 0;}6.8
#include using namespace std;int charToInt(char c) { if (c >= '0' && c = 'a' && c = 0 && c <= 9) return c + '0'; else return c - 10 + 'A';}long long toD(string s, int n) { long long ans = 0; for (int i = 0; i > n >> s >> m) { long long temp = toD(s, n); string ans = toM(temp, m); reverse(ans.begin(), ans.end()); cout << ans << endl; } return 0;}最大公约数与最小公倍数
| 题目 | 地址 | |
|---|---|---|
| 例题6.9 | 最大公约数（哈尔滨工业大学复试上机题） | http://t.cn/AiCuWLTS |
| 例题6.10 | 最小公倍数 | |
| 习题6.11 | 最简真分数（北京大学复试上机题） | http://t.cn/AiCua2g8 |
6.9
最大公约数（公因数）用辗转相除法（欧几里得算法）
#include using namespace std;int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }int main() { int a, b; while (cin >> a >> b) { cout << gcd(a, b) << endl; } return 0;}6.10 ⭐
最大公因数和最小公倍数的积等于两个数的积
最大公因数×最小公倍数
=共同因数×（共同因数×两个数各自的独有因数）
=（共同因数×一个数独有因数）×（共同因数×另一个数独有因数）
=一个数×另一个数
=两个数的积
最小公倍数 = a * b / gcd(a,b)
6.11
最简分数，是分子、分母只有公因数1的分数，或者说分子和分母互质的分数，又称既约分数
真分数,指的是分子比分母小的分数
#include using namespace std;int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }int main() { int n; while (cin >> n) { if (n == 0) return 0; vector a; for (int i = 0; i > x; a.push_back(x); } sort(a.begin(), a.end()); int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (gcd(a[i], a[j]) == 1) count++; } } cout << count << endl; } return 0;}质数
| 题目 | 地址 | |
|---|---|---|
| 例题6.12 | 素数判定（哈尔滨工业大学复试上机题） | http://t.cn/AiCuWE0Q |
| 例题6.13 | 素数 | http://t.cn/AiCulqtW |
| 习题6.14 | Prime Number（上海交通大学复试上机题） | http://t.cn/AiCulrSh |
6.12
#include using namespace std;bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i > n) { if (isPrime(n)) cout << "yes" << endl; else cout << "no" << endl; } return 0;}6.13
#include using namespace std;bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i > n) { for (int i = 2; i < n; i++) { if (i % 10 == 1 && isPrime(i)) cout << i << " "; } cout << endl; } return 0;}6.14
#include using namespace std;bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) return false; } return true;}int const N = 1e4 + 10;int ans[N];int main() { int idx = 1, i = 2; while (idx > n) { cout << ans[n] << endl; } return 0;}分解质因素
| 题目 | 地址 | |
|---|---|---|
| 例题6.15 | 质因数的个数（清华大学复试上机题） | http://t.cn/Aip7J0Oo |
| 习题6.16 | 约数的个数（清华大学复试上机题） | http://t.cn/Aip7dTUp |
6.15 ⭐
#include using namespace std;int main() { int n; while (cin >> n) { int cnt = 0; for (int i = 2; i 1) cnt++; cout << cnt << endl; } return 0;}6.16
#include using namespace std;int main() { int n; while (cin >> n) { for (int i = 0; i > x; vector primes; for (int k = 2; k 1) primes.push_back(1); int res = 1; for (auto c : primes) res *= (c + 1); cout << res << endl; } } return 0;}快速幂
| 题目 | 地址 | |
|---|---|---|
| 例题6.17 | 快速幂 | https://www.nowcoder.com/share/jump/7523383881696517430391 |
6.17
算法学习笔记(4)：快速幂 – 知乎 (zhihu.com)
取模常用公式
一 . (a+b)mod n = ((a mod n)+(b mod n) mod n
二 . (a-b)mod n = ((a mod n)-(b mod n)+n) mod n
三 . ab mod n = (a mod n)(b mod n) mod n
#include using namespace std;long long a, b, p;long long qpow(long long x, long long n) { if (n == 0) return 1; else if (n % 2 == 0) { long long temp = (qpow(x, n / 2) % p); return temp * temp; } else { return (qpow(x, n - 1) % p) * (x % p); }}int main() { int n; cin >> n; while (n--) { cin >> a >> b >> p; cout << (qpow(a, b) % p) << endl; } return 0;}矩阵快速幂
没刷
高精度整数
没刷
贪心
| 题目 | 地址 | |
|---|---|---|
| 例题7.1 | 鸡兔同笼（北京大学复试上机题） | http://t.cn/E9ewERU |
另外可做一下区间贪心题（如区间合并，区间选择等）
7.1
#include using namespace std;int main() { int n; while (cin >> n) { if (n % 2 != 0) cout << "0 0" << endl; else { int a = n / 4; int b = (n - a * 4) / 2; cout << a + b; cout << " "; cout << n / 2 << endl; } } return 0;}递归与分治递归
| 题目 | 地址 | |
|---|---|---|
| 例题8.1 | n的阶乘（清华大学复试上机题） | http://t.cn/Ai0ocOUY |
| 例题8.2 | 汉诺塔 | https://www.nowcoder.com/questionTerminal/84ce91c6099a45dc869355fa1c4f589d |
| 例题8.3 | 汉诺塔 | https://leetcode.cn/problems/hanota-lcci/description/ |
| 习题8.4 | 杨辉三角形（西北工业大学复试上机题） | https://www.nowcoder.com/share/jump/7523383881696451582920 |
| 习题8.5 | 全排列（北京大学复试上机题） | http://t.cn/Ai0K0hXZ |
8.1
#include using namespace std;long long jie(int n) { if (n == 1) return 1; else return n * jie(n - 1);}int main() { int n; while (cin >> n) { cout << jie(n) << endl; } return 0;}8.2
- n = 1 时
- 直接把盘子从 A 移到 C
- n > 1 时
- 先把上面 n – 1 个盘子从 A 通过 C 移到 B（子问题，递归）
- 再将最大的盘子从 A 移到 C （此时 A 空）
- 再将 B 上 n – 1 个盘子从 B 通过 A 移到 C（子问题，递归）
#include using namespace std;void move(int n, char* pos1, char* pos3) { printf("Move %d from %s to %s\n", n, pos1, pos3);}void Hanoi(int n, char* pos1, char* pos2, char* pos3) { // 如果是1个盘子，直接从起始柱A移动到目标柱C if (n == 1) move(n, pos1, pos3); else { // 如果盘子大于1个，需要把n-1个盘子，从起始柱pos1，通过目标柱pos3，移动到中转柱pos2 Hanoi(n - 1, pos1, pos3, pos2); // 此时pos1上的n-1个盘子全部移动pos2上去了，那么可以直接把pos1上剩下的1个盘子，直接移动到pos3上 move(n, pos1, pos3); // 把pos2剩下的n-1个盘子，通过中转位置pos1，移动到目标位置pos3 Hanoi(n - 1, pos2, pos1, pos3); }}int main() { int n; while (cin >> n) { char* pos1 = "left"; char* pos2 = "mid"; char* pos3 = "right"; Hanoi(n, pos1, pos2, pos3); } return 0;}8.3
class Solution {public: void hanota(vector& A, vector& B, vector& C) { int n = A.size(); move(n, A, B, C); } void move(int n, vector& A, vector& B, vector& C){ if (n == 1){ C.push_back(A.back()); A.pop_back(); return; } move(n-1, A, C, B); // 将A上面n-1个通过C移到B C.push_back(A.back()); // 将A最后一个移到C A.pop_back(); // 这时，A空了 move(n-1, B, A, C); // 将B上面n-1个通过空的A移到C }};8.4
没用到递归
#include using namespace std;int main() { int n = 0; int arr[30][30] = {0}; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { if (0 == j || i == j) { arr[i][j] = 1; } else { arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; } printf("%5d", arr[i][j]); } printf("\n"); } return 0;}8.5 ⭐
比如这里所说的全排列{“a”,”b”,”c”,”d”};
1。首先四个字母的全排列可以被简化成分别以”a”、”b”、”c”、”d”打头，加上剩下三个字母的全排列；
2。以此类推，上一步中的每一个三个字母的全排列，又可以被简化为分别以三个字母打头，加上剩下两个字母的全排列
3。重复前面的简化过程，直到只剩一个字母的时候，就很容易了处理了，因为一个字母的全排列太显而易见了
另外注意：用了map而不是vector。因为递归只能找出所有的排列，并不能保证是按照字典序排序的。所有用map，map底层是红黑树，内部仍然是有序的
#include using namespace std;string s;map mp;void dfs(int now) { if (now == s.size()) mp[s] = 1; else { // now 下标字母选哪个开头 for (int i = now; i > s; dfs(0); for (auto c : mp) { cout << c.first << endl; } return 0;}#include using namespace std;string s;int main() { cin >> s; sort(s.begin(), s.end()); do { cout << s << endl; } while (next_permutation(s.begin(), s.end())); return 0;}全排列函数
头文件 #include
next_permutation：求下一个排列组合
- 函数模板：next_permutation(arr, arr+size);
- 参数说明：
arr： 数组名
size：数组元素个数 - 函数功能： 返回值为bool类型，当当前序列不存在下一个排列时，函数返回false，否则返回true，排列好的数在数组中存储
- 注意：在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。比如，如果数组num初始化为2,3,1，那么输出就变为了：{2 3 1}
prev_permutation：求上一个排列组合
- 函数模板：prev_permutation(arr, arr+size);
- 参数说明：
arr： 数组名
size：数组元素个数 - 函数功能： 返回值为bool类型，当当前序列不存在上一个排列时，函数返回false，否则返回true]
- 注意：在使用前需要对欲排列数组按降序排序，否则只能找出该序列之后的全排列数。
string s;while (getline(cin, s)) { sort(s.begin(), s.end()); do { cout << s << endl; } while (next_permutation(s.begin(), s.end())); cout << endl;}for (int i = 0; i > a[i];sort(a, a + n);do{ for (int i = 0; i < n; i++)cout << a[i]; cout << endl;} while (next_permutation(a, a + n));cout << endl;分治
| 题目 | 地址 | |
|---|---|---|
| 例题8.6 | Fibonacci（上海交通大学复试上机题） | http://t.cn/Ai0K3tU5 |
| 例题8.7 | 二叉树（北京大学复试上机题） | http://t.cn/Ai0Ke6I0 |
8.6
#include using namespace std;int f(int n) { if (n == 0) return 0; if (n == 1) return 1; return f(n - 1) + f(n - 2);}int main() { int n; while (cin >> n) { cout << f(n) << endl; } return 0;}8.7
#include using namespace std;int n, m;int dfs(int n) { if (n > m) return 0; return 1 + dfs(2 * n) + dfs(2 * n + 1);}int main() { while (cin >> n >> m) { if (n == 0 && m == 0) return 0; cout << dfs(n) << endl; } return 0;}搜索
| 题目 | 地址 | |
|---|---|---|
| 习题9.1 | 玛雅人的密码 | http://t.cn/Ai0lUhJj |
| 习题9.2 | 神奇的口袋（北京大学复试上机题） | http://t.cn/Ai0u0GUz |
| 习题9.3 | 八皇后（北京大学复试上机题） | http://t.cn/Ai0uOazs |
9.1
#include using namespace std;struct str { int count; // 记录移动次数（为什么要加？答：因为bfs队列一直在循环，不清楚排队的兄弟经过了几次字符移动） string s;};bool check(string s) { if (s.find("2012") != string::npos) return true; else return false;}int fact(int l) { if (l == 0) return 1; else return l * fact(l - 1);}queue q;int _count = -1;void bfs(str s, int len) { q.push(s); int flag = 0; // 记录排队数，全排列后还没跳出，说明无解，撤退之 // BFS主体 while (!q.empty()) { if (flag++ > fact(len)) return; // 取队首检查之 str temp = q.front(); q.pop(); if (check(temp.s) == true) { _count = temp.count; return; } // 字符移动并入队 for (int i = 0; i > len; str _str; cin >> _str.s; _str.count = 0; bfs(_str, len); cout << _count << endl; system("pause"); return 0;}9.2
01背包问题，有递归和非递归写法
#include using namespace std;int f[41];int n;int main() { f[0] = 1; cin >> n; for (int i = 1; i > x; for (int j = 40; j >= x; j--) f[j] = f[j] + f[j - x]; } cout << f[40] << endl; return 0;}#include using namespace std;int v[25];int n;int dfs(int j, int i) { if (j n) return 0; // ^ 后执行 return dfs(j, i + 1) + dfs(j - v[i], i + 1);}int main() { cin >> n; for (int i = 1; i > v[i]; } cout << dfs(40, 1) << endl; return 0;}9.3 ⭐
col、dg、udg 代表列、主对角线、副对角线（减少了判断）
#include using namespace std;vector<vector> ans;vector path(8, 0);bool col[9], dg[2 * 9 - 1], udg[2 * 9 - 1];void dfs(int n) { if (n == 8) { ans.push_back(path); return; } for (int i = 1; i > n) { for (auto c : ans[n - 1]) cout << c; cout << endl; } return 0;}数据结构 II优先队列
| 题目 | 地址 | |
|---|---|---|
| 例题10.1 | 复数集合（北京邮电大学复试上机题） | http://t.cn/Ai98yYlt |
| 例题10.2 | 哈夫曼树（北京邮电大学复试上机题） | http://t.cn/AiCuGMki |
| 习题10.3 | 查找第K小的数（北京邮电大学复试上机题） | http://t.cn/AiCu5hcK |
| 习题10.4 | 搬水果（吉林大学复试上机题） | http://t.cn/AiCu5nsQ |
10.1
#include using namespace std;struct Complex { int a; // 实部 int b; // 虚部 bool operator<(const Complex &w) const { return a * a + b * b < w.a * w.a + w.b * w.b; };};int main() { int n; priority_queue queue; cin >> n; for (int i = 0; i > action; if (action == "Pop") { if (queue.empty()) { printf("empty\n"); } else { printf("%d+i%d\n", queue.top().a, queue.top().b); queue.pop(); printf("SIZE = %d\n", queue.size()); } } else if (action == "Insert") { int re, im; scanf("%d+i%d", &re, &im); // 格式化读取 Complex c; queue.push({re, im}); printf("SIZE = %d\n", queue.size()); } } return 0;}10.2 ⭐
数据结构——哈夫曼树（Huffman Tree） – 知乎 (zhihu.com)
#include using namespace std;int main() { int n; cin >> n; priority_queue<int, vector, greater> que; for (int i = 0; i > num; que.push(num); } int res = 0; while (que.size() > 1) { int a = que.top(); que.pop(); int b = que.top(); que.pop(); res += a + b; que.push(a + b); } printf("%d", res);}10.3
#include using namespace std;int main() { int n; while (cin >> n) { priority_queue<int, vector, greater> heap; for (int i = 0; i > x; heap.push(x); } int count; cin >> count; int res; for (int k = 1; k <= count; k++) { res = heap.top(); while (!heap.empty() && heap.top() == res) heap.pop(); } cout << res << endl; } return 0;}10.4
#include using namespace std;int main() { int n; while (cin >> n) { if (n == 0) return 0; priority_queue<int, vector, greater> heap; for (int i = 1; i > x; heap.push(x); } long long res = 0; while (heap.size() != 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); res += a + b; heap.push(a + b); } cout << res << endl; } return 0;}哈希表
| 题目 | 地址 | |
|---|---|---|
| 例题10.5 | 查找学生信息（清华大学复试上机题） | http://t.cn/AiCuVIuY |
| 例题10.6 | 字串计算（北京大学复试上机题） | http://t.cn/AiCuJtI5 |
| 习题10.7 | 统计同成绩学生人数（浙江大学复试上机题） | http://t.cn/AiCuM7nj |
| 习题10.8 | 开门人和关门人(浙江大学复试上机题) | http://t.cn/AiCuM09f |
| 习题10.9 | 谁是你的潜在朋友（北京大学复试上机题） | http://t.cn/AiCux4f7 |
10.5
#include using namespace std;struct Student { string name; string gender; int year;};int main() { unordered_map hash; int n; cin >> n; for (int i = 0; i > a >> b >> c >> d; hash[a] = {b, c, d}; } cin >> n; for (int i = 0; i > a; if (hash.find(a) == hash.end()) cout << "No Answer!" << endl; else cout << a << " " << hash[a].name << " " << hash[a].gender << " " << hash[a].year << endl; } return 0;}10.6
#include using namespace std;int main() { string s; while (cin >> s) { map hash; for (int i = 0; i < s.size(); i++) for (int j = i; j 1) cout << c.first << " " << c.second << endl; } return 0;}10.7
#include using namespace std;int main() { int n; while (cin >> n) { if (n == 0) return 0; unordered_map hash; for (int i = 0; i > x; hash[x]++; } int y; cin >> y; cout << hash[y] << endl; } return 0;}10.8
#include using namespace std; int main(){ int n; while(cin >> n){ string id, signIn, signOut; string openId, closeId; string signInTime = "24:00:00", signOutTime = "00:00:00"; for(int i = 0; i > id >> signIn >> signOut; if(signIn signOutTime){ signOutTime = signOut; closeId = id; } } cout << openId << " " << closeId << endl; } return 0;}- map以红黑树实现：字典序
- 迭代器可以++、–，但不支持+1
#include#include#include10.9
#include using namespace std;int main() { int n, m; while (cin >> n >> m) { // 书编号、人数 unordered_map book; vector record; for (int i = 0; i > x; book[x]++; record.push_back(x); } for (int i = 0; i 1) cout << book[record[i]] - 1 << endl; else cout << "BeiJu" << endl; } } return 0;}二叉树
https://www.cnblogs.com/linxiaoxu/p/17753583.html#二叉树
二叉排序树
没刷，建议自己找题目刷一下
图论并查集
| 题目 | 地址 | |
|---|---|---|
| 例题11.1 | 畅通工程（浙江大学复试上机题） | http://t.cn/AiOvBHj9 |
| 例题11.2 | 连通图（吉林大学复试上机题） | http://t.cn/AiO77VoA |
| 习题11.3 | 第一题（上海交通大学复试上机题） | http://t.cn/AiOhkgMJ |
11.1
#include using namespace std;int const N = 1e3 + 10;int p[N];int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];}int n, m;int main() { while (cin >> n >> m) { for (int i = 1; i <= n; i++) p[i] = i; for (int i = 0; i > a >> b; // ^ 合并的时候是大类合并，不是两个节点合并 int fa = find(a), fb = find(b); if (fa != fb) p[fa] = fb; } int count = -1; for (int i = 1; i <= n; i++) { if (find(i) == i) count++; } cout << count << endl; } return 0;}11.2
#include using namespace std;int const N = 1010;int p[N];int find(int x) { if (x != p[x]) p[x] = find(p[x]); return p[x];}int n, m;int main() { while (cin >> n >> m) { if (n == 0 && m == 0) break; for (int i = 1; i <= n; i++) p[i] = i; for (int i = 1; i > a >> b; int fa = find(a), fb = find(b); if (fa != fb) p[fa] = fb; } int root = find(1); int i; for (i = 1; i <= n; i++) { if (find(i) != root) break; } if (i == n + 1) cout << "YES" << endl; else cout << "NO" << endl; } return 0;}11.3
#include using namespace std;unordered_map p;int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];}int main() { int a, b; while (cin >> a >> b) { // 第一次访问节点，初始化操作 if (p.find(a) == p.end()) p[a] = a; if (p.find(b) == p.end()) p[b] = b; int fa = find(a); int fb = find(b); if (fa != fb) p[fa] = fb; } int count = 0; for (auto c : p) if (c.first == c.second) count++; cout << count << endl; return 0;}最小生成树
https://www.cnblogs.com/linxiaoxu/p/17679355.html#最小生成树
最短路径
https://www.cnblogs.com/linxiaoxu/p/17679355.html#最短路
拓扑排序
https://www.cnblogs.com/linxiaoxu/p/17679355.html#有向图的拓扑序列
关键路径
没刷
动态规划递归求解
| 题目 | 地址 | |
|---|---|---|
| 例题12.1 | N阶楼梯上楼问题（华中科技大学复试上机题） | http://t.cn/Aij9Fr3V |
| 习题12.2 | 吃糖果（北京大学复试上机题） | http://t.cn/AiQsVyKz |
12.1
#include using namespace std;int f[100];int main() { int n; while (cin >> n) { f[0] = 1; for (int i = 1; i = 0) f[i] += f[i - 2]; } cout << f[n] << endl; } return 0;}12.2
#include using namespace std;int f[100];int main() { int n; while (cin >> n) { f[0] = 1; for (int i = 1; i = 0) f[i] += f[i - 2]; } cout << f[n] << endl; } return 0;}背包问题
https://www.cnblogs.com/linxiaoxu/p/17694869.html#背包dp