为准备浙江理工大学复试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

本栏目推荐文章
• 【C语言】
• 【C语言】形参和实参的一些注意点
• Go 语言为什么不支持并发读写 map？
• 【C语言】函数的递归调用
• 综合练习5
• Scala编程语言day1
• 算法练习题
• NUS CS1101S：SICP JavaScript 描述：四、元语言抽象
• 线段树练习
• 学了这么多编程语言，你学会了几种“Hello world”呢？

练习题 理工大学 理工 试题 语言练习题 理工大学 理工 试题 语言文学 理工 语言 学院 理工大学 理工 理工学院 理工 大学 工程学 理工大学 理工 经验 大学 学校 分校 理工 软件学院 理工大学 理工 计算机 理工大学 理工 经验 大学