蓝桥杯-刷题

刷题

// 全排列
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], c[N];
int n;
bool st[N];

void dfs(int k) {
    if (k > n) {
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            a[k] = i;
            st[i] = true;
            dfs(k + 1);
            st[i] = false;
        }
    }
}

int main() {
    scanf_s("%d", &n);
    memset(st, false, sizeof(st));
    dfs(1);
    return 0;
}

// 组合
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N], c[N];
int n;
bool st[N];

void dfs(int k) {
    if (k > n) {
        for (int i = 1; i <= n; i++)
            if (st[i])
                cout << i << " ";
        cout << endl;
        return;
    }
    st[k] = true;
    dfs(k + 1);
    st[k] = false;
    dfs(k + 1);
}

int main() {
    scanf_s("%d", &n);
    memset(st, false, sizeof(st));
    dfs(1);
    return 0;
}

// 组合数 随机选出来 m 个
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 25;
int n, m;
int path[N];
bool st[N];
void dfs(int u, int num) {
    if (u > m) {
        for (int i = 1; i <= m; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!st[i] && i > num) { // 用于判断当前 i 是否大于前面生成的，保证最后序列是递增的
            st[i] = true;
            path[u] = i;
            dfs(u + 1, i);
            st[i] = false;
        }
    }
}
int main() {
    cin >> n >> m;
    dfs(1, 0);

    return 0;
}

// dfs

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int N = 20;
char g[N][N];
int n, m;
int dx[] = {0, 1, -1, 0}, dy[] = {1, 0, 0, -1};
bool st[N][N];

// * 表示墙 T 表示出口
bool dfs(int x, int y) {
    if (g[x][y] == 'T') return true;
    if (g[x][y] == '*') return false;
    st[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a <= 0 || a > n || b <= 0 || b > m || st[a][b]) continue;
        if (dfs(a, b)) return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    int a, b;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'S') {
                a = i, b = j;
            }
        }
    if (dfs(a, b))
        cout << " yes " << endl;
    else
        cout << " no " << endl;

    return 0;
}

// 迷宫问题二

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;
int n, m;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];
int Min = 9999;

void dfs(int x, int y, int u) {
    if (g[x][y] == 'T') {
        Min = min(Min, u);
        return;  // 加上 return，当找到终点后立即结束当前搜索分支
    }
    if (g[x][y] == '*') return;

    st[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a > n || a <= 0 || b <= 0 || b > m || st[a][b] || g[a][b] == '*') continue;
        dfs(a, b, u + 1);
    }
    st[x][y] = false;  // 在递归调用结束后取消标记
}

int main() {
    cin >> n >> m;
    int x, y;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'S') {
                x = i;
                y = j;
            }
        }
    }
    dfs(x, y, 0);
    if (Min != 9999) {
        cout << " yes " << endl << " 最大步数是：" << Min << endl;
    } else {
        cout << " no " << endl;
    }

    return 0;
}

// 迷宫问题三

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

using namespace std;
const int N = 20;
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char g[N][N];
bool st[N][N];
int minn = 99999;
void dfs(int x, int y, int stmp) {
    if (stmp > minn) return;
    if (x == 0 || y == 0 || x == n + 1 || y == m + 1) {
        minn = min(minn, stmp);
        return;
    }
    st[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b =

 y + dy[i];
        if (g[a][b] == '#') continue;
        if (st[a][b]) continue;
        dfs(a, b, stmp + 1);
        st[a][b] = false;
    }
}
int main() {
    cin >> n >> m;
    int x, y;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == '@') {
                x = i;
                y = j;
            }
        }
    }
    dfs(x, y, 0);
    if (minn == 99999) {
        cout << -1 << endl;
    } else {
        cout << minn - 1 << endl;
    }
    return 0;
}

// FeiBo
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a = 1, b = 1;
    for (int i = 2; i <= n / 2; i++) {
        a += b;
        cout << a << " ";
        b += a;
        cout << b << " ";
    }
    cout << endl;
    if (n % 2)
        cout << a << endl;
    else
        cout << b << endl;

    return 0;
}

// 二进制枚举

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

using namespace std;
const int N = 510;
char g[6][6], backup[6][6];
int dx[6] = {-1, 0, 1, 0, 0}, dy[6] = {0, 1, 0, -1, 0};  // 5 方向变换
int n;

void turn(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b] ^= 1;
    }
}

int main() {
    cin >> n;
    while (n--) {
        for (int i = 0; i < 5; i++) cin >> g[i];

        int ans = 10;
        for (int op = 0; op < 32; op++) {
            memcpy(backup, g, sizeof g);
            int stmp = 0;
            for (int i = 0; i < 5; i++) {
                if (op >> i & 1) {
                    turn(0, i);
                    stmp++;
                }
            }
            for (int i = 1; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (g[i - 1][j] == '0') {
                        turn(i, j);
                        stmp++;
                    }
                }
            }
            bool suf = true;
            for (int j = 0; j < 5; j++) {
                if (g[4][j] == '0') {
                    suf = false;
                    break;
                }
            }

            if (suf) {
                ans = min(ans, stmp);
            }

            memcpy(g, backup, sizeof backup);
        }
        if (ans > 6) {
            cout << -1 << endl;
        } else {
            cout << ans << endl;
        }
    }

    return 0;
}

// 右二分

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N];
int n, tar;

int main() {
    cin >> n >> tar;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;  // 取右中位数
        if (a[mid] <= tar)
            l = mid;
        else
            r = mid - 1;
    }
    if (a[l] == tar)
        cout << l << endl;
    else
        cout << " Not Found " << endl;

    return 0;
}

// 左二分

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N];
int n, tar;

int main() {
    cin >> n >> tar;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] == tar)
            r = mid;
        else
            l = mid + 1;
    }
    if (a[l] == tar)
        cout << l << endl;
    else
        cout << " Not Found " << endl;

    return 0;
}

// 快排

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N];
int n;

void qs(int arr[], int left, int right) {
    if (left >= right) return;
    int l = left - 1, r = right + 1, mid = a[left + right >> 1];

    while (l < r) {
        do l++; while (a[l] < mid);
        do r--; while (a[r] > mid);
        if (l < r) swap(a[l], a[r]);
    }
    qs(arr, left, r);
    qs(arr, r + 1, right);
}

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

    qs(a, 1, n);

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

    return 0;
}

// 贪心 1349. 修理牛棚

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

using namespace std;
const int N = 210;
int a[N], b[N];
int m, s, c;

int main() {
    cin >> m >> s >> c;
    for (int i = 1; i <= c; i++) cin >> a[i];
    sort(a + 1, a + c + 1);
    for (int i = 1; i < c; i++) b[i] = a[i + 1] - a[i] - 1;

    sort(b + 1, b + c);

    int sum = 0;
    for (int i = c - 1; i > c - m;

 i--) sum += b[i];
    cout << (a[c] - a[1] + 1 - sum);
    return 0;
}

// 差分 适用于区间修改，单点查询  4262. 空调

#include <iostream>
using namespace std;

const int N = 1e5 + 3;
int a[N], b[N];

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

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

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

    for (int i = 1; i <= n; i++) b[i] += a[i], b[i + 1] -= a[i];

    int s = 0, t = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] > 0) s += b[i];
        else if (b[i] < 0) t -= b[i];
    }

    cout << max(s, t) << '\n';

    return 0;
}

// 前缀和 562. 壁画
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5e6 + 10;
int a[N], b[N];

int main() {
    int T;
    cin >> T;
    for (int m = 1; m <= T; m++) {
        int n, ans = 0;
        cin >> n;
        int len = (n + 1) / 2;
        string s;
        cin >> s;
        a[0] = 0;
        for (int i = 1; i <= n; i++)
            a[i] = ((s[i - 1] - '0') + a[i - 1]);

        for (int i = 1; i <= n; i++) {
            if (len < i)
                ans = max(ans, a[i] - a[i - len]);
            else
                ans = max(ans, a[i]);
        }
        cout << " Case #" << m << ": " << ans << endl;
    }
    return 0;
}

// 全排列

#include <iostream>

using namespace std;

const int N = 10;

int target;      // 题目给出的目标数
int num[N];      // 保存全排列的结果
bool used[N];    // 生成全排列过程中标记是否使用过

void dfs(int u) {
    if (u == target) {
        for (int i = 0; i < target; i++) {
            cout << num[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= target; i++) {
        if (!used[i]) {
            used[i] = true;    // 标记使用
            num[u] = i;
            dfs(u + 1);
            used[i] = false;    // 还原现场
        }
    }
}

int main() {
    scanf("%d", &target);
    dfs(0);
    return 0;
}