刷题地址：晴问算法 (sunnywhy.com)

入门模拟

简单模拟

3N+1猜想

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main() {
    int n, res = 0;
    scanf("%d", &n);
    while (n != 1) {
        if (n % 2 == 0) n /= 2;
        else n = (3 * n + 1) / 2;
        res ++;
    }
    printf("%d", res);
    return 0;
}

判断三角形

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a + b > c && a + c > b && b + c > a) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

单调递增序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
const int MAXN = 101;
int nums[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    bool flag = true;
    for (int i = 1; i < n; i++) {
        if (nums[i] < nums[i - 1]) {
            flag = false;
            break;
        }
    }
    printf(flag ? "YES" : "NO");
    return 0;
}

数列奇数和

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>

int main() {
    int n, x, res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (x % 2 == 1) res += x;
    }
    printf("%d", res);
    return 0;
}

三位数

1
2
3
4
5
6
7
8
9
10
#include <cstdio>
int main() {
    int n, bai = 0, shi = 0, ge = 0;
    scanf("%d", &n);
    bai = n / 100;
    shi = n % 100 / 10;
    ge = n % 10;
    printf("%d %d %d", bai, shi, ge);
    return 0;
}

水仙花数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <cmath>
int main() {
    int n, bai, shi, ge;
    scanf("%d", &n);
    bai = n / 100;
    shi = n % 100 / 10;
    ge = n % 10;
    if (pow(bai, 3) + pow(shi, 3) + pow(ge, 3) == n) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

水仙花数II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
bool check(int x) {
    int a = x / 100;
    int b = x % 100 / 10;
    int c = x % 10;
    return a * a * a + b * b * b + c * c * c == x;
}
const int MAXN = 100;
int nums[MAXN];
int main() {
    int a, b, idx = 0;
    scanf("%d%d", &a, &b);
    for (int i = a; i <= b; i++) {
        if (check(i)) {
            nums[idx++] = i;
        }
    }
    for (int i = 0; i < idx; i++) {
        printf("%d", nums[i]);
        if (i < idx - 1) printf(" ");
    }
    if (idx == 0) printf("NO");
    return 0;
}

2的幂

1
2
3
4
5
6
7
8
9
10
#include <cstdio>
int main() {
    int n, res = 1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        res = (res * 2) % 1007;
    }
    printf("%d", res);
    return 0;
}

查找元素

查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
const int MAXN = 101;
int nums[MAXN];
int main() {
    int n, x, res = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    scanf("%d", &x);
    for (int i = 0; i < n; i++) {
        if (x == nums[i]) {
            res = i + 1;
            break;
        }
    }
    if (res == -1) printf("NO");
    else printf("%d", res);
    return 0;
}

统计元素个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
const int MAXN = 101;
int nums[MAXN];
int main() {
    int n, x, res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    scanf("%d", &x);
    for (int i = 0; i < n; i++) {
        if (x == nums[i]) {
            res ++;
        }
    }
    printf("%d", res);
    return 0;
}

寻找元素对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
const int MAXN = 1001;
int nums[MAXN];
int main() {
    int n, k, res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    scanf("%d", &k);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == k) res ++;
        }
    }
    printf("%d", res);
    return 0;
}

图形输出

等腰直角三角形

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("*");
        }
        printf("\n");
    }
    return 0;
}

等腰直角三角形II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            if (j == 0 || j == i || i == n - 1) {
                printf("*");
            } else {
                printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}

画X

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j == i || j == n - i - 1) {
                printf("*");
            } else if (j > i && j > n - i - 1) {
                continue;
            } else {
                printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}

日期处理

判断闰年

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
int main() {
    int n;
    scanf("%d", &n);
    if (n % 400 == 0 || n % 100 != 0 and n % 4 == 0) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

日期加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
int dayOfMonth[2][13] = {
    {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
bool isLeapYear(int year) {
    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}
void addOneDay(int &year, int &month, int &day) {
    day++;
    if (day > dayOfMonth[isLeapYear(year)][month]) {
        month ++;
        day = 1;
    }
    if (month > 12) {
        year++;
        month = 1;
    }
}
int main() {
    int year, month, day, n;
    scanf("%d-%d-%d", &year, &month, &day);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        addOneDay(year, month, day);
    }
    printf("%04d-%02d-%02d", year, month, day);
    return 0;
}

日期减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
int daOfMonth[2][13] = {
    {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
bool isLeapYear(int year) {
    return (year % 400 == 0 || year % 4 == 0 and year % 100 != 0);
}
void subDay(int &year, int &month, int &day){
    day--;
    if (day == 0) {
        month--;
        if (month == 0) {
            year --;
            month = 12;
        }
        day = daOfMonth[isLeapYear(year)][month];
    }
}
int main() {
    int year, month, day, n;
    scanf("%d-%d-%d", &year, &month, &day);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        subDay(year, month, day);
    }
    printf("%04d-%02d-%02d", year, month,day);
    return 0;
}

一年中的第几天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
int dayOfMonth[2][13] = {
    {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
bool isLeapYear(int year) {
    return (year % 400 == 0 || year % 4 == 0 && year % 100 != 0);
}

int main() {
    int year, month, day;
    scanf("%d-%d-%d", &year, &month, &day);
    int res = day;
    for (int i = 1; i < month; i++) {
        res += dayOfMonth[isLeapYear(year)][i];
    }
    printf("%d", res);
    return 0;
}

日期先后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
bool isBefore(int year1, int month1, int day1, int year2, int month2, int day2) {
    if (year1 != year2) {
        return year1 < year2;
    }
    if (month1 != month2) {
        return month1 < month2;
    }
    return day1 < day2;
}
int main() {
    int year1, year2, month1, month2, day1, day2;
    scanf("%d-%d-%d", &year1, &month1, &day1);
    scanf("%d-%d-%d", &year2, &month2, &day2);
    printf(isBefore(year1, month1, day1, year2, month2, day2) ? "YES" : "NO");
    return 0;
}

进制转换

十进制转二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
const int MAXN = 11;
int nums[MAXN];
int main() {
    int n, idx = 0;
    scanf("%d", &n);
    while (n != 0) {
        nums[idx++] = n % 2;
        n /= 2;
    }
    for (int i = idx - 1; i >= 0; i--) {
        printf("%d", nums[i]);
    }
    return 0;
}

二进制转十进制

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main() {
    int s, res = 0, p = 1;
    scanf("%d", &s);
    while (s != 0) {
        res += p * (s % 10);
        p *= 2;
        s /= 10;
    }
    printf("%d", res);
    return 0;
}

十进制转K进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
const int MAXN = 101;
int nums[MAXN];

int main() {
    int n, k, idx = 0;
    scanf("%d %d", &n, &k);
    while (n != 0) {
        nums[idx++] = n % k;
        n /= k;
    }
    for (int i = idx - 1; i >= 0; i--) {
        if (nums[i] > 9) {
            printf("%c", nums[i] - 10 + 'A');
        } else {
            printf("%d", nums[i]);
        }
    }
    return 0;
}

K进制转十进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <cstring>
const int MAXN = 10;
char nums[MAXN];
int main() {
    int k, res = 0, p = 1;
    scanf("%s %d", nums, &k);
    for (int i = strlen(nums) - 1; i >= 0 ; i--) {
        int t = (nums[i] >= '0' && nums[i] <= '9') ? (nums[i] - '0') : (nums[i] - 'A' + 10);
        res += p * t;
        p *= k;
    }
    printf("%d", res);
    return 0;    
}

字符串处理

回文字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cstring>
using namespace std;
int main() {
    string str;
    cin >> str;
    bool flag = true;
    int n = str.length();
    for (int i = 0; i < n / 2; i++) {
        if (str[i] != str[str.length() - i - 1]) flag = false;
    }
    printf(flag ? "YES" : "NO");
    return 0;   
}

单词倒序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
const int MAXN = 500;
const int MAXL = 11;
char str[MAXN][MAXL], num = 0;
int main() {
    while (scanf("%s", str[num]) != EOF) {
        num++;
    }
    for (int i = num - 1; i >= 0; i--) {
        printf("%s", str[i]);
        if (i > 0) printf(" ");
    }
    return 0;
}

单词倒序II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstring>
const int MAXN = 1000;
const int MAXM = 11;
char str[MAXN][MAXM], num = 0;
int main() {
    while (scanf("%s", str[num]) != EOF) {
        num++;
    }
    for (int i = 0; i < num; i++) {
        for (int j = strlen(str[i]) - 1; j >= 0; j--) {
            printf("%c", str[i][j]);
        }
        if (i < num - 1) printf(" ");
    }
    return 0;
}

单词数

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
const int MAXN = 500;
const int MAXM = 11;
char str[MAXN][MAXM], num = 0;
int main() {
    while (scanf("%s", str[num]) != EOF) {
        num++;
    }
    printf("%d", num);
    return 0;
}

首字母大写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <cstring>
const int MAXN = 500;
const int MAXM = 11;
char str[MAXN][MAXM];
int num = 0;
int main() {
    while (scanf("%s", str[num]) != EOF) {
        num++;
    }
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < strlen(str[i]); j++) {
            if (j == 0) printf("%c", str[i][j] - 32);
            else printf("%c", str[i][j]);
        }
        if (i < num - 1) printf(" ");
    }
    return 0;
}

公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 20;
const int MAXM = 51;
char str[MAXN][MAXM];
int main() {
    int n, minl = 51; 
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", str[i]);
        minl = min(minl, (int)strlen(str[i]));
    }
    for (int j = 0; j < minl; j++) {
        char a = str[0][j];
        bool flag = true;
        for (int i = 1; i < n; i++) {
            if (a != str[i][j]) {
                flag = false;
                break;
            }
        }
        if (flag) printf("%c", a);
        else break;
    }
    return 0;
}

连续相同字符统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <cstring>
const int MAXL = 101;
char str[MAXL];
int main() {
    scanf("%s", str);
    int idx = 0, len = strlen(str);
    while (idx < len) {
        printf("%c ", str[idx++]);
        int cnt = 1;
        while (idx < len && str[idx] == str[idx - 1]) {
            cnt ++;
            idx ++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

C语言合法变量名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cstring>
const int MAXL = 21;
char str[MAXL];
int main() {
    scanf("%s", str);
    bool result = true;
    int len = strlen(str);
    if (!((str[0] >= 'A' && str[0] <= 'Z') || (str[0] >= 'a' && str[0] <= 'z') || str[0] == '_')) {
        result = false;
    }
    for (int i = 1; i < len; i++) {
        if (!((str[i] >= 'A' && str[i] <= 'Z') || (str[i] >= 'a' && str[i] <= 'z') || (str[i] >= '0' && str[i] <= '9') || str[i] == '_')) {
            result = false;
            break;
        }
    }
    printf(result ? "YES" : "NO");
    return 0;
}

算法初步

排序

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 51;
int a[MAXN], n;

void selectSort() {
    for (int i = 0; i < n; i++) {
        int k = i;
        for (int j = i; j < n; j++) {
            if (a[j] < a[k]) {
                k = j;
            }
        }
        swap(a[i], a[k]);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    selectSort();
    for (int i = 0; i < n; i++) {
        printf("%d", a[i]);
        printf(i < n - 1 ? " " : "\n");
    }
    return 0;
}

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
const int MAXN = 51;
int nums[MAXN], n;
void insertSort() {
    for (int i = 1; i < n; i++) {
        int t = nums[i];
        int j = i;
        while (j - 1 >= 0 && nums[j - 1] > t) {
            nums[j] = nums[j - 1];
            j --;
        }
        nums[j] = t;
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    insertSort();
    for (int i = 0; i < n; i++) {
        printf("%d", nums[i]);
        printf(i < n - 1 ? " " : "\n");
    }
    return 0;
}

整数升序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 50;
int a[MAXN], n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        printf("%d", a[i]);
        printf(i < n - 1 ? " " : "\n");
    }
    return 0;
}

整数降序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 51;
int nums[MAXN], n;
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    sort(nums, nums + n, cmp);
    for (int i = 0; i < n; i++) {
        printf("%d", nums[i]);
        printf(i < n - 1 ? " " : "\n");
    }
    return 0;
}

字符串升序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 51;
int n;
string str[MAXN];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }
    sort(str, str + n);
    for (int i = 0; i < n; i++) {
        cout << str[i] << endl;
    }
    return 0;
}

字符串降序排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 51;
string str[MAXN];
int n;
bool cmp(string a, string b) {
    return a > b;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }
    sort(str, str + n, cmp);
    for (int i = 0; i < n; i++) {
        cout << str[i] << endl;
    }
    return 0;
}

考生排序

1

散列

递归

贪心

二分

双指针

其他高效技巧与算法

数学问题

简单数学

最大公约数与最小公倍数

分数的四则运算

素数

质因子分解

大整数运算

扩展欧几里得算法

组合数

数据结构I

栈

队列

链表

搜索

深度优先搜索

广度优先搜索

数据结构II

树与二叉树

二叉树的遍历

树的遍历

二叉查找树BST

平衡二叉树AVL

并查集

堆

哈夫曼树

图

图的定义

图的存储

图的遍历

最短路径

最小生成树

拓扑排序

关键路径

动态规划

动态规划的递归与递推

最大连续子序列和

最长不下降子序列LIS

最长公共子序列

最长回文子串

DAG最长路

背包问题

总结

字符串

字符串hash进阶

KMP算法

专题扩展

分块思想

树状数组BIT

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~