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

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

快速复习

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

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

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

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

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

暴力求解枚举

题目地址
例题2.1abc(清华大学复试上机题)http://t.cn/E9WMRTE
例题2.2反序数(清华大学复试上机题)http://t.cn/E9WBrut
例题2.3对称平方数1(清华大学复试上机题)http://t.cn/E9lUYRn
习题2.4与7无关的数(北京大学复试上机题)http://t.cn/E9lOOZQ
习题2.5百鸡问题(北京哈尔滨工业大学复试上机题)http://t.cn/E9ldhru
习题2.6old bill(上海交通大学复试上机题)http://t.cn/E9jqijR

2.1

#include using namespace std;int main() {    for (int a = 0; a <= 9; a++)        for (int b = 0; b <= 9; b++)            for (int c = 0; c <= 9; c++) {                // int x = a * 100 + b * 10 + c;                // int y = b * 100 + c * 10 + c;                if (a * 100 + b * 110 + 12 * c == 532)                    cout << a << " " << b << " " << c << endl;            }}

2.2

#include using namespace std;int main() {    for (int i = 1000; i <= 1111; i++) {        int k = 9 * i;        if (k % 10 == i / 1000 && k / 10 % 10 == i / 100 % 10 &&            k / 100 % 10 == i / 10 % 10 && k / 1000 == i % 10)            cout << i << endl;    }    return 0;}

2.3

#include using namespace std;// 还有一种方式,计算相反数:每次截取x的个位加给res然后x/=10,res进位,直至x为0,返回resbool DC(int x) {    string s = to_string(x);    int n = s.size();    for (int i = 0; i < n / 2; i++) {        if (s[i] != s[n - i - 1]) return false;    }    return true;}int main() {    for (int i = 0; i <= 256; i++) {        if (DC(i * i)) cout << i << endl;    }    return 0;}

2.4

#include using namespace std;int main() {    int n;    while (cin >> n) {        int sum = 0;        for (int i = 1; i <= n; i++) {            if (i % 7 != 0 && i % 10 != 7) {                sum += i * i;            }        }        cout << sum << endl;    }    return 0;}

2.5

#include using namespace std;int main() {    int x, y, z;    int n;    while (cin >> n) {        for (int x = 0; x <= 100; x++)            for (int y = 0; y <= 100 - x; y++)                for (int z = 0; z <= 100 - x - y; z++)                    if (5 * x + 3 * y + ceil(1.0 / 3 * z) <= n &&                        x + y + z == 100)                        printf("x=%d,y=%d,z=%d\n", x, y, z);    }    return 0;}

2.6

#include using namespace std;int main() {    int n, x, y, z;    while (cin >> n >> x >> y >> z) {        bool flag = true;        for (int i = 9; i >= 1; i--) {            for (int j = 9; j >= 0; j--) {                int k = i * 10000 + x * 1000 + y * 100 + z * 10 + j;                if (k % n == 0) {                    cout << k / 10000 << " " << k % 10 << " " << k / n << endl;                    flag = false;                    break;                }            }            if (!flag) break;        }        if (flag) cout << 0 << endl;    }    return 0;}

模拟

题目地址
例题2.7今年的第几天?(清华大学复试上机题)http://t.cn/E9jXK5A
例题2.8打印日期(华中科技大学复试上机题)http://t.cn/E9YP2a8
例题2.9剩下的树(清华大学复试上机题)http://t.cn/E9ufYo5
例题2.10XXX定律(浙江大学复试上机题)http://t.cn/E937wDs
习题2.11Grading(浙江大学复试上机题)http://t.cn/E9rDPSq

2.7

#include #include using namespace std;int days[2][12] = {{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};bool isLerpYear(int y) {    if (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0))        return true;    else        return false;}int main() {    int y, m, d;    while (cin >> y >> m >> d) {        int state = 0;        if (isLerpYear(y)) state = 1;        int sum = 0;        for (int i = 0; i < m - 1; i++) sum += days[state][i];        sum += d;        cout << sum << endl;    }    return 0;}

2.8

#include using namespace std;int days[2][12] = {    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},};bool isLerpYear(int y) {    if (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0))        return true;    else        return false;}int main() {    int y, d;    while (cin >> y >> d) {        int state = 0;        if (isLerpYear(y)) state = 1;        int m = 0;        for (; m  days[state][m]; m++) {            d -= days[state][m];        }        printf("%04d-%02d-%02d\n", y, m + 1, d);    }    return 0;}

2.9

#include using namespace std;int const N = 1e2 + 10;typedef pair PII;PII segs[N];int main() {    int l, n;    while (cin >> l >> n) {        for (int i = 0; i > segs[i].first >> segs[i].second;            if (segs[i].first > segs[i].second)                swap(segs[i].first, segs[i].second);        }        sort(segs, segs + n);        int sum = l + 1, start = segs[0].first, end = segs[0].second;        for (int i = 0; i  end) {                sum -= (end - start + 1);                start = segs[i].first;                end = segs[i].second;            } else if (segs[i].second > end)                end = segs[i].second;        }        // 最后一段未减去        sum -= (end - start + 1);        cout << sum << endl;    }    return 0;}

2.10

#include using namespace std;int main() {    int n;    while (cin >> n) {        int count = 0;        while (n != 1) {            count++;            if (n % 2 == 0)                n /= 2;            else if (n % 2)                n = (3 * n + 1) / 2;        }        cout << count << endl;    }    return 0;}

2.11

#include using namespace std;void grade(int T, int G1, int G2, int G3, int GJ) {    if (fabs(G1 - G2) <= T) {        printf("%.1f\n", 1.0 * (G1 + G2) / 2);    } else {        if (fabs(G1 - G3) <= T && fabs(G1 - G3) <= T) {            printf("%.1f\n", max(max(G1, G2), G3));        } else if (fabs(G1 - G3) <= T) {            printf("%.1f\n", 1.0 * (G1 + G3) / 2);        } else if (fabs(G2 - G3) > P >> T >> G1 >> G2 >> G3 >> GJ) {        grade(T, G1, G2, G3, GJ);    }    return 0;}

排序与查找排序

题目地址
例题3.1排序(清华大学复试上机题)http://t.cn/E9dLx5K
例题3.2成绩排序(清华大学复试上机题)http://t.cn/E9d3ysv
例题3.3成绩排序2(清华大学复试上机题)http://t.cn/E9gyHM1
习题3.4特殊排序(华中科技大学复试上机题)http://t.cn/E9gio39
习题3.5整数奇偶排序(北京大学复试上机题)http://t.cn/E9glPvp
习题3.6小白鼠排队(北京大学复试上机题)http://t.cn/E9gXh9Z

3.1

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

//所有基本的排序方法了,桶排序、基数排序暂不写了#includeusing namespace std;const int N = 110, MAX = 1e8;int a[N];int n;int h[N], idx;//heap_sort用int tmp[N];//merge_sort用int bkt[MAX];//counting_sort用void buble_sort(){    for(int i = 0; i < n - 1; i ++)        for(int j = 0; j a[j+1]) swap(a[j], a[j + 1]);        }}void quick_sort(int l, int r){    if(l>=r) return;    int x = a[(l + r) / 2];    int i = l - 1, j = r + 1;    while(i<j){        do i ++; while(a[i]  x);        if(i < j) swap(a[i], a[j]);    }    quick_sort(l, j);    quick_sort(j+1, r);}void selection_sort(){    for(int i = 0; i < n - 1;i ++){        int min_pos = i;        for(int j = i + 1; j < n; j ++)            if(a[j]<a[min_pos]) min_pos = j;        swap(a[i], a[min_pos]);    }}void down(int u){    int t = u;    if(u*2<=idx&&h[u*2]<h[t]) t = u*2;    if(u*2+1<=idx&&h[u*2+1]<h[t]) t= u*2+1;    if(t!=u){        swap(h[t], h[u]);        down(t);    }}void heap_sort(){    for(int i = 1; i  0; i --) down(i);    for(int i = 0; i < n; i ++){        a[i] = h[1];        h[1] = h[idx--];        down(1);    }}void insertion_sort(){    for(int i = 1; i =0 && a[j]>cur_idx; j --){            a[j+1] = a[j];        }        a[j+1] = cur_idx;    }}void binary_insertion_sort(){    for(int i = 1; i < n; i ++){        int cur_idx = a[i];        int l = 0, r = i - 1;        while(l<r){            int mid = (l + r + 1) / 2;            if(a[mid]cur_idx) l = -1;        int j;        for(j = i - 1; j>l ;j --) a[j+1] = a[j];        a[j+1] = cur_idx;    }}void shell_sort(){    for(int gap = n/2; gap>=1; gap /= 2){        for(int i = gap; i =0 && a[j]>cur_idx; j -= gap){                a[j+gap] = a[j];            }            a[j + gap] = cur_idx;        }    }}void merge_sort(int l, int r){    if(l>=r) return;    int mid = (l + r) / 2;    merge_sort(l, mid), merge_sort(mid + 1, r);    int k = 0, i = l, j = mid + 1;    while(i<=mid&&j<=r){        if(a[i]<=a[j]) tmp[k++] = a[i++];        else tmp[k++] = a[j++];    }    while(i<=mid) tmp[k++] = a[i++];    while(j<=r) tmp[k++] = a[j++];    for(int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];}void counting_sort(){    int max = 0;    for(int i = 0 ; i max) max = a[i];    }    int j = 0;    for(int i = 0; i < max+1; i ++){        while(bkt[i]){            a[j++] = i;            bkt[i]--;        }    }}int main(){    scanf("%d", &n);    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);//     buble_sort();//     quick_sort(0, n - 1);//     selection_sort();//     heap_sort();//     insertion_sort();//     binary_insertion_sort();//     shell_sort();//    merge_sort(0, n - 1);    counting_sort();    for(int i = 0; i < n; i ++) printf("%d ", a[i]);    return 0;}

3.2

#include using namespace std;struct Student {    int p;    int q;} s[101];int main() {    int n;    cin >> n;    for (int i = 0; i > s[i].p >> s[i].q;    sort(s, s + n, [](Student x, Student y) {        if (x.q == y.q)            return x.p < y.p;        else            return x.q < y.q;    });    for (int i = 0; i < n; i++) cout << s[i].p << " " << s[i].q << endl;    return 0;}

3.3

#include using namespace std;struct Student {    string name;    int score;};int mode;bool cmp(Student a, Student b) {    if (mode == 0)        return a.score > b.score;    else        return a.score > n) {        cin >> mode;        Student s[n];        for (int i = 0; i > s[i].name >> s[i].score;        stable_sort(s, s + n, cmp);        for (int i = 0; i < n; i++)            cout << s[i].name << " " << s[i].score << endl;    }    return 0;}

3.4

#include using namespace std;int n;int a[1010];int main() {    while (cin >> n) {        for (int i = 0; i > a[i];        sort(a, a + n);        cout << a[n - 1] << endl;        for (int i = 0; i < n - 1; i++) cout << a[i] << " ";        if (n - 1 == 0) cout << -1;        cout << endl;    }    return 0;}

3.5

#include using namespace std;int main() {    int a[10];    while (cin >> a[0]) {        for (int i = 1; i > a[i];        sort(a, a + 10);        for (int i = 9; i >= 0; i--)            if (a[i] % 2) cout << a[i] << " ";        for (int i = 0; i <= 9; i++)            if (a[i] % 2 == 0) cout << a[i] << " ";        cout << endl;    }    return 0;}

3.6

#include using namespace std;struct Rat {    int w;    string color;} r[101];int main() {    int n;    while (cin >> n) {        for (int i = 0; i > r[i].w >> r[i].color;        sort(r, r + n, [](Rat x, Rat y) { return x.w > y.w; });        for (int i = 0; i < n; i++) cout << r[i].color << endl;    }    return 0;}

查找

题目地址
例题3.7找x(哈尔滨工业大学复试上机题)http://t.cn/E9gHFnS
例题3.8查找(北京邮电大学复试上机题)http://t.cn/E9g8aaR
习题3.9找最小数(北京邮电大学复试上机题)http://t.cn/E9gekWa
习题3.10打印极值点下标(北京大学复试上机题)http://t.cn/E9ehDw4
习题3.11找位置(华中科技大学复试上机题)http://t.cn/E9eh4jY

3.7

#include using namespace std;int main() {    int n, x, a[201];    while (cin >> n) {        for (int i = 0; i > a[i];        cin >> x;        int ans = -1;        for (int i = 0; i < n; i++)            if (a[i] == x) ans = i;        cout << ans << endl;    }    return 0;}

3.8 ⭐ map、二分

\(O(n)\)

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

\(O(nlogn)\)

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

3.9

#include using namespace std;typedef pair PII;bool compare(PII x, PII y) {    if (x.first == y.first)        return x.second < y.second;    else        return x.first > n) {        for (int i = 0; i > a[i].first >> a[i].second;        sort(a, a + n, compare);        cout << a[0].first << " " << a[0].second << endl;    }    return 0;}

3.10

#include using namespace std;int n;int a[101];int main() {    while (cin >> n) {        for (int i = 0; i > a[i];        for (int i = 0; i < n; i++) {            if (i == 0) {                if (a[i] != a[i + 1]) cout << i << " ";            } else if (i == n - 1) {                if (a[i] != a[i - 1]) cout << i < a[i + 1] && a[i] > a[i - 1] ||                    a[i] < a[i + 1] && a[i] < a[i - 1])                    cout << i << " ";            }        }        cout << endl;    }    return 0;}

3.11

#include using namespace std;vector arr[128];bool visited[128];void Init(string str) {  // 将字符串所有字符统计一遍    for (int i = 0; i > str) {        memset(arr, 0, sizeof arr);        memset(visited, false, sizeof visited);  // 初始化为没访问过        Init(str);        for (int i = 0; i                     1) {  // 如果是没有访问过的字符 且 是重复的字符                for (int j = 0; j < arr[str[i]].size(); j++) {                    if (j == 0) {  // 输出控制                        printf("%c:%d", str[i], arr[str[i]][j]);                    } else {                        printf(",%c:%d", str[i], arr[str[i]][j]);                    }                }                printf("\n");                visited[str[i]] = true;  // 置访问过            }        }    }    return 0;}

字符串

题目地址
例题4.1特殊乘法(清华大学复试上机题)http://t.cn/Ai8by9vW
例题4.2密码翻译(北京大学复试上机题)http://t.cn/Ai8bGaIx
例题4.3简单密码(北京大学复试上机题)http://t.cn/Ai8bih2z
例题4.4统计字符(浙江大学复试上机题)http://t.cn/Ai8fvq4I
例题4.5字母统计(上海交通大学复试上机题)http://t.cn/Ai8VB72e
习题4.6skew数(北京大学复试上机题)http://t.cn/Ai8IALKI
习题4.7单词替换(北京大学复试上机题)http://t.cn/Ai8Iycp6
习题4.8首字母大写(北京大学复试上机题)http://t.cn/Ai8I2hco

4.1

#include using namespace std;int sum(int n) {    int sum = 0;    while (n) {        sum += n % 10;        n /= 10;    }    return sum;}int main() {    int a, b;    while (cin >> a >> b) {        cout << sum(a) * sum(b) << endl;    }    return 0;}

4.2

#include using namespace std;// char change(char x) {//     if (!(x >= 'a' && x = 'A' && x <= 'Z')) return x;//     if (x == 'z')//         return 'a';//     else if (x == 'Z')//         return 'A';//     else//         return (char)x + 1;// }int main() {    string s;    while (getline(cin, s)) {        // for (int i = 0; i < s.size(); i++) s[i] = change(s[i]);        for (int i = 0; i = 'A' && s[i] = 'a' && s[i] <= 'z') {                s[i] = (s[i] - 'a' + 1) % 26 + 'a';            }        }        cout << s << endl;    }    return 0;}

4.3

#include using namespace std;int main() {    char a[30] = {'V', 'W', 'X', 'Y', 'Z', 'A', 'B', 'C', 'D',                  'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',                  'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U'};    string s;    while (getline(cin, s)) {        if (s == "START" || s == "END" || s == "ENDOFINPUT") continue;        for (int i = 0; i = 'A' && s[i] <= 'Z') s[i] = a[s[i] - 'A'];        cout << s << endl;    }    return 0;}

4.4

#include using namespace std;int main() {    string s1, s2;    while (getline(cin, s1), getline(cin, s2)) {        int count[128] = {0};        for (int i = 0; i < s2.size(); i++) count[s2[i]]++;        for (int i = 0; i < s1.size(); i++)            cout << s1[i] << " " << count[s1[i]] << endl;    }    return 0;}

4.5

#include using namespace std;int main() {    string s;    while (getline(cin, s)) {        unordered_map hash;        for (int i = 0; i < s.size(); i++) hash[s[i]]++;        for (int i = 'A'; i <= 'Z'; i++)            cout << (char)i << ":" << hash[i] << endl;    }    return 0;}

4.6

#include using namespace std;int main() {    string s;    while (getline(cin, s)) {        int sum = 0;        int n = s.size();        for (int i = 0; i < s.size(); i++) {            sum += (s[i] - '0') * (pow(2, n) - 1);            n--;        }        cout << sum << endl;    }    return 0;}

4.7 ⭐

先按空格将句子分成一个一个单词,这样就非常方便替换了。直接检查单词即可了

#include #include #include using namespace std; vector split(string &s){    int i = 0, j = 0;    vector a;    while (i < s.size())    {        while (s[j] != ' ' && j > a >> b;    auto res = split(s);    for (int i = 0; i < res.size(); ++i)        if (res[i] == a)            cout << b << ' ';        else            cout << res[i] << ' ';    return 0;}

因为直接使用 find 的话不是单词也可能匹配到,所以在 a,b 前面加了空格,主要使用了 C++ 库函数的 erase(pos, len),清除 pos 开始的长度为 len 的子串,insert(pos, b) 在 pos 位置插入字符串 b

#include #include using namespace std; int main(){    string s,a,b;    getline(cin,s);    getline(cin,a);    getline(cin,b);    s = " " + s + " ";    a = " " + a + " ";    b = " " + b + " ";    int start;    while(1){        start=s.find(a);        if(start == string::npos)            break;        else{            s.erase(start,a.length());            s.insert(start,b);        }    }    int n = s.size();    cout<<s.substr(1, n - 2);    return 0;}

4.8

#include using namespace std;// bool isK(char x) {//     return x == ' ' || x == '\t' || x == '\r' || x == '\n' ||//            x == '\0';  // 注意 \0// }int main() {    string s;    while (getline(cin, s)) {        // for (int i = 0, j = 0; i < s.size() && j < s.size();) {        //     if (s[i] = 'a') s[i] -= 32;        //     while (!isK(s[j])) j++;        //     i = ++j;        // }        if (s[0] >= 'a' && s[0] <= 'z') s[0] -= 32;        for (int i = 1; i = 'a' && s[i + 1] <= 'z') s[i + 1] -= 32;            }        }        cout << s;    }    return 0;}

数据结构 I

题目地址
例题5.1完数与盈数(清华大学复试上机题)http://t.cn/AiKEyQWW
例题5.2约瑟夫问题NO.2http://bailian.openjudge.cn/practice/3254
例题5.3Zero-complexity Transposition(上海交通大学复试上机题)http://t.cn/AiKa20bt
例题5.4括号匹配问题http://ccnu.openjudge.cn/practice/1978/
习题5.5堆栈的使用(吉林大学复试上机题)http://t.cn/AiKKM6F6

5.1

#include using namespace std;vector ans1;vector ans2;int sum(int x) {    int sum = 1;    for (int i = 2; i * i <= x; i++) {        if (x % i == 0) {            sum += i;            if (x / i != i) sum += x / i;        }    }    return sum;}int main() {    for (int i = 2; i  i)            ans2.push_back(i);    }    cout << "E: ";    for (auto c : ans1) cout << c << " ";    cout << endl;    cout << "G: ";    for (auto c : ans2) cout << c << " ";    cout << endl;    return 0;}

5.2

#include using namespace std;int main() {    queue q;    int n, p, m;    while (cin >> n >> p >> m, n && p && m) {        for (int i = 1; i <= n; i++) q.push(i);        while (q.front() != p) {            int t = q.front();            q.pop();            q.push(t);        }        int count = 1;        while (!q.empty()) {            if (count != m) {                count++;                int t = q.front();                q.pop();                q.push(t);            } else if (count == m) {                int t = q.front();                q.pop();                cout << t;                if (!q.empty()) cout << ',';                count = 1;            }        }        cout << endl;    }    return 0;}

5.3

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

5.4 ⭐

#include using namespace std;int main() {    string s;    while (cin >> s) {        stack stk;        // ^ 动态实例化一个字符串,非常好的方法        string ans(s.size(), ' ');        for (int i = 0; i < s.size(); i++) {            if (s[i] == '(')                stk.push(i);            else if (s[i] == ')') {                if (!stk.empty()) {                    stk.pop();                } else                    ans[i] = '?';            }        }        while (!stk.empty()) {            ans[stk.top()] = '$';            stk.pop();        }        cout << s << endl;        cout << ans << endl;    }    return 0;}

5.5

#include using namespace std;int main() {    int n;    while (cin >> n) {        stack stk;        char op;        for (int i = 0; i > op;            int x;            if (op == 'P') {                cin >> x;                stk.push(x);            } else if (op == 'O') {                if (!stk.empty()) stk.pop();            } else if (op == 'A') {                if (!stk.empty())                    cout << stk.top() << endl;                else                    cout << "E" << endl;            }        }    }    return 0;}

数学问题进制转换

题目地址
例题6.1二进制数(北京邮电大学复试上机题)http://t.cn/AiCuKTOv
例题6.2进制转换(清华大学复试上机题)http://t.cn/AiCuoPRO
例题6.3十进制与二进制(清华大学复试上机题)http://t.cn/AiCuoHKg
例题6.4进制转换2(清华大学复试上机题)http://t.cn/AiCuKG7E
习题6.5八进制(华中科技大学复试上机题)http://t.cn/AiCu0lHe
习题6.6又一版A+B(浙江大学复试上机题)http://t.cn/AiCuOSWv
习题6.7进制转换(北京大学复试上机题)http://t.cn/AiCuig9B
习题6.8数制转换(北京大学复试上机题)http://t.cn/AiCu6ne4

6.1

#include using namespace std;int main() {    unsigned int n;    while (cin >> n) {        vector ans;        while (n) {            ans.push_back(n % 2);            n /= 2;        }        reverse(ans.begin(), ans.end());        for (auto c : ans) cout << c;        cout << endl;    }    return 0;}

6.2 ⭐ 模拟竖式除法

#include using namespace std;string s;int main() {    while (cin >> s) {        int n = s.size();        vector ans;        for (int i = 0; i < n;) {            int remain = 0;            for (int j = i; j = 0; i--) cout << ans[i];        cout << endl;    }    return 0;}

6.3 ⭐

#include using namespace std;string convert(string s, int n, int m) {    string ans = "";    int len = s.size();    for (int i = 0; i < len;) {        int remain = 0;        for (int j = i; j > s) {        string temp = convert(s, 10, 2);        string ans = convert(temp, 2, 10);        reverse(ans.begin(), ans.end());        cout << ans << endl;    }    return 0;}

6.4

#include #include #include using namespace std;int CharToInt(char c) {    if (c >= '0' && c <= '9') {        return c - '0';  // 数字型字符转数字    } else {        return c - 'A' + 10;  // 字符型字符转数字    }}char IntToChar(int target) {    if (target < 10) {        return target + '0';    } else {        return target + 'a' - 10;    }}long long ConvertM2T(string str,                     int current) {  // current为当前需转换的目标的当前进制    long long number = 0;    for (int i = 0; i < str.size(); ++i) {        number *= current;        number += CharToInt(str[i]);    }    return number;}void ConvertT2N(long long number, int target) {  // target为目标进制    stack myStack;    if (number == 0) {        myStack.push('0');    }    while (number != 0) {        myStack.push(IntToChar(number % target));        number /= target;    }    while (!myStack.empty()) {        printf("%c", myStack.top());        myStack.pop();    }    printf("\n");}int main() {    int m, n;    while (cin >> m >> n) {        string str;        cin >> str;        long long number = ConvertM2T(str, m);  // 先转换成十进制        ConvertT2N(number, n);                  // 再将十进制转n进制    }    return 0;}

6.5

#include using namespace std;int main() {    int n;    while (cin >> n) {        stack stk;        if (n == 0) stk.push(0);        while (n) {            stk.push(n % 8);            n /= 8;        }        while (!stk.empty()) {            cout << stk.top();            stk.pop();        }        cout << endl;    }    return 0;}

6.6

#include using namespace std;string add(string s1, string s2) {    string s;    while (s1.size() > s2.size()) s2 = "0" + s2;    while (s1.size() = 0; i--) {        t = t + s1[i] + s2[i] - '0' - '0';        char c = t % 10 + '0';        s.insert(0, 1, c);        t = t / 10;    }    if (t) {        char c = t % 10 + '0';        s.insert(0, 1, c);        t = t / 10;    }    return s;}string div(string s, int n) {    int len = s.size();    string ans = "";    for (int i = 0; i < len;) {        int remain = 0;        for (int j = i; j > n >> s1 >> s2) {        string temp = add(s1, s2);        temp = div(temp, n);        reverse(temp.begin(), temp.end());        cout << temp << endl;    }    return 0;}

6.7

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

6.8

#include using namespace std;int charToInt(char c) {    if (c >= '0' && c = 'a' && c = 0 && c <= 9)        return c + '0';    else        return c - 10 + 'A';}long long toD(string s, int n) {    long long ans = 0;    for (int i = 0; i > n >> s >> m) {        long long temp = toD(s, n);        string ans = toM(temp, m);        reverse(ans.begin(), ans.end());        cout << ans << endl;    }    return 0;}

最大公约数与最小公倍数

题目地址
例题6.9最大公约数(哈尔滨工业大学复试上机题)http://t.cn/AiCuWLTS
例题6.10最小公倍数
习题6.11最简真分数(北京大学复试上机题)http://t.cn/AiCua2g8

6.9

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

#include using namespace std;int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }int main() {    int a, b;    while (cin >> a >> b) {        cout << gcd(a, b) << endl;    }    return 0;}

6.10 ⭐

最大公因数和最小公倍数的积等于两个数的积

最大公因数×最小公倍数
=共同因数×(共同因数×两个数各自的独有因数)
=(共同因数×一个数独有因数)×(共同因数×另一个数独有因数)
=一个数×另一个数
=两个数的积

最小公倍数 = a * b / gcd(a,b)

6.11

最简分数,是分子、分母只有公因数1的分数,或者说分子和分母互质的分数,又称既约分数

真分数,指的是分子比分母小的分数

#include using namespace std;int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }int main() {    int n;    while (cin >> n) {        if (n == 0) return 0;        vector a;        for (int i = 0; i > x;            a.push_back(x);        }        sort(a.begin(), a.end());        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                if (gcd(a[i], a[j]) == 1) count++;            }        }        cout << count << endl;    }    return 0;}

质数

题目地址
例题6.12素数判定(哈尔滨工业大学复试上机题)http://t.cn/AiCuWE0Q
例题6.13素数http://t.cn/AiCulqtW
习题6.14Prime Number(上海交通大学复试上机题)http://t.cn/AiCulrSh

6.12

#include using namespace std;bool isPrime(int n) {    if (n <= 1) return false;    for (int i = 2; i > n) {        if (isPrime(n))            cout << "yes" << endl;        else            cout << "no" << endl;    }    return 0;}

6.13

#include using namespace std;bool isPrime(int n) {    if (n <= 1) return false;    for (int i = 2; i > n) {        for (int i = 2; i < n; i++) {            if (i % 10 == 1 && isPrime(i)) cout << i << " ";        }        cout << endl;    }    return 0;}

6.14

#include using namespace std;bool isPrime(int n) {    if (n <= 1) return false;    for (int i = 2; i <= n / i; i++) {        if (n % i == 0) return false;    }    return true;}int const N = 1e4 + 10;int ans[N];int main() {    int idx = 1, i = 2;    while (idx > n) {        cout << ans[n] << endl;    }    return 0;}

分解质因素

题目地址
例题6.15质因数的个数(清华大学复试上机题)http://t.cn/Aip7J0Oo
习题6.16约数的个数(清华大学复试上机题)http://t.cn/Aip7dTUp

6.15 ⭐

#include using namespace std;int main() {    int n;    while (cin >> n) {        int cnt = 0;        for (int i = 2; i  1) cnt++;        cout << cnt << endl;    }    return 0;}

6.16

#include using namespace std;int main() {    int n;    while (cin >> n) {        for (int i = 0; i > x;            vector primes;            for (int k = 2; k  1) primes.push_back(1);            int res = 1;            for (auto c : primes) res *= (c + 1);            cout << res << endl;        }    }    return 0;}

快速幂

题目地址
例题6.17快速幂https://www.nowcoder.com/share/jump/7523383881696517430391

6.17

算法学习笔记(4):快速幂 – 知乎 (zhihu.com)

取模常用公式

一 . (a+b)mod n = ((a mod n)+(b mod n) mod n

二 . (a-b)mod n = ((a mod n)-(b mod n)+n) mod n

三 . ab mod n = (a mod n)(b mod n) mod n

#include using namespace std;long long a, b, p;long long qpow(long long x, long long n) {    if (n == 0)        return 1;    else if (n % 2 == 0) {        long long temp = (qpow(x, n / 2) % p);        return temp * temp;    } else {        return (qpow(x, n - 1) % p) * (x % p);    }}int main() {    int n;    cin >> n;    while (n--) {        cin >> a >> b >> p;        cout << (qpow(a, b) % p) << endl;    }    return 0;}

矩阵快速幂

没刷

高精度整数

没刷

贪心

题目地址
例题7.1鸡兔同笼(北京大学复试上机题)http://t.cn/E9ewERU

另外可做一下区间贪心题(如区间合并,区间选择等)

7.1

#include using namespace std;int main() {    int n;    while (cin >> n) {        if (n % 2 != 0)            cout << "0 0" << endl;        else {            int a = n / 4;            int b = (n - a * 4) / 2;            cout << a + b;            cout << " ";            cout << n / 2 << endl;        }    }    return 0;}

递归与分治递归

题目地址
例题8.1n的阶乘(清华大学复试上机题)http://t.cn/Ai0ocOUY
例题8.2汉诺塔https://www.nowcoder.com/questionTerminal/84ce91c6099a45dc869355fa1c4f589d
例题8.3汉诺塔https://leetcode.cn/problems/hanota-lcci/description/
习题8.4杨辉三角形(西北工业大学复试上机题)https://www.nowcoder.com/share/jump/7523383881696451582920
习题8.5全排列(北京大学复试上机题)http://t.cn/Ai0K0hXZ

8.1

#include using namespace std;long long jie(int n) {    if (n == 1)        return 1;    else        return n * jie(n - 1);}int main() {    int n;    while (cin >> n) {        cout << jie(n) << endl;    }    return 0;}

8.2

  • n = 1 时
    • 直接把盘子从 A 移到 C
  • n > 1 时
    • 先把上面 n – 1 个盘子从 A 通过 C 移到 B(子问题,递归)
    • 再将最大的盘子从 A 移到 C (此时 A 空)
    • 再将 B 上 n – 1 个盘子从 B 通过 A 移到 C(子问题,递归)
#include using namespace std;void move(int n, char* pos1, char* pos3) {    printf("Move %d from %s to %s\n", n, pos1, pos3);}void Hanoi(int n, char* pos1, char* pos2, char* pos3) {    // 如果是1个盘子,直接从起始柱A移动到目标柱C    if (n == 1)        move(n, pos1, pos3);    else {        // 如果盘子大于1个,需要把n-1个盘子,从起始柱pos1,通过目标柱pos3,移动到中转柱pos2        Hanoi(n - 1, pos1, pos3, pos2);        // 此时pos1上的n-1个盘子全部移动pos2上去了,那么可以直接把pos1上剩下的1个盘子,直接移动到pos3上        move(n, pos1, pos3);        // 把pos2剩下的n-1个盘子,通过中转位置pos1,移动到目标位置pos3        Hanoi(n - 1, pos2, pos1, pos3);    }}int main() {    int n;    while (cin >> n) {        char* pos1 = "left";        char* pos2 = "mid";        char* pos3 = "right";        Hanoi(n, pos1, pos2, pos3);    }    return 0;}

8.3

class Solution {public:    void hanota(vector& A, vector& B, vector& C) {        int n = A.size();        move(n, A, B, C);    }    void move(int n, vector& A, vector& B, vector& C){        if (n == 1){            C.push_back(A.back());            A.pop_back();            return;        }        move(n-1, A, C, B);    // 将A上面n-1个通过C移到B        C.push_back(A.back());  // 将A最后一个移到C        A.pop_back();          // 这时,A空了        move(n-1, B, A, C);     // 将B上面n-1个通过空的A移到C    }};

8.4

没用到递归

#include using namespace std;int main() {    int n = 0;    int arr[30][30] = {0};    scanf("%d", &n);    for (int i = 0; i < n; i++) {        for (int j = 0; j <= i; j++) {            if (0 == j || i == j) {                arr[i][j] = 1;            } else {                arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];            }            printf("%5d", arr[i][j]);        }        printf("\n");    }    return 0;}

8.5 ⭐

比如这里所说的全排列{“a”,”b”,”c”,”d”};

1。首先四个字母的全排列可以被简化成分别以”a”、”b”、”c”、”d”打头,加上剩下三个字母的全排列;

2。以此类推,上一步中的每一个三个字母的全排列,又可以被简化为分别以三个字母打头,加上剩下两个字母的全排列

3。重复前面的简化过程,直到只剩一个字母的时候,就很容易了处理了,因为一个字母的全排列太显而易见了

另外注意:用了map而不是vector。因为递归只能找出所有的排列,并不能保证是按照字典序排序的。所有用map,map底层是红黑树,内部仍然是有序的

#include using namespace std;string s;map mp;void dfs(int now) {    if (now == s.size())        mp[s] = 1;    else {        // now 下标字母选哪个开头        for (int i = now; i > s;    dfs(0);    for (auto c : mp) {        cout << c.first << endl;    }    return 0;}

#include using namespace std;string s;int main() {    cin >> s;    sort(s.begin(), s.end());    do {        cout << s << endl;    } while (next_permutation(s.begin(), s.end()));    return 0;}

全排列函数

头文件 #include


next_permutation:求下一个排列组合 

  • 函数模板:next_permutation(arr, arr+size);
  • 参数说明:
    arr: 数组名
      size:数组元素个数
  • 函数功能: 返回值为bool类型,当当前序列不存在下一个排列时,函数返回false,否则返回true,排列好的数在数组中存储
  • 注意:在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。比如,如果数组num初始化为2,3,1,那么输出就变为了:{2 3 1}

prev_permutation:求上一个排列组合

  • 函数模板:prev_permutation(arr, arr+size);
  • 参数说明:
    arr: 数组名
      size:数组元素个数
  • 函数功能: 返回值为bool类型,当当前序列不存在上一个排列时,函数返回false,否则返回true]
  • 注意:在使用前需要对欲排列数组按降序排序,否则只能找出该序列之后的全排列数。
string s;while (getline(cin, s)) {    sort(s.begin(), s.end());    do    {        cout << s << endl;    } while (next_permutation(s.begin(), s.end()));    cout << endl;}

for (int i = 0; i > a[i];sort(a, a + n);do{    for (int i = 0; i < n; i++)cout << a[i];    cout << endl;} while (next_permutation(a, a + n));cout << endl;

分治

题目地址
例题8.6Fibonacci(上海交通大学复试上机题)http://t.cn/Ai0K3tU5
例题8.7二叉树(北京大学复试上机题)http://t.cn/Ai0Ke6I0

8.6

#include using namespace std;int f(int n) {    if (n == 0) return 0;    if (n == 1) return 1;    return f(n - 1) + f(n - 2);}int main() {    int n;    while (cin >> n) {        cout << f(n) << endl;    }    return 0;}

8.7

#include using namespace std;int n, m;int dfs(int n) {    if (n > m) return 0;    return 1 + dfs(2 * n) + dfs(2 * n + 1);}int main() {    while (cin >> n >> m) {        if (n == 0 && m == 0) return 0;        cout << dfs(n) << endl;    }    return 0;}

搜索

题目地址
习题9.1玛雅人的密码http://t.cn/Ai0lUhJj
习题9.2神奇的口袋(北京大学复试上机题)http://t.cn/Ai0u0GUz
习题9.3八皇后(北京大学复试上机题)http://t.cn/Ai0uOazs

9.1

#include using namespace std;struct str {    int count;  // 记录移动次数(为什么要加?答:因为bfs队列一直在循环,不清楚排队的兄弟经过了几次字符移动)    string s;};bool check(string s) {    if (s.find("2012") != string::npos)        return true;    else        return false;}int fact(int l) {    if (l == 0)        return 1;    else        return l * fact(l - 1);}queue q;int _count = -1;void bfs(str s, int len) {    q.push(s);    int flag = 0;  // 记录排队数,全排列后还没跳出,说明无解,撤退之    // BFS主体    while (!q.empty()) {        if (flag++ > fact(len)) return;        // 取队首检查之        str temp = q.front();        q.pop();        if (check(temp.s) == true) {            _count = temp.count;            return;        }        // 字符移动并入队        for (int i = 0; i > len;    str _str;    cin >> _str.s;    _str.count = 0;    bfs(_str, len);    cout << _count << endl;    system("pause");    return 0;}

9.2

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

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

#include using namespace std;int v[25];int n;int dfs(int j, int i) {    if (j  n) return 0;  // ^ 后执行    return dfs(j, i + 1) + dfs(j - v[i], i + 1);}int main() {    cin >> n;    for (int i = 1; i > v[i];    }    cout << dfs(40, 1) << endl;    return 0;}

9.3 ⭐

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

#include using namespace std;vector<vector> ans;vector path(8, 0);bool col[9], dg[2 * 9 - 1], udg[2 * 9 - 1];void dfs(int n) {    if (n == 8) {        ans.push_back(path);        return;    }    for (int i = 1; i > n) {        for (auto c : ans[n - 1]) cout << c;        cout << endl;    }    return 0;}

数据结构 II优先队列

题目地址
例题10.1复数集合(北京邮电大学复试上机题)http://t.cn/Ai98yYlt
例题10.2哈夫曼树(北京邮电大学复试上机题)http://t.cn/AiCuGMki
习题10.3查找第K小的数(北京邮电大学复试上机题)http://t.cn/AiCu5hcK
习题10.4搬水果(吉林大学复试上机题)http://t.cn/AiCu5nsQ

10.1

#include using namespace std;struct Complex {    int a;  // 实部    int b;  // 虚部    bool operator<(const Complex &w) const {        return a * a + b * b < w.a * w.a + w.b * w.b;    };};int main() {    int n;    priority_queue queue;    cin >> n;    for (int i = 0; i > action;        if (action == "Pop") {            if (queue.empty()) {                printf("empty\n");            } else {                printf("%d+i%d\n", queue.top().a, queue.top().b);                queue.pop();                printf("SIZE = %d\n", queue.size());            }        } else if (action == "Insert") {            int re, im;            scanf("%d+i%d", &re, &im);  // 格式化读取            Complex c;            queue.push({re, im});            printf("SIZE = %d\n", queue.size());        }    }    return 0;}

10.2 ⭐

数据结构——哈夫曼树(Huffman Tree) – 知乎 (zhihu.com)

#include using namespace std;int main() {    int n;    cin >> n;    priority_queue<int, vector, greater> que;    for (int i = 0; i > num;        que.push(num);    }    int res = 0;    while (que.size() > 1) {        int a = que.top();        que.pop();        int b = que.top();        que.pop();        res += a + b;        que.push(a + b);    }    printf("%d", res);}

10.3

#include using namespace std;int main() {    int n;    while (cin >> n) {        priority_queue<int, vector, greater> heap;        for (int i = 0; i > x;            heap.push(x);        }        int count;        cin >> count;        int res;        for (int k = 1; k <= count; k++) {            res = heap.top();            while (!heap.empty() && heap.top() == res) heap.pop();        }        cout << res << endl;    }    return 0;}

10.4

#include using namespace std;int main() {    int n;    while (cin >> n) {        if (n == 0) return 0;        priority_queue<int, vector, greater> heap;        for (int i = 1; i > x;            heap.push(x);        }        long long res = 0;        while (heap.size() != 1) {            int a = heap.top();            heap.pop();            int b = heap.top();            heap.pop();            res += a + b;            heap.push(a + b);        }        cout << res << endl;    }    return 0;}

哈希表

题目地址
例题10.5查找学生信息(清华大学复试上机题)http://t.cn/AiCuVIuY
例题10.6字串计算(北京大学复试上机题)http://t.cn/AiCuJtI5
习题10.7统计同成绩学生人数(浙江大学复试上机题)http://t.cn/AiCuM7nj
习题10.8开门人和关门人(浙江大学复试上机题)http://t.cn/AiCuM09f
习题10.9谁是你的潜在朋友(北京大学复试上机题)http://t.cn/AiCux4f7

10.5

#include using namespace std;struct Student {    string name;    string gender;    int year;};int main() {    unordered_map hash;    int n;    cin >> n;    for (int i = 0; i > a >> b >> c >> d;        hash[a] = {b, c, d};    }    cin >> n;    for (int i = 0; i > a;        if (hash.find(a) == hash.end())            cout << "No Answer!" << endl;        else            cout << a << " " << hash[a].name << " " << hash[a].gender << " "                 << hash[a].year << endl;    }    return 0;}

10.6

#include using namespace std;int main() {    string s;    while (cin >> s) {        map hash;        for (int i = 0; i < s.size(); i++)            for (int j = i; j  1) cout << c.first << " " << c.second << endl;    }    return 0;}

10.7

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

10.8

#include  using namespace std; int main(){    int n;    while(cin >> n){        string id, signIn, signOut;        string openId, closeId;        string signInTime = "24:00:00", signOutTime = "00:00:00";        for(int i = 0; i > id >> signIn >> signOut;            if(signIn  signOutTime){                signOutTime = signOut; closeId = id;            }        }        cout << openId << " " << closeId << endl;    }    return 0;}
  • map以红黑树实现:字典序
  • 迭代器可以++、–,但不支持+1
#include#include#includeusing namespace std; int main(){  int n;  string number,timein,timeout;//证件号、进入时间,退出时间  while(scanf("%d",&n)!=EOF){    mapFirst;    mapLast;    while(n--){      cin>>number>>timein>>timeout;      First[timein]=number;      Last[timeout]=number;    }       cout<second<<" "<second <<endl;  }      return 0;}

10.9

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

二叉树

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

二叉排序树

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

图论并查集

题目地址
例题11.1畅通工程(浙江大学复试上机题)http://t.cn/AiOvBHj9
例题11.2连通图(吉林大学复试上机题)http://t.cn/AiO77VoA
习题11.3第一题(上海交通大学复试上机题)http://t.cn/AiOhkgMJ

11.1

#include using namespace std;int const N = 1e3 + 10;int p[N];int find(int x) {    if (p[x] != x) p[x] = find(p[x]);    return p[x];}int n, m;int main() {    while (cin >> n >> m) {        for (int i = 1; i <= n; i++) p[i] = i;        for (int i = 0; i > a >> b;            // ^ 合并的时候是大类合并,不是两个节点合并            int fa = find(a), fb = find(b);            if (fa != fb) p[fa] = fb;        }        int count = -1;        for (int i = 1; i <= n; i++) {            if (find(i) == i) count++;        }        cout << count << endl;    }    return 0;}

11.2

#include using namespace std;int const N = 1010;int p[N];int find(int x) {    if (x != p[x]) p[x] = find(p[x]);    return p[x];}int n, m;int main() {    while (cin >> n >> m) {        if (n == 0 && m == 0) break;        for (int i = 1; i <= n; i++) p[i] = i;        for (int i = 1; i > a >> b;            int fa = find(a), fb = find(b);            if (fa != fb) p[fa] = fb;        }        int root = find(1);        int i;        for (i = 1; i <= n; i++) {            if (find(i) != root) break;        }        if (i == n + 1)            cout << "YES" << endl;        else            cout << "NO" << endl;    }    return 0;}

11.3

#include using namespace std;unordered_map p;int find(int x) {    if (p[x] != x) p[x] = find(p[x]);    return p[x];}int main() {    int a, b;    while (cin >> a >> b) {        // 第一次访问节点,初始化操作        if (p.find(a) == p.end()) p[a] = a;        if (p.find(b) == p.end()) p[b] = b;        int fa = find(a);        int fb = find(b);        if (fa != fb) p[fa] = fb;    }    int count = 0;    for (auto c : p)        if (c.first == c.second) count++;    cout << count << endl;    return 0;}

最小生成树

https://www.cnblogs.com/linxiaoxu/p/17679355.html#最小生成树

最短路径

https://www.cnblogs.com/linxiaoxu/p/17679355.html#最短路

拓扑排序

https://www.cnblogs.com/linxiaoxu/p/17679355.html#有向图的拓扑序列

关键路径

没刷

动态规划递归求解

题目地址
例题12.1N阶楼梯上楼问题(华中科技大学复试上机题)http://t.cn/Aij9Fr3V
习题12.2吃糖果(北京大学复试上机题)http://t.cn/AiQsVyKz

12.1

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

12.2

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

背包问题

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