这里是2022/4/2 离十三届蓝桥杯还有7天 按题型复习模板

(一)日历、日期问题(枚举、模拟)

总结：https://www.acwing.com/blog/content/5918/

• acwing 1229 日期问题

枚举年份，先判断是否合法，然后再按要求输出
eg. date从 19600101 ~ 20591231

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

bool check_valid(int year, int month, int day)
{
    if (month <= 0 || month > 12) return false;  //月份1~12
    if (day == 0) return false;  //日不为0
    if (month != 2)  //特判2月
    {
        if (day > days[month]) return false;
    }
    else
    {
        int leap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0;  //闰年leap = 1
        if (day > 28 + leap) return false;
    }
    return true;
}

int year = date / 10000, month = date % 10000 / 100, day = date % 100;

• acwing 466.回文日期

  输入：20110101 20111231
  输出：1 （表示在 date1 和 date2 之间，有多少个日期是回文的。）

//枚举回文日期，判断日期是否合法and是否在范围内
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

bool check_valid(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (month == 0 || month > 12) return false;
    if (day == 0 || month != 2 && day > days[month]) return false;

    if (month == 2)
    {
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }
    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;

    int res = 0;
    for (int i = 1000; i < 10000; i ++ )  //枚举所有四位数
    {
        int date = i, x = i;
        for (int j = 0; j < 4; j ++ )  //扩充日期：把i翻转，接到i后面
        {
            date = date * 10 + x % 10;
            x /= 10;
        }
        if (date >= date1 && date <= date2 && check_valid(date)) res ++ ;
    }

    cout << res << endl;

    return 0;
}

• acwing 2867.回文日期
  给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

//判断日期是否合法
bool check_valid(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (month <= 0 || month > 12) return false;
    if (day == 0) return false;
    if (month != 2)
    {
        if (day > days[month]) return false;
    }
    else {
        int leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

//判断日期是否为ABABBABA格式
bool check(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;
    if (year / 100 != year % 100) return false;
    else {
        if (month % 10 == day / 10) return false;
        if ((month / 10 == day / 10) && (month % 10 == day % 10)) return true;
    }
    return false;

}

int ans1, ans2;
bool st1, st2;

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = n / 10000; i < 10000; i ++ )
    {
        int date = i, x = i;
        for (int j = 0; j < 4; j ++ ) date = date * 10 + x % 10, x /= 10;

        if (check_valid(date) && date > n)
        {
            if (!st1) st1 = true, ans1 = date;
            if (!st2 && check(date)) st2 = true, ans2 = date;
        }

        if (st1 && st2) break;
    }

    printf("%d\n%d", ans1, ans2);
    return 0;
}

• acwing 3218.日期计算

给定一个年份 y 和一个整数 d，问这一年的第 d 天是几月几日？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

//获得当前月份的天数
int get(int year, int month)
{
    int leap = year % 4 == 0 && year % 100 || year % 400 == 0;
    if (month == 2)
    {
        return 28 + leap;
    }
    else 
    {
        return days[month];
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    int year = n, month = 1, day = 0;
    while (m -- )
    {
        day ++ ;
        if (day > get(year, month)) month ++ , day = 1;
        if (month > 12) year ++ , month = 1;
    }
    cout << month << endl << day << endl;

    return 0;
}

（二）递归（DFS/BFS）

• DFS(暴搜)

eg1.842 全排列问题

按字典序输出1~n的全排列

#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)  //u为当前位置
{
    if (u == n)  //到了最后一个位置，说明已经都排好了
    {
        for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i ++ )  //1~n
    {
        if (!st[i])
        {
            path[u] = i;  //当前位置上放i
            st[i] = true;  //标记i已经被放过

            dfs(u + 1);  //回溯

            //恢复现场
            // path[u] = 0;
            st[i] = false;
        }

    }
    return;
}

int main()
{
    cin >> n;

    dfs(0);  //从头开始遍历

    return 0;
}

eg.843.n皇后问题

//第一种搜索顺序
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];  //列，主对角线，副对角线

void dfs(int u)  //u表示当前在哪一行
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; i ++ )  //在第u行看Q可以放在哪一列
    {
        if (!col[i] && !dg[i + u] && !udg[i - u + n])
        {
            g[u][i] = 'Q';
            col[i] = dg[i + u] = udg[i - u + n] = true;

            dfs(u + 1);

            col[i] = dg[i + u] = udg[i - u + n] = false;
            g[u][i] = '.';
        }
    }
    return;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}

//第二种搜索顺序：按格子枚举，放or不放，再找下一个
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s)
{
    if (y == n) y = 0, x ++ ;

    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    //不放皇后
    dfs(x, y + 1, s); 

    //放皇后 
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;

        dfs(x, y + 1, s + 1);

        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

int main()
{
    cin >> n; 
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}

• BFS（宽搜）仅当所有边的权值都相等时，最短路问题才可以用BFS。

acwing 844.走迷宫

数字表示从起点走到该点的距离

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);

    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.x][t.y] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n - 1][m - 1];

}

int main()
{
    cin >> n >> m;

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

    cout << bfs() << endl;
    return 0;
}  

DP

二分

前缀和

倒转数字

• acwing 445.数字反转

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    string str;
    cin >> str;

    reverse(str.begin(), str.end());  //翻转字符串

    if (str.back() == '-')  //如果是负数，翻转后负号在末尾
    {
        cout << '-';  //输出负号
        str.pop_back();  //把末尾的负号去掉
    }

    //去前导0
    int k = 0;
    while (k + 1 < str.size() && str[k] == '0') k ++ ;  //判k + 1是否越界是因为如果是0，也要输出0
    while (k < str.size()) cout << str[k ++ ];

    return 0;
}

进制转换

• 任意a进制转换为b进制：
• (1) a进制 -> 10进制 -> b进制 （存储数据需要用高精度）
• (2) a进制 -> b进制

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int a, b;
        string a_line, b_line;
        cin >> a >> b >> a_line;

        vector<int> num;
        for (auto c : a_line)
        {
            if (c >= '0' && c <= '9') num.push_back(c - '0');
            if (c >= 'A' && c <= 'Z') num.push_back(c - 'A' + 10);
            if (c >= 'a' && c <= 'z') num.push_back(c - 'a' + 36);
        }
        reverse(num.begin(), num.end());

        vector<int> res;
        while (num.size())
        {
            int r = 0;
            for (int i = num.size() - 1; i >= 0; i -- )
            {
                num[i] += r * a;
                r = num[i] % b;
                num[i] /= b;
            }
            res.push_back(r);
            while (num.size() && num.back() == 0) num.pop_back();
        }
        reverse(res.begin(), res.end());

        for (auto x : res)
        {
            if (x <= 9) b_line += char(x + '0');
            if (x >= 10 && x <= 35) b_line += char(x + 'A' - 10);
            if (x >= 36) b_line += char(x + 'a' - 36);
        }
        cout << a << ' ' << a_line << endl;
        cout << b << ' ' << b_line << endl;
        cout << endl;
    }
    return 0;
}

• 10转2

for (int op = 31; op >= 0; op -- ) cout << (n >> op & 1);

数学

• 质数

（1）质数的判定：试除法

字符串