今年学习的

目  录

实验一 三大基本结构的具体应用（一）

题目 1977：求中间数

题目 1011：最大公约数与最小公倍数

题目 1017：完数的判断

题目 1021：迭代法求平方根

题目 1018：有规律的数列求和

题目 1022：筛选 N 以内的素数

实验二 文字或算式题目的解题技巧（一）

题目 1016：水仙花数判断

题目 1136：求具有 abcd=(ab+cd)² 性质的四位数

题目 1434：回文数字

题目 1615：友好数

题目 1157：亲和数

题目 1234：检查一个数是否为质数

实验三 文字或算式题目的解题技巧（二）

题目 1：赛软件 × 比赛 = 软件比拼

题目 2：古堡算式 ABCDE × ? = EDCBA

题目 3：马虎的算式 ab × cde = adb × ce

题目 4：三羊献瑞

题目 5：立方和问题

题目 6：类似 625 的数字

实验四 数组的具体应用及其解题技巧（一）

题目 A：求平均值及大于平均值的个数

题目 B：日期是该年的第几天

题目 C：绝对值最小的数与最后一个数交换

题目 D：插入数到有序数组

题目 E：判断回文串

题目 F：字符串颠倒

实验五 数组的具体应用及其解题技巧（二）

题目 A：矩阵中绝对值最大的元素

题目 B：每行最大值位置放该行总和

题目 C：判断矩阵是否对称

题目 D：矩阵转置

题目 E：去掉字符串中的空格

题目 F：字符串编码（Run-Length Encoding）

题目 G：回文数加法步骤

实验六 函数的定义及其应用

题目 A：判断水仙花数（函数实现）

题目 B：数字间加空格输出（函数实现）

题目 C：字符串反序（函数实现）

题目 D：统计字符类型（函数实现）

题目 E：最大最小数与首尾交换（函数实现）

题目 F：循环移位（函数实现）

实验七 递归函数的定义及其应用

题目 1：输出 begin 到 end 之间的数

题目 2：递归求 1 到 n 之和

题目 3：递归求最大公约数

题目 4：递归求数组前 n 项之和 (mysum1)

题目 5：递归求数组 L 到 R 项之和 (mysum2)

题目 6：递归判断回文串

实验八 快速幂和二分法应用技巧

题目 1：P2249 查找（二分查找）

题目 2：2163 查找最接近的元素

题目 3：2088 快速幂

题目 4：2513 序列的第 k 个数

实验九 二分法的应用扩展——二分答案

题目 1：1885 分巧克力

题目 2：P2440 木材加工

题目 3：P1824 进击的奶牛

题目 4：P1182 数列分段 Section II

实验十 STL 应用技巧（一）

问题 A：重排序列

问题 B：s01 串变换

问题 C：统计单词出现次数

问题 D：去重 + 排序

问题 E：集合操作

问题 F：集合并集

实验十一 STL 应用技巧（二）

问题 A：统计自然数出现次数（map）

问题 B：删除重复元素（DelPack）

问题 C：统计单词数量

问题 D：统计不同单词个数

问题 E：输出最长单词

问题 F：倒数第二小的数

实验十二 STL 应用技巧（三）

问题 A：合并链表（按学号排序）

问题 B：1 到 n 的全排列

问题 C：求排列序号

问题 D：求第 n 个全排列

问题 E：7254 等式

问题 F：后缀子串排序

问题 G：括号匹配

实验十三 并查集及其应用技巧

问题 A：判断图是否连通

问题 B：畅通工程

问题 C：亲戚关系判断

问题 D：小区网络通信判断

实验十四 动态规划算法初步（一）

题目 1：1400 教学楼的楼梯（记忆化搜索）

题目 2：P1464 Function（记忆化搜索）

题目 3：P1216 数字三角形（记忆化搜索）

实验十五 动态规划算法初步（二）

问题 A：数字三角形（递推法）

问题 B：最大子段和

问题 C：最长不下降子序列（LIS）

程序训练实验速查手册

实验一 三大基本结构的具体应用（一）

题目 1977：求中间数

题目描述

#include <iostream>

using namespace std;

int main() {

    int a, b, c;

    cin >> a >> b >> c;

    if ((a > b && a < c) || (a > c && a < b)) cout << a << endl;

    else if ((b > a && b < c) || (b > c && b < a)) cout << b << endl;

    else cout << c << endl;

    return 0;

}

题目 1011：最大公约数与最小公倍数

题目描述

#include <iostream>

using namespace std;

int main() {

    int m, n, a, b, temp;

    cin >> m >> n;

    a = m; b = n;

    while (b != 0) { temp = b; b = a % b; a = temp; }

    int gcd = a, lcm = m * n / gcd;

    cout << gcd << " " << lcm << endl;

    return 0;

}

题目 1017：完数的判断

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n; cin >> n;

    for (int i = 1; i <= n; i++) {

        vector<int> factors;

        int sum = 0;

        for (int j = 1; j < i; j++)

            if (i % j == 0) { factors.push_back(j); sum += j; }

        if (sum == i) {

            cout << i << " its factors are ";

            for (auto f : factors) cout << f << " ";

            cout << endl;

        }

    }

    return 0;

}

题目 1021：迭代法求平方根

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int a; cin >> a;

    double x = a, last;

    do {

        last = x;

        x = (x + a / x) / 2.0;

    } while (fabs(x - last) >= 0.00001);

    printf("%.3lf", x);

    return 0;

}

题目 1018：有规律的数列求和

题目描述

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

    int N; cin >> N;

    double sum = 0, a = 2, b = 1;

    for (int i = 1; i <= N; i++) {

        sum += a / b;

        double temp = a;

        a = a + b;

        b = temp;

    }

    cout << fixed << setprecision(2) << sum;

    return 0;

}

题目 1022：筛选 N 以内的素数

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n; cin >> n;

    for (int i = 2; i <= n; i++) {

        int flag = 1;

        for (int j = 2; j * j <= i; j++)

            if (i % j == 0) { flag = 0; break; }

        if (flag) cout << i << endl;

    }

    return 0;

}

实验二 文字或算式题目的解题技巧（一）

题目 1016：水仙花数判断

题目描述

#include <iostream>

using namespace std;

int main() {

    for (int i = 100; i <= 999; i++) {

        int a = i % 10, b = i / 10 % 10, c = i / 100;

        if (a*a*a + b*b*b + c*c*c == i) cout << i << endl;

    }

    return 0;

}

题目 1136：求具有 abcd=(ab+cd)² 性质的四位数

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    for (int i = 1000; i <= 9999; i++) {

        int ab = i / 100, cd = i % 100;

        if ((ab + cd) * (ab + cd) == i) cout << i << " ";

    }

    return 0;

}

题目 1434：回文数字

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n; cin >> n;

    for (int i = 10000; i <= 999999; i++) {

        int sum = 0, temp = i, rev = 0;

        while (temp) { sum += temp % 10; rev = rev * 10 + temp % 10; temp /= 10; }

        if (rev == i && sum == n) cout << i << endl;

    }

    return 0;

}

题目 1615：友好数

题目描述

#include <bits/stdc++.h>

using namespace std;

int factor(int n) {

    int s = 0;

    for (int i = 1; i <= n / 2; i++)

        if (n % i == 0) s += i;

    return s;

}

int main() {

    int a, b; cin >> a >> b;

    if (factor(a) == b && factor(b) == a) cout << "yes";

    else cout << "no";

    return 0;

}

题目 1157：亲和数

题目描述

#include <iostream>

using namespace std;

int main() {

    int n; cin >> n;

    while (n--) {

        int x, y, s = 0; cin >> x >> y;

        for (int i = 1; i < x; i++) if (x % i == 0) s += i;

        if (s == y) {

            s = 0;

            for (int i = 1; i < y; i++) if (y % i == 0) s += i;

            if (s == x) cout << "YES" << endl;

            else cout << "NO" << endl;

        } else cout << "NO" << endl;

    }

    return 0;

}

题目 1234：检查一个数是否为质数

题目描述

#include <iostream>

using namespace std;

int main() {

    int n;

    while (cin >> n) {

        int ok = 1;

        if (n == 1) ok = 0;

        for (int i = 2; i * i <= n; i++)

            if (n % i == 0) { ok = 0; break; }

        cout << (ok ? 'Y' : 'N') << endl;

    }

    return 0;

}

实验三 文字或算式题目的解题技巧（二）

题目 1：赛软件 × 比赛 = 软件比拼

题目描述

#include <stdio.h>

int main() {

    int a, b, c, d, e; // a赛 b软 c件 d比 e拼

    for (a = 1; a <= 9; a++)

        for (b = 1; b <= 9; b++)

            for (c = 0; c <= 9; c++)

                for (d = 1; d <= 9; d++)

                    for (e = 0; e <= 9; e++) {

                        int x = a * 100 + b * 10 + c;

                        int y = d * 10 + a;

                        int z = b * 1000 + c * 100 + d * 10 + e;

                        if (x * y == z) printf("%d*%d=%d\n", x, y, z);

                    }

    return 0;

}

题目 2：古堡算式 ABCDE × ? = EDCBA

题目描述

#include <stdio.h>

int main() {

    int a, b, c, d, e, f;

    for (a = 1; a <= 9; a++)

        for (b = 0; b <= 9; b++)

            for (c = 0; c <= 9; c++)

                for (d = 0; d <= 9; d++)

                    for (e = 1; e <= 9; e++)

                        for (f = 1; f <= 9; f++) {

                            int x = a*10000 + b*1000 + c*100 + d*10 + e;

                            int z = e*10000 + d*1000 + c*100 + b*10 + a;

                            if (x*f == z && a!=b && a!=c && a!=d && a!=e

                                && b!=c && b!=d && b!=e && b!=f

                                && c!=d && c!=e && c!=f

                                && d!=e && d!=f && e!=f)

                                printf("%d*%d=%d\n", x, f, z);

                        }

    return 0;

}

题目 3：马虎的算式 ab × cde = adb × ce

题目描述

#include <stdio.h>

int main() {

    int a, b, c, d, e, cnt = 0;

    for (a = 1; a <= 9; a++)

        for (b = 1; b <= 9; b++)

            for (c = 1; c <= 9; c++)

                for (d = 1; d <= 9; d++)

                    for (e = 1; e <= 9; e++) {

                        int x = a*10+b, y = c*100+d*10+e;

                        int z = a*100+d*10+b, l = c*10+e;

                        if (x*y == z*l && a!=b && a!=c && a!=d && a!=e

                            && b!=c && b!=d && b!=e

                            && c!=d && c!=e && d!=e)

                            printf("%d*%d=%d*%d\n", x, y, z, l), cnt++;

                    }

    printf("cnt=%d\n", cnt);

    return 0;

}

题目 4：三羊献瑞

题目描述

#include <stdio.h>

int main() {

    int a, b, c, d, e, f, g, h;

    for (a = 1; a <= 9; a++) for (b = 0; b <= 9; b++)

        for (c = 0; c <= 9; c++) for (d = 0; d <= 9; d++)

            for (e = 1; e <= 9; e++) for (f = 0; f <= 9; f++)

                for (g = 0; g <= 9; g++) for (h = 0; h <= 9; h++) {

                    if (a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h

                        && b!=c && b!=d && b!=e && b!=f && b!=g && b!=h

                        && c!=d && c!=e && c!=f && c!=g && c!=h

                        && d!=e && d!=f && d!=g && d!=h

                        && e!=f && e!=g && e!=h && f!=g && f!=h && g!=h) {

                        int n1 = a*1000+b*100+c*10+d;

                        int n2 = e*1000+f*100+g*10+b;

                        int n3 = e*10000+f*1000+c*100+b*10+h;

                        if (n1+n2 == n3) { printf("三羊献瑞 = %d\n", n2); return 0; }

                    }

                }

    return 0;

}

题目 5：立方和问题

题目描述

#include <stdio.h>

int main() {

    int a, b, c, d;

    for (a = 1; a < 30; a++)

        for (b = a+1; b < 30; b++)

            for (c = b+1; c < 30; c++)

                for (d = c+1; d < 30; d++)

                    if (a*a*a + d*d*d == b*b*b + c*c*c)

                        printf("%d,%d,%d,%d\n", a, b, c, d);

    return 0;

}

题目 6：类似 625 的数字

题目描述

#include <stdio.h>

int main() {

    for (int n = 100; n <= 999; n++) {

        long long square = (long long)n * n;

        if (square % 1000 == n) printf("%d\n", n);

    }

    return 0;

}

实验四 数组的具体应用及其解题技巧（一）

题目 A：求平均值及大于平均值的个数

题目描述

#include <stdio.h>

int main() {

    int a[10], sum = 0, cnt = 0;

    for (int i = 0; i < 10; i++) { scanf("%d", &a[i]); sum += a[i]; }

    int avg = sum / 10;

    for (int i = 0; i < 10; i++) if (a[i] > avg) cnt++;

    printf("%d\n", cnt);

    return 0;

}

题目 B：日期是该年的第几天

题目描述

#include <stdio.h>

int main() {

    int y, m, d;

    int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    while (scanf("%d/%d/%d", &y, &m, &d) != EOF) {

        int sum = 0;

        for (int i = 0; i < m; i++) sum += month[i];

        sum += d;

        if (m > 2 && (y%4==0 && y%100!=0 || y%400==0)) sum++;

        printf("%d\n", sum);

    }

    return 0;

}

题目 C：绝对值最小的数与最后一个数交换

题目描述

#include <stdio.h>

#include <math.h>

int main() {

    int a[10], min = 0;

    for (int i = 0; i < 10; i++) scanf("%d", &a[i]);

    for (int i = 1; i < 10; i++)

        if (abs(a[i]) < abs(a[min])) min = i;

    int t = a[min]; a[min] = a[9]; a[9] = t;

    for (int i = 0; i < 10; i++) printf("%d ", a[i]);

    return 0;

}

题目 D：插入数到有序数组

题目描述

#include <stdio.h>

int main() {

    int a[10], x, i;

    for (i = 0; i < 9; i++) scanf("%d", &a[i]);

    scanf("%d", &x);

    for (i = 8; i >= 0 && a[i] > x; i--) a[i+1] = a[i];

    a[i+1] = x;

    for (i = 0; i < 10; i++) printf("%d\n", a[i]);

    return 0;

}

题目 E：判断回文串

题目描述

#include <stdio.h>

#include <string.h>

int main() {

    char s[256];

    gets(s);

    int len = strlen(s), flag = 1;

    for (int i = 0, j = len-1; i < j; i++, j--)

        if (s[i] != s[j]) { flag = 0; break; }

    printf(flag ? "Y" : "N");

    return 0;

}

题目 F：字符串颠倒

题目描述

#include <stdio.h>

#include <string.h>

int main() {

    char s[256];

    gets(s);

    for (int i = strlen(s)-1; i >= 0; i--) putchar(s[i]);

    return 0;

}

实验五 数组的具体应用及其解题技巧（二）

题目 A：矩阵中绝对值最大的元素

题目描述

#include <stdio.h>

#include <math.h>

int main() {

    int n, i, j, max = 0, i1 = 0, j1 = 0;

    scanf("%d", &n);

    int a[n][n];

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++) scanf("%d", &a[i][j]);

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

            if (abs(a[i][j]) > abs(max)) { max = a[i][j]; i1 = i; j1 = j; }

    printf("%d %d %d", max, i1+1, j1+1);

    return 0;

}

题目 B：每行最大值位置放该行总和

题目描述

#include <iostream>

using namespace std;

int main() {

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

    while (cin >> n >> m) {

        for (int i = 0; i < n; i++)

            for (int j = 0; j < m; j++) cin >> a[i][j];

        for (int i = 0; i < n; i++) {

            int sum = 0, t = 0, max = a[i][0];

            for (int j = 0; j < m; j++) {

                sum += a[i][j];

                if (max < a[i][j]) { max = a[i][j]; t = j; }

            }

            a[i][t] = sum;

        }

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) cout << a[i][j] << " ";

            cout << endl;

        }

    }

    return 0;

}

题目 C：判断矩阵是否对称

题目描述

#include <stdio.h>

int main() {

    int n, a[100][100];

    while (scanf("%d", &n) != EOF) {

        int flag = 1;

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);

        for (int i = 0; i < n; i++)

            for (int j = 0; j < i; j++)

                if (a[i][j] != a[j][i]) { flag = 0; break; }

        printf(flag ? "Yes!\n" : "No!\n");

    }

    return 0;

}

题目 D：矩阵转置

题目描述

#include <iostream>

using namespace std;

int main() {

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

    cin >> m >> n;

    for (int i = 0; i < m; i++)

        for (int j = 0; j < n; j++) { cin >> a[i][j]; b[j][i] = a[i][j]; }

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) cout << b[i][j] << " ";

        cout << endl;

    }

    return 0;

}

题目 E：去掉字符串中的空格

题目描述

#include <stdio.h>

int main() {

    char a[100];

    while (fgets(a, sizeof(a), stdin) != NULL)

        for (int i = 0; a[i] != '\0'; i++)

            if (a[i] != ' ') putchar(a[i]);

    return 0;

}

题目 F：字符串编码（Run-Length Encoding）

题目描述

#include <iostream>

#include <string>

using namespace std;

int main() {

    int n; cin >> n;

    while (n--) {

        string str; cin >> str;

        str += '*';

        int cnt = 0;

        for (int i = 0; i < (int)str.size(); i++) {

            if (str[i] != str[i+1]) {

                if (cnt) cout << cnt+1;

                if (str[i] != '*') cout << str[i];

                cnt = 0;

            } else cnt++;

        }

        cout << endl;

    }

    return 0;

}

题目 G：回文数加法步骤

题目描述

#include <iostream>

using namespace std;

int ishw(int m) {

    int a[20], n = 0;

    for (int i = 0; m; i++) { a[i] = m % 10; m /= 10; n = i; }

    for (int j = 0; j < n; j++, n--)

        if (a[j] != a[n]) return 0;

    return 1;

}

int newnum(int m) {

    int n = 0;

    while (m) { n = n*10 + m%10; m /= 10; }

    return n;

}

int main() {

    int n, m; cin >> n;

    while (n--) {

        cin >> m;

        int i;

        for (i = 0; i < 8; i++) {

            if (ishw(m)) break;

            m = m + newnum(m);

        }

        cout << (i < 8 ? i : 0) << endl;

    }

    return 0;

}

实验六 函数的定义及其应用

题目 A：判断水仙花数（函数实现）

题目描述

#include <iostream>

using namespace std;

int panduan(int n) {

    int a = n%10, b = n/10%10, c = n/100;

    return (a*a*a + b*b*b + c*c*c == n) ? 1 : 0;

}

int main() {

    int n; cin >> n;

    cout << panduan(n) << endl;

    return 0;

}

题目 B：数字间加空格输出（函数实现）

题目描述

#include <iostream>

using namespace std;

void myfun(int n) {

    int a = n%10, b = n/10%10, c = n/100%10, d = n/1000%10;

    printf("%d %d %d %d\n", d, c, b, a);

}

int main() {

    int n; cin >> n;

    myfun(n);

    return 0;

}

题目 C：字符串反序（函数实现）

题目描述

#include <iostream>

#include <cstring>

using namespace std;

void myreverse(char s[]) {

    int len = strlen(s);

    for (int i = 0, j = len-1; i < j; i++, j--) {

        char t = s[i]; s[i] = s[j]; s[j] = t;

    }

}

int main() {

    char s[100]; cin >> s;

    myreverse(s);

    cout << s;

    return 0;

}

题目 D：统计字符类型（函数实现）

题目描述

#include <iostream>

using namespace std;

void myfun(char s[], int cnt[]) {

    for (int i = 0; s[i] != '\0'; i++) {

        if (s[i]>='a'&&s[i]<='z' || s[i]>='A'&&s[i]<='Z') cnt[0]++;

        else if (s[i]>='0'&&s[i]<='9') cnt[1]++;

        else if (s[i]==' ') cnt[2]++;

        else cnt[3]++;

    }

}

int main() {

    char s[200]; int cnt[4] = {0};

    scanf("%[^\n]", s);

    myfun(s, cnt);

    for (int i = 0; i < 4; i++) cout << cnt[i] << " ";

    return 0;

}

题目 E：最大最小数与首尾交换（函数实现）

题目描述

#include <cstdio>

#include <algorithm>

using namespace std;

void input(int a[]) { for (int i = 0; i < 10; i++) scanf("%d", &a[i]); }

void deal(int a[]) {

    int max = 0, min = 0;

    for (int i = 1; i < 10; i++) {

        if (a[i] > a[max]) max = i;

        if (a[i] < a[min]) min = i;

    }

    swap(a[0], a[min]);

    if (max == 0) max = min;

    swap(a[9], a[max]);

}

void output(int a[]) { for (int i = 0; i < 10; i++) printf("%d ", a[i]); }

int main() {

    int a[10];

    input(a); deal(a); output(a);

    return 0;

}

题目 F：循环移位（函数实现）

题目描述

#include <cstdio>

unsigned int move(unsigned int value, int n) {

    const int BITS = 32;

    if (n > 0) return (value >> n) | (value << (BITS - n));

    else { n = -n; return (value << n) | (value >> (BITS - n)); }

}

int main() {

    unsigned int x; int n;

    scanf("%u%d", &x, &n);

    printf("%u\n", move(x, n));

    return 0;

}

实验七 递归函数的定义及其应用

题目 1：输出 begin 到 end 之间的数

题目描述

#include <iostream>

using namespace std;

void fun(int begin, int end) {

    if (begin > end) return;

    cout << begin << endl;

    fun(begin + 1, end);

}

int main() {

    int a, b; cin >> a >> b;

    fun(a, b);

    return 0;

}

题目 2：递归求 1 到 n 之和

题目描述

#include <iostream>

using namespace std;

int mysum(int n) {

    if (n == 0) return 0;

    return mysum(n-1) + n;

}

int main() {

    int n; cin >> n;

    cout << mysum(n) << endl;

    return 0;

}

题目 3：递归求最大公约数

题目描述

#include <iostream>

using namespace std;

int gcd(int m, int n) {

    if (m % n == 0) return n;

    return gcd(n, m % n);

}

int main() {

    int m, n; cin >> m >> n;

    cout << gcd(m, n) << endl;

    return 0;

}

题目 4：递归求数组前 n 项之和 (mysum1)

题目描述

#include <iostream>

using namespace std;

int mysum1(int a[], int n) {

    if (n == 0) return 0;

    return a[n-1] + mysum1(a, n-1);

}

int main() {

    int n, a[100]; cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    cout << mysum1(a, n) << endl;

    return 0;

}

题目 5：递归求数组 L 到 R 项之和 (mysum2)

题目描述

#include <iostream>

using namespace std;

int mysum2(int a[], int L, int R) {

    if (L > R) return 0;

    return a[L] + mysum2(a, L+1, R);

}

int main() {

    int n, a[100]; cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    cout << mysum2(a, 0, n-1) << endl;

    return 0;

}

题目 6：递归判断回文串

题目描述

#include <iostream>

#include <cstring>

using namespace std;

int fun(char s[], int L, int R) {

    if (L >= R) return 1;

    if (s[L] != s[R]) return 0;

    return fun(s, L+1, R-1);

}

int main() {

    char s[100]; gets(s);

    cout << (fun(s, 0, strlen(s)-1) ? "yes" : "no") << endl;

    return 0;

}

实验八 快速幂和二分法应用技巧

题目 1：P2249 查找（二分查找）

题目描述

#include <bits/stdc++.h>

using namespace std;

int binsearch(int a[], int n, int x) {

    int L = 0, R = n;

    while (L < R) {

        int mid = (L + R) / 2;

        if (x > a[mid]) L = mid + 1;

        else R = mid;

    }

    return L;

}

int a[1000002];

int main() {

    int m, n, x;

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> a[i];

    while (m--) {

        cin >> x;

        int pos = binsearch(a, n, x);

        if (a[pos] == x) cout << pos+1 << " ";

        else cout << -1 << " ";

    }

    return 0;

}

题目 2：2163 查找最接近的元素

题目描述

#include <bits/stdc++.h>

using namespace std;

int binsearch(int a[], int n, int x) {

    int L = 0, R = n;

    while (L < R) {

        int mid = (L + R) / 2;

        if (x > a[mid]) L = mid + 1;

        else R = mid;

    }

    if (L == 0) return a[0];

    if (L == n) return a[n-1];

    if (x - a[L-1] < a[L] - x) return a[L-1];

    else return a[L];

}

int a[100002];

int main() {

    int m, n, x;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    scanf("%d", &m);

    while (m--) {

        scanf("%d", &x);

        printf("%d\n", binsearch(a, n, x));

    }

    return 0;

}

题目 3：2088 快速幂

题目描述

#include <iostream>

using namespace std;

typedef long long LL;

LL qpow(LL a, LL b, LL p) {

    LL res = 1;

    while (b) {

        if (b & 1) res = res * a % p;

        a = a * a % p;

        b >>= 1;

    }

    return res;

}

int main() {

    LL a, b; int p;

    cin >> a >> b >> p;

    cout << qpow(a, b, p) << endl;

    return 0;

}

题目 4：2513 序列的第 k 个数

题目描述

#include <iostream>

using namespace std;

typedef long long LL;

const LL MOD = 200907;

LL qpow(LL a, LL b) {

    LL res = 1;

    while (b) { if (b&1) res = res*a%MOD; a = a*a%MOD; b >>= 1; }

    return res;

}

int main() {

    int T; cin >> T;

    while (T--) {

        LL a, b, c, k;

        cin >> a >> b >> c >> k;

        if (b - a == c - b) { // 等差数列

            LL d = b - a;

            cout << (a + (k-1)*d % MOD + MOD) % MOD << endl;

        } else { // 等比数列

            LL q = b / a;

            cout << a * qpow(q, k-1) % MOD << endl;

        }

    }

    return 0;

}

实验九 二分法的应用扩展——二分答案

题目 1：1885 分巧克力

题目描述

#include <iostream>

using namespace std;

int n, k, h[100005], w[100005];

int check(int len) {

    int sum = 0;

    for (int i = 0; i < n; i++) sum += (h[i]/len) * (w[i]/len);

    return sum >= k;

}

int main() {

    cin >> n >> k;

    for (int i = 0; i < n; i++) cin >> h[i] >> w[i];

    int L = 1, R = 100000;

    while (L < R) {

        int mid = (L + R + 1) / 2;

        if (check(mid)) L = mid;

        else R = mid - 1;

    }

    cout << L;

    return 0;

}

题目 2：P2440 木材加工

题目描述

#include <iostream>

using namespace std;

int n, k, h[100005];

int check(int len) {

    int sum = 0;

    for (int i = 0; i < n; i++) sum += h[i] / len;

    return sum >= k;

}

int main() {

    cin >> n >> k;

    int L = 0, R = 0;

    for (int i = 0; i < n; i++) {

        cin >> h[i];

        if (h[i] > R) R = h[i];

    }

    while (L < R) {

        int mid = (L + R + 1) / 2;

        if (check(mid)) L = mid;

        else R = mid - 1;

    }

    cout << L;

    return 0;

}

题目 3：P1824 进击的奶牛

题目描述

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, x[100005];

int check(int d) {

    int cnt = 1, last = x[0];

    for (int i = 1; i < n; i++)

        if (x[i] - last >= d) { cnt++; last = x[i]; }

    return cnt >= m;

}

int main() {

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> x[i];

    sort(x, x + n);

    int L = 1, R = x[n-1] - x[0];

    while (L < R) {

        int mid = (L + R + 1) / 2;

        if (check(mid)) L = mid;

        else R = mid - 1;

    }

    cout << L;

    return 0;

}

题目 4：P1182 数列分段 Section II

题目描述

#include <iostream>

using namespace std;

int n, m, a[100005];

int check(int mid) {

    int cnt = 1, sum = 0;

    for (int i = 0; i < n; i++) {

        if (sum + a[i] > mid) { cnt++; sum = a[i]; }

        else sum += a[i];

    }

    return cnt <= m;

}

int main() {

    cin >> n >> m;

    int L = 0, R = 0;

    for (int i = 0; i < n; i++) {

        cin >> a[i];

        if (a[i] > L) L = a[i];

        R += a[i];

    }

    while (L < R) {

        int mid = (L + R) / 2;

        if (check(mid)) R = mid;

        else L = mid + 1;

    }

    cout << L;

    return 0;

}

实验十 STL 应用技巧（一）

问题 A：重排序列

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    vector<int> v1;

    int n, k1, kn; cin >> n;

    while (n--) {

        cin >> k1; v1.push_back(k1);

        for (int i = 1; i <= 8; i++) {

            cin >> kn;

            if (kn > k1) v1.push_back(kn);

            else v1.insert(v1.begin(), kn);

        }

        for (auto x : v1) cout << x << " ";

        cout << endl;

        v1.clear();

    }

    return 0;

}

问题 B：s01 串变换

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1 = "0", s2;

    int n; cin >> n;

    while (n--) {

        for (char ch : s1)

            s2 += (ch == '0' ? "1" : "01");

        s1 = s2; s2 = "";

    }

    cout << s1;

    return 0;

}

问题 C：统计单词出现次数

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, m, cnt = 0;

    string s1, s2; cin >> n >> s1 >> m >> s2;

    int pos = s1.find(s2);

    while (pos != -1) { cnt++; pos = s1.find(s2, pos+1); }

    cout << cnt;

    return 0;

}

问题 D：去重 + 排序

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, x; set<int> s1;

    cin >> n;

    for (int i = 0; i < n; i++) { cin >> x; s1.insert(x); }

    cout << s1.size() << endl;

    for (auto it : s1) cout << it << " ";

    return 0;

}

问题 E：集合操作

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    set<int> s;

    int k; cin >> k;

    while (k--) {

        int op, x; cin >> op >> x;

        if (op == 1) s.insert(x);

        else cout << (s.count(x) ? "True" : "False") << endl;

    }

    return 0;

}

问题 F：集合并集

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    set<int> s1;

    int n, m, x;

    while (cin >> n >> m) {

        for (int i = 0; i < n+m; i++) { cin >> x; s1.insert(x); }

        for (auto it : s1) cout << it << " ";

        cout << endl; s1.clear();

    }

    return 0;

}

实验十一 STL 应用技巧（二）

问题 A：统计自然数出现次数（map）

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, x; map<int, int> mp;

    cin >> n;

    while (n--) { cin >> x; mp[x]++; }

    for (auto it : mp) cout << it.first << " " << it.second << endl;

    return 0;

}

问题 B：删除重复元素（DelPack）

题目描述

#include <bits/stdc++.h>

using namespace std;

void DelPack(string &s) {

    map<char, int> mp;

    for (char ch : s) mp[ch]++;

    string s1;

    for (char ch : s) if (mp[ch] == 1) s1 += ch;

    s = s1;

}

int main() {

    string s; getline(cin, s);

    DelPack(s); cout << s;

    return 0;

}

问题 C：统计单词数量

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1, word; getline(cin, s1);

    stringstream ss; ss << s1;

    vector<string> v1;

    while (ss >> word) v1.push_back(word);

    cout << v1.size() << endl;

    return 0;

}

问题 D：统计不同单词个数

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1, word; getline(cin, s1);

    stringstream ss; ss << s1;

    set<string> mys1;

    while (ss >> word) mys1.insert(word);

    cout << mys1.size() << endl;

    return 0;

}

问题 E：输出最长单词

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1, word; getline(cin, s1);

    stringstream ss; ss << s1;

    vector<string> v1;

    while (ss >> word) v1.push_back(word);

    int maxlen = 0, k = 0;

    for (int i = 0; i < (int)v1.size(); i++)

        if ((int)v1[i].size() > maxlen) { maxlen = v1[i].size(); k = i; }

    cout << v1[k];

    return 0;

}

问题 F：倒数第二小的数

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int a[200], t, n; cin >> t;

    while (t--) {

        cin >> n;

        for (int i = 0; i < n; i++) cin >> a[i];

        sort(a, a + n);

        cout << a[1] << endl;

    }

    return 0;

}

实验十二 STL 应用技巧（三）

问题 A：合并链表（按学号排序）

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    map<int, int> mp;

    int n, m, num, score; cin >> n >> m;

    for (int i = 0; i < n+m; i++) { cin >> num >> score; mp[num] = score; }

    for (auto x : mp) cout << x.first << " " << x.second << endl;

    return 0;

}

问题 B：1 到 n 的全排列

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int a[10] = {1,2,3,4,5,6,7,8,9,10}, n;

    cin >> n;

    do {

        for (int i = 0; i < n; i++) cout << a[i] << " ";

        cout << endl;

    } while (next_permutation(a, a+n));

    return 0;

}

问题 C：求排列序号

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1, s2; int n = 0;

    cin >> s1; s2 = s1;

    sort(s1.begin(), s1.end());

    do {

        if (s1 == s2) { cout << n << endl; break; }

        n++;

    } while (next_permutation(s1.begin(), s1.end()));

    return 0;

}

问题 D：求第 n 个全排列

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1 = "0123456789";

    int n, cnt = 0; cin >> n;

    do {

        cnt++;

        if (cnt == n) { cout << s1 << endl; break; }

    } while (next_permutation(s1.begin(), s1.end()));

    return 0;

}

问题 E：7254 等式

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    int a[9] = {1,2,3,4,5,6,7,8,9};

    do {

        int x = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];

        int y = a[4]*10 + a[5], z = a[6]*100 + a[7]*10 + a[8];

        if (x == y*z) printf("%d = %d x %d\n", x, y, z);

        int x1 = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];

        int y1 = a[4], z1 = a[5]*1000 + a[6]*100 + a[7]*10 + a[8];

        if (x1 == y1*z1) printf("%d = %d x %d\n", x1, y1, z1);

    } while (next_permutation(a, a+9));

    return 0;

}

问题 F：后缀子串排序

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s1;

    while (cin >> s1) {

        vector<string> v1;

        int len = s1.size();

        for (int i = 0; i < len; i++) v1.push_back(s1.substr(i));

        sort(v1.begin(), v1.end());

        for (auto x : v1) cout << x << endl;

        v1.clear();

    }

    return 0;

}

问题 G：括号匹配

题目描述

#include <bits/stdc++.h>

using namespace std;

int main() {

    stack<char> st;

    char ch;

    while ((ch = getchar()) != '@') {

        if (ch == '(') st.push(ch);

        else if (ch == ')') {

            if (st.empty()) { cout << "NO" << endl; return 0; }

            st.pop();

        }

    }

    cout << (st.empty() ? "YES" : "NO") << endl;

    return 0;

}

实验十三 并查集及其应用技巧

问题 A：判断图是否连通

题目描述

#include <iostream>

using namespace std;

int father[100003];

void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }

int Find(int x) { return x == father[x] ? x : Find(father[x]); }

void Union(int x, int y) {

    int rx = Find(x), ry = Find(y);

    if (rx != ry) father[rx] = ry;

}

int main() {

    int n, m, x, y;

    while (cin >> n >> m) {

        if (n==0 && m==0) break;

        Init(n);

        while (m--) { cin >> x >> y; Union(x, y); }

        int cnt = 0;

        for (int i = 1; i <= n; i++) if (i == father[i]) cnt++;

        cout << (cnt == 1 ? "YES" : "NO") << endl;

    }

    return 0;

}

问题 B：畅通工程

题目描述

#include <iostream>

using namespace std;

int father[100003];

void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }

int Find(int x) { return x == father[x] ? x : Find(father[x]); }

void Union(int x, int y) {

    int rx = Find(x), ry = Find(y);

    if (rx != ry) father[rx] = ry;

}

int main() {

    int n, m, x, y;

    while (cin >> n && n) {

        Init(n); cin >> m;

        while (m--) { cin >> x >> y; Union(x, y); }

        int cnt = 0;

        for (int i = 1; i <= n; i++) if (i == father[i]) cnt++;

        cout << cnt - 1 << endl;

    }

    return 0;

}

问题 C：亲戚关系判断

题目描述

#include <iostream>

using namespace std;

int father[100003];

void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }

int Find(int x) { return x == father[x] ? x : father[x] = Find(father[x]); }

void Union(int x, int y) {

    int rx = Find(x), ry = Find(y);

    if (rx != ry) father[rx] = ry;

}

int main() {

    int n, m, q, x, y;

    cin >> n >> m; Init(n);

    while (m--) { scanf("%d%d", &x, &y); Union(x, y); }

    cin >> q;

    while (q--) {

        scanf("%d%d", &x, &y);

        printf(Find(x) == Find(y) ? "Yes\n" : "No\n");

    }

    return 0;

}

问题 D：小区网络通信判断

题目描述

#include <iostream>

using namespace std;

int father[100003];

void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }

int Find(int x) { return x == father[x] ? x : Find(father[x]); }

void Union(int x, int y) {

    int rx = Find(x), ry = Find(y);

    if (rx != ry) father[rx] = ry;

}

int main() {

    int n, m, x, y;

    cin >> n >> m; Init(n);

    while (m--) { cin >> x >> y; Union(x, y); }

    cin >> x >> y;

    cout << (Find(x) == Find(y) ? "Yes" : "No") << endl;

    return 0;

}

实验十四 动态规划算法初步（一）

题目 1：1400 教学楼的楼梯（记忆化搜索）

题目描述

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL f[100] = {0};

LL myfun(int n) {

    if (n == 1 || n == 2) return 1;

    if (f[n] != 0) return f[n];

    return f[n] = myfun(n-1) + myfun(n-2);

}

int main() {

    int t, n; cin >> t;

    while (t--) { cin >> n; cout << myfun(n) << endl; }

    return 0;

}

题目 2：P1464 Function（记忆化搜索）

题目描述

#include <iostream>

using namespace std;

typedef long long LL;

LL p[21][21][21];

LL w(LL a, LL b, LL c) {

    if (a <= 0 || b <= 0 || c <= 0) return 1;

    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);

    if (p[a][b][c] != 0) return p[a][b][c];

    if (a < b && b < c)

        return p[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);

    return p[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1);

}

int main() {

    LL a, b, c;

    while (cin >> a >> b >> c && !(a==-1 && b==-1 && c==-1))

        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));

    return 0;

}

题目 3：P1216 数字三角形（记忆化搜索）

题目描述

#include <iostream>

#include <algorithm>

using namespace std;

const int MAXR = 1005;

int a[MAXR][MAXR], mem[MAXR][MAXR], r;

int dfs(int i, int j) {

    if (i == r) return a[i][j];

    if (mem[i][j] != -1) return mem[i][j];

    return mem[i][j] = a[i][j] + max(dfs(i+1, j), dfs(i+1, j+1));

}

int main() {

    fill(&mem[0][0], &mem[MAXR][0], -1);

    cin >> r;

    for (int i = 1; i <= r; i++)

        for (int j = 1; j <= i; j++) cin >> a[i][j];

    cout << dfs(1, 1) << endl;

    return 0;

}

实验十五 动态规划算法初步（二）

问题 A：数字三角形（递推法）

题目描述

#include <iostream>

using namespace std;

const int N = 105;

int a[N][N], dp[N][N];

int main() {

    int t, n; cin >> t;

    while (t--) {

        cin >> n;

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= i; j++) cin >> a[i][j];

        for (int j = 1; j <= n; j++) dp[n][j] = a[n][j];

        for (int i = n-1; i >= 1; i--)

            for (int j = 1; j <= i; j++)

                dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);

        cout << dp[1][1] << endl;

    }

    return 0;

}

问题 B：最大子段和

题目描述

#include <iostream>

using namespace std;

const int N = 100005;

int a[N], dp[N];

int main() {

    int n; cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    dp[0] = a[0];

    int maxv = dp[0];

    for (int i = 1; i < n; i++) {

        dp[i] = max(dp[i-1] + a[i], a[i]);

        if (dp[i] > maxv) maxv = dp[i];

    }

    cout << maxv;

    return 0;

}

问题 C：最长不下降子序列（LIS）

题目描述

#include <iostream>

using namespace std;

const int N = 10006;

int a[N], dp[N];

int main() {

    int n; cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {

        dp[i] = 1;

        for (int j = 1; j < i; j++)

            if (a[i] >= a[j]) dp[i] = max(dp[i], dp[j] + 1);

    }

    int maxv = dp[1];

    for (int i = 2; i <= n; i++)

        if (dp[i] > maxv) maxv = dp[i];

    cout << maxv;

    return 0;

}