为准备浙江理工大学复试C语言程序设计机试，自己找的模拟练习题，需要的同学可自行挑选题目练习。

文章不含任何复试内容及题目，仅限模拟练习题。均为个人题解，有问题可以在评论区提出来，我会及时解答。

快速复习

C++算法之旅、03 语法篇 | 全内容 - 小能日记 - 博客园 (cnblogs.com)

C++算法之旅、04 基础篇 | 第一章 基础算法 - 小能日记 - 博客园 (cnblogs.com)

C++算法之旅、05 基础篇 | 第二章 数据结构 - 小能日记 - 博客园 (cnblogs.com)

C++算法之旅、06 基础篇 | 第三章 图论 - 小能日记 - 博客园 (cnblogs.com)

浙江工商大学复试_若无忧的博客-CSDN博客

暴力求解

枚举

2.1

#include <bits/stdc++.h>

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 <bits/stdc++.h>

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 <bits/stdc++.h>

using namespace std;

// 还有一种方式，计算相反数：每次截取x的个位加给res然后x/=10，res进位，直至x为0，返回res
bool 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 <bits/stdc++.h>

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 <bits/stdc++.h>

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 <bits/stdc++.h>

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

#include <cstdio>
#include <iostream>

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 <bits/stdc++.h>

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 < 11 && d > days[state][m]; m++) {
            d -= days[state][m];
        }
        printf("%04d-%02d-%02d\n", y, m + 1, d);
    }
    return 0;
}

2.9

#include <bits/stdc++.h>

using namespace std;

int const N = 1e2 + 10;

typedef pair<int, int> PII;
PII segs[N];

int main() {
    int l, n;
    while (cin >> l >> n) {
        for (int i = 0; i < n; i++) {
            cin >> 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 < n; i++) {
            if (segs[i].first > 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 <bits/stdc++.h>

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 <bits/stdc++.h>
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) <= T) {
            printf("%.1f\n", 1.0 * (G2 + G3) / 2);
        } else {
            printf("%.1f\n", GJ);
        }
    }
}

int main() {
    int P, T, G1, G2, G3, GJ;
    while (cin >> P >> T >> G1 >> G2 >> G3 >> GJ) {
        grade(T, G1, G2, G3, GJ);
    }
    return 0;
}

排序与查找

排序

3.1

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    int a[101];
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << endl;
    }
    return 0;
}

//所有基本的排序方法了，桶排序、基数排序暂不写了
#include<iostream>
using 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 < n - 1 - i; j ++){
            if(a[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);
        do j --; while(a[j] > 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 <= n; i ++) h[i] = a[i-1];
    idx = n;
    for(int i = idx/2; 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 < n; i ++){
        int cur_idx = a[i];
        int j;
        for(j = i-1; j >=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 = mid;
            else r = mid - 1;
        }
        if(a[l]>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 < n; i ++){
            int cur_idx = a[i];
            int j;
            for(j = i - gap; j>=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 < n; i ++){
        bkt[a[i]]++;
        if(a[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 <bits/stdc++.h>

using namespace std;

struct Student {
    int p;
    int q;
} s[101];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> 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 <bits/stdc++.h>

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 < b.score;
}
int main() {
    int n;
    while (cin >> n) {
        cin >> mode;
        Student s[n];
        for (int i = 0; i < n; i++) cin >> 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 <bits/stdc++.h>

using namespace std;

int n;
int a[1010];

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int a[10];
    while (cin >> a[0]) {
        for (int i = 1; i < 10; i++) cin >> 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 <bits/stdc++.h>

using namespace std;

struct Rat {
    int w;
    string color;
} r[101];

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> 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

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x, a[201];
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> 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 <bits/stdc++.h>

using namespace std;

int n, m;
int main() {
    while (cin >> n) {
        unordered_map<int, bool> hash;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            hash[x] = true;
        }
        cin >> m;
        for (int i = 0; i < m; i++) {
            int x;
            cin >> x;
            if (hash.find(x) != hash.end())
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
    return 0;
}

\(O(nlogn)\)

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[101], b;

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> a[i];
        cin >> m;
        sort(a, a + n);
        for (int i = 0; i < m; i++) {
            cin >> b;
            if (binary_search(a, a + n, b))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
    return 0;
}

3.9

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

bool compare(PII x, PII y) {
    if (x.first == y.first)
        return x.second < y.second;
    else
        return x.first < y.first;
}

int n;
PII a[1010];
int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
        sort(a, a + n, compare);
        cout << a[0].first << " " << a[0].second << endl;
    }
    return 0;
}

3.10

#include <bits/stdc++.h>

using namespace std;

int n;
int a[101];
int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> 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 << " ";
            } else {
                if (a[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 <bits/stdc++.h>

using namespace std;

vector<int> arr[128];
bool visited[128];

void Init(string str) {  // 将字符串所有字符统计一遍
    for (int i = 0; i < str.size(); i++) {
        arr[str[i]].push_back(i);
    }
}

int main() {
    string str;
    while (cin >> str) {
        memset(arr, 0, sizeof arr);
        memset(visited, false, sizeof visited);  // 初始化为没访问过
        Init(str);

        for (int i = 0; i < str.size();
             i++) {  // 遍历字符串 （为了按字符串出现顺序输出）
            if (!visited[str[i]] &&
                arr[str[i]].size() >
                    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

#include <bits/stdc++.h>

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 <bits/stdc++.h>

using namespace std;

// char change(char x) {
//     if (!(x >= 'a' && x <= 'z' || 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 < s.size(); ++i) {
            if (s[i] >= 'A' && s[i] <= 'Z') {
                s[i] = (s[i] - 'A' + 1) % 26 + 'A';
            }
            if (s[i] >= 'a' && s[i] <= 'z') {
                s[i] = (s[i] - 'a' + 1) % 26 + 'a';
            }
        }
        cout << s << endl;
    }
    return 0;
}

4.3

#include <bits/stdc++.h>

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 < s.size(); i++)
            if (s[i] >= 'A' && s[i] <= 'Z') s[i] = a[s[i] - 'A'];
        cout << s << endl;
    }
    return 0;
}

4.4

#include <bits/stdc++.h>

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 <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        unordered_map<char, int> 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 <bits/stdc++.h>

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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<string> split(string &s)
{
    int i = 0, j = 0;
    vector<string> a;
    while (i < s.size())
    {
        while (s[j] != ' ' && j < s.size())
            ++j;
        a.push_back(s.substr(i, j - i));
        while (s[j] == ' ')
            ++j;
        i = j;
    }
    return a;
}
 
int main()
{
    string s, a, b;
    getline(cin, s);
    cin >> 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 <iostream>
#include <string>
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 <bits/stdc++.h>

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] <= 'z' && 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 < s.size(); i++) {
            if (s[i] == ' ' || s[i] == '\t' || s[i] == '\r' || s[i] == '\n') {
                if (s[i + 1] >= 'a' && s[i + 1] <= 'z') s[i + 1] -= 32;
            }
        }
        cout << s;
    }
    return 0;
}

数据结构 I

5.1

#include <bits/stdc++.h>

using namespace std;

vector<int> ans1;
vector<int> 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 <= 60; i++) {
        int total = sum(i);
        if (total == i)
            ans1.push_back(i);
        else if (total > 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 <bits/stdc++.h>

using namespace std;

int main() {
    queue<int> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        stack<int> stk;
        int x;
        for (int i = 0; i < n; i++) {
            cin >> x;
            stk.push(x);
        }
        while (!stk.empty()) {
            cout << stk.top() << " ";
            stk.pop();
        }
        cout << endl;
    }
    return 0;
}

5.4 ⭐

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    while (cin >> s) {
        stack<char> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        stack<int> stk;
        char op;
        for (int i = 0; i < n; i++) {
            cin >> 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

#include <bits/stdc++.h>

using namespace std;

int main() {
    unsigned int n;
    while (cin >> n) {
        vector<int> 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 <bits/stdc++.h>

using namespace std;

string s;
int main() {
    while (cin >> s) {
        int n = s.size();
        vector<int> ans;
        for (int i = 0; i < n;) {
            int remain = 0;
            for (int j = i; j < n; j++) {
                int t = (remain * 10 + s[j] - '0') % 2;
                s[j] = (remain * 10 + s[j] - '0') / 2 + '0';
                remain = t;
            }
            ans.push_back(remain);
            while (s[i] == '0') i++;
        }
        for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
        cout << endl;
    }
    return 0;
}

6.3 ⭐

#include <bits/stdc++.h>

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 < len; j++) {
            int t = (remain * n + s[j] - '0') % m;
            s[j] = (remain * n + s[j] - '0') / m + '0';
            remain = t;
        }
        ans += (remain + '0');
        while (s[i] == '0') i++;
    }
    return ans;
}

int main() {
    string s;
    while (cin >> 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 <cstdio>
#include <iostream>
#include <stack>

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<char> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        stack<int> 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 <bits/stdc++.h>

using namespace std;

string add(string s1, string s2) {
    string s;
    while (s1.size() > s2.size()) s2 = "0" + s2;
    while (s1.size() < s2.size()) s1 = "0" + s1;
    int t = 0;  // 进位
    for (int i = s1.size() - 1; i >= 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 < len; j++) {
            int t = (remain * 10 + s[j] - '0') % n;
            s[j] = (remain * 10 + s[j] - '0') / n + '0';  // @ + '0' 不能忘
            remain = t;
        }
        ans += (remain + '0');  // @ 记录结果
        while (s[i] == '0') i++;
    }
    return ans;
}

int main() {
    string s1, s2;
    int n;
    while (cin >> 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 <bits/stdc++.h>

using namespace std;

int main() {
    long long n;
    while (~scanf("%llx", &n)) {
        cout << n << endl;
    }
    return 0;
}

6.8

#include <bits/stdc++.h>

using namespace std;

int charToInt(char c) {
    if (c >= '0' && c <= '9')
        return c - '0';
    else if (c >= 'a' && c <= 'z')
        return c - 'a' + 10;
    else
        return c - 'A' + 10;
}

int intToChar(int c) {
    if (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 < s.size(); i++) {
        ans *= n;
        ans += charToInt(s[i]);
    }
    return ans;
}

string toM(long long s, int n) {
    string ans = "";
    while (s) {
        int x = s % n;
        ans += intToChar(x);
        s /= n;
    }
    return ans;
}

int main() {
    int n, m;
    string s;
    while (cin >> 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

最大公约数（公因数）用辗转相除法（欧几里得算法）

#include <bits/stdc++.h>

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 <bits/stdc++.h>

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<int> a;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> 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

#include <bits/stdc++.h>

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 main() {
    int n;
    while (cin >> n) {
        if (isPrime(n))
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}

6.13

#include <bits/stdc++.h>

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 main() {
    int n;
    while (cin >> n) {
        for (int i = 2; i < n; i++) {
            if (i % 10 == 1 && isPrime(i)) cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

6.14

#include <bits/stdc++.h>

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 <= 10000) {
        if (isPrime(i)) ans[idx++] = i;
        i++;
    }
    int n;
    while (cin >> n) {
        cout << ans[n] << endl;
    }
    return 0;
}

分解质因素

6.15 ⭐

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int cnt = 0;
        for (int i = 2; i <= n / i; i++) {
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
        }
        if (n > 1) cnt++;
        cout << cnt << endl;
    }
    return 0;
}

6.16

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            vector<int> primes;
            for (int k = 2; k <= x / k; k++) {
                if (x % k == 0) {
                    int cnt = 0;
                    while (x % k == 0) {
                        cnt++;
                        x /= k;
                    }
                    primes.push_back(cnt);
                }
            }
            if (x > 1) primes.push_back(1);
            int res = 1;
            for (auto c : primes) res *= (c + 1);
            cout << res << endl;
        }
    }
    return 0;
}

快速幂

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 <bits/stdc++.h>

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

#include <bits/stdc++.h>

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

#include <bits/stdc++.h>

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 <bits/stdc++.h>

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<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        move(n, A, B, C);
    }

    void move(int n, vector<int>& A, vector<int>& B, vector<int>& 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 <bits/stdc++.h>

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 <bits/stdc++.h>

using namespace std;

string s;

map<string, int> mp;

void dfs(int now) {
    if (now == s.size())
        mp[s] = 1;
    else {
        // now 下标字母选哪个开头
        for (int i = now; i < s.size(); i++) {
            swap(s[now], s[i]);
            dfs(now + 1);
            swap(s[now], s[i]);
        }
    }
}

int main() {
    cin >> s;
    dfs(0);
    for (auto c : mp) {
        cout << c.first << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

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 <algorithm>

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 < n; i++)cin >> 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

#include <bits/stdc++.h>

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 <bits/stdc++.h>

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

#include <bits/stdc++.h>
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<str> 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 - 1; i++) {
            swap(temp.s[i], temp.s[i + 1]);
            q.push({temp.count + 1, temp.s});
            swap(temp.s[i], temp.s[i + 1]);
        }
    }
}

int main() {
    int len;
    cin >> len;
    str _str;
    cin >> _str.s;
    _str.count = 0;
    bfs(_str, len);
    cout << _count << endl;
    system("pause");
    return 0;
}

9.2

01背包问题，有递归和非递归写法

#include <bits/stdc++.h>

using namespace std;

int f[41];

int n;
int main() {
    f[0] = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = 40; j >= x; j--) f[j] = f[j] + f[j - x];
    }
    cout << f[40] << endl;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int v[25];

int n;

int dfs(int j, int i) {
    if (j < 0) return 0;
    if (j == 0) return 1;
    if (i > n) return 0;  // ^ 后执行
    return dfs(j, i + 1) + dfs(j - v[i], i + 1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cout << dfs(40, 1) << endl;
    return 0;
}

9.3 ⭐

col、dg、udg 代表列、主对角线、副对角线（减少了判断）

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> ans;
vector<int> 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 <= 8; i++) {
        if (!col[i] && !dg[n + i] && !udg[8 - n + i]) {
            col[i] = dg[n + i] = udg[8 - n + i] = true;
            path[n] = i;
            dfs(n + 1);
            col[i] = dg[n + i] = udg[8 - n + i] = false;
        }
    }
}

int main() {
    dfs(0);
    int n;
    while (cin >> n) {
        for (auto c : ans[n - 1]) cout << c;
        cout << endl;
    }
    return 0;
}

数据结构 II

优先队列

10.1

#include <bits/stdc++.h>

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<Complex> queue;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string action;
        cin >> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> que;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> 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 <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) return 0;
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> 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

#include <bits/stdc++.h>

using namespace std;

struct Student {
    string name;
    string gender;
    int year;
};

int main() {
    unordered_map<string, Student> hash;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string a, b, c;
        int d;
        cin >> a >> b >> c >> d;
        hash[a] = {b, c, d};
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        string a;
        cin >> 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 <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    while (cin >> s) {
        map<string, int> hash;
        for (int i = 0; i < s.size(); i++)
            for (int j = i; j < s.size(); j++) hash[s.substr(i, j - i + 1)]++;
        for (auto c : hash)
            if (c.second > 1) cout << c.first << " " << c.second << endl;
    }
    return 0;
}

10.7

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) return 0;
        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            hash[x]++;
        }
        int y;
        cin >> y;
        cout << hash[y] << endl;
    }
    return 0;
}

10.8

#include <bits/stdc++.h>
 
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 < n; i ++){
            cin >> id >> signIn >> signOut;
            if(signIn < signInTime){
                signInTime = signIn; openId = id;
            }
            if(signOut > signOutTime){
                signOutTime = signOut; closeId = id;
            }
        }
        cout << openId << " " << closeId << endl;
    }
    return 0;
}

• map以红黑树实现：字典序
• 迭代器可以++、--，但不支持+1

#include<iostream>
#include<string>
#include<map>
using namespace std;
 
int main(){
  int n;
  string number,timein,timeout;//证件号、进入时间，退出时间
  while(scanf("%d",&n)!=EOF){
    map<string,string>First;
    map<string,string>Last;
    while(n--){
      cin>>number>>timein>>timeout;
      First[timein]=number;
      Last[timeout]=number;
    }
   
    cout<<(First.begin())->second<<" "<<(--Last.end())->second <<endl;
  }
    
  return 0;
}

10.9

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        // 书编号、人数
        unordered_map<int, int> book;
        vector<int> record;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            book[x]++;
            record.push_back(x);
        }
        for (int i = 0; i < n; i++) {
            if (book[record[i]] > 1)
                cout << book[record[i]] - 1 << endl;
            else
                cout << "BeiJu" << endl;
        }
    }
    return 0;
}

二叉树

https://www.cnblogs.com/linxiaoxu/p/17753583.html#二叉树

二叉排序树

没刷，建议自己找题目刷一下

图论

并查集

11.1

#include <bits/stdc++.h>

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 < m; i++) {
            int a, b;
            cin >> 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 <bits/stdc++.h>

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 <= m; i++) {
            int a, b;
            cin >> 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 <bits/stdc++.h>

using namespace std;

unordered_map<int, int> 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

#include <bits/stdc++.h>

using namespace std;

int f[100];
int main() {
    int n;
    while (cin >> n) {
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            if (i - 2 >= 0) f[i] += f[i - 2];
        }
        cout << f[n] << endl;
    }
    return 0;
}

12.2

#include <bits/stdc++.h>

using namespace std;

int f[100];
int main() {
    int n;
    while (cin >> n) {
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            if (i - 2 >= 0) f[i] += f[i - 2];
        }
        cout << f[n] << endl;
    }
    return 0;
}

背包问题

https://www.cnblogs.com/linxiaoxu/p/17694869.html#背包dp

热门相关：神秘总裁小小妻   楚氏赘婿   重生之女将星   慕少，你老婆又重生了   重生之女将星