第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组

A. 日期统计

思路：

• 可以写8层for循环，也可以写dfs。

时间复杂度：\(O(2^{12})\)

int m[] {
    5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
    5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
    2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
    8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
    1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
};
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    auto dfs = [&](auto self, int m[], int date[], int p1, int p2) { //n是传进来的100个数，date是需要找的日期，pos1找到num第几位，pos2找date第几位
        if (p2 == 8) { //我们已经遍历完，找到日期了
            return true;
        }
        if (p1 >= 100) { //整个数组找完了，没有找到
            return false;
        }
        if (m[p1] == date[p2]) { //当前位置的数是我们想要的数
            return self(self, m, date, p1 + 1, p2 + 1);  //继续往下找
        } else {
            return self(self, m, date, p1 + 1, p2); //如果不是想要的数，那么就继续在数组找
        }    
    };

    int date[] = {2, 0, 2, 3, 0, 0, 0, 0}, ans = 0;
    int mo[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    for (int i = 1; i <= 12; i++) {
        if (i < 10) {
            date[4] = 0;
            date[5] = i;
        } else {
            date[4] = 1;
            date[5] = i % 10;
        }
        for (int j = 1; j <= mo[i]; j++) {
            if (j < 10) {
                date[6] = 0;
                date[7] = j;
            } else {
                date[6] = j / 10;
                date[7] = j % 10;
            }
            ans += dfs(dfs, m, date, 0, 0);
        }
    }
    std::cout << ans << "\n";

    return 0;
}

C. 冶炼金属

思路：

• 求最大值：直接二分第一个大于 \(\frac{A}{B}\) 的位置，然后不断地取 \(max\)
• 求最小值：每次直接整除，然后取min即可

时间复杂度：\(O(Nmax(a_i, b_i))\)

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    int X = -1, Y = 2E9;
    for (int i = 0; i < N; i++) {
        int A, B;
        std::cin >> A >> B;

        Y = std::min(Y, A / B);
        int l = 0, r = A;
        while (l < r) {
            int mid = l + r >> 1;
            if (A / mid <= B) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        X = std::max(X, l);
    }

    std::cout << X << " " << Y << "\n";
    
    return 0;
}

D. 飞机降落

思路：

• 根据数据范围可以推测，这题是暴搜，难点在于搜的方式
• 我们可以从第1个位置开始搜索，然后当搜到最后一个位置就结束，每次走到一个新的位置，然后记录，当前的时间是否与前面盘旋的飞机的最小时间相冲突，如果不冲突，就继续搜索，如果搜索了所有的方案，都没找到不合法的情况，就输出YES，否则NO

时间复杂度：\(O(n^n)\)

struct node {
    int t, d, l;
};

void solve() {
    int N;
    std::cin >> N;
    
    std::vector<node> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i].t >> a[i].d >> a[i].l;
    }
    
    std::vector<int> vis(N + 1);
    std::function<bool(int, int)> dfs = [&](int u, int la) { // u 当前位置 la 上一次最晚下落的时间
        if (u == N) return true; // 如果平安的搜到最后面，就说明没有问题
        for (int i = 0; i < N; i++) { 
            int t = a[i].t, d = a[i].d, l = a[i].l;
            if (!vis[i] && t + d >= la) { // 若果当前位置没有搜过并且最晚下落时间大于上一次的下落时间
                vis[i] = true; // 标记走了
                if (dfs(u + 1, std::max(la, t) + l)) return true;
                vis[i] = false; // 回溯
            }
        }
        return false; // 找不到就说明有问题
    };
    std::cout << (dfs(0, 0) ? "YES\n" : "NO\n");
}

E. 接龙数列

思路：

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        std::string s;
        std::cin >> s;
        a[i] = s.front() - '0';
        b[i] = s.back() - '0';
    } 
    
    std::vector<int> dp(n + 1), g(10);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        dp[i] = std::max(dp[i], g[a[i]] + 1);
        g[b[i]] = std::max(g[b[i]], dp[i]);
    }
    
    int max = 0;
    for (int i = 1; i <= n; i++) {
        max = std::max(max, dp[i]);
    }
    std::cout << n - max << "\n";
    
    return 0;
}

F. 岛屿个数

思路：

• 首先，这个可能出现一个一圈，中间一个小岛，然后搜错。
• 所以我们要把最外围的一层扩展为海水，然后把其他可以渗透的位置都染色，最开始预处理的时候，设八个方向的向量，然后开始染色，等染色完，我们就见到一个群岛就记录一个，最后输出即可。
• 难点在于怎么处理一个群岛

时间复杂度：\(O(NM)\)

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

void solve() {
    int M, N;
    std::cin >> M >> N;
    
    std::vector<std::vector<char>> g(M + 2, std::vector<char>(M + 2, '0'));
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            std::cin >> g[i][j];
        }
    }
    
    std::queue<std::pair<int, int>> q;
    q.push({0, 0});
    g[0][0] = '$';
    
    while (!q.empty()) {
        auto e = q.front();
        q.pop();
        
        int x = e.first, y = e.second;
        for (int i = 0; i < 8; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a <= M + 1 && b >= 0 && b <= N + 1) {
                if (g[a][b] == '0') {
                    g[a][b] = '$';
                    q.push({a, b});
                }
            }
        }
    } 
    
    std::function<void(int, int)> bfs = [&](int x, int y) {
        std::queue<std::pair<int, int>> q;
        g[x][y] = '$';
        q.push({x, y});
        
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            
            for (int i = 0; i < 4; i++) {
                int a = t.first + dx[i], b = t.second + dy[i];
                if (a >= 1 && a <= M && b >= 1 && b <= N) {
                    if (g[a][b] == '0' || g[a][b] == '1') {
                        g[a][b] = '$';
                        q.push({a, b});
                    }
                }
            }
        }
    };
    
    int ans = 0;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if (g[i][j] == '1') {
                bfs(i, j);
                ans++;
            }
        }
    }
    std::cout << ans << "\n";
}

G. 子串简写

思路：

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int K;
    std::cin >> K;
    
    char a, b;
    std::string S;
    std::cin >> S >> a >> b;
    
    S = ' ' + S;
    int n = S.size();
    std::vector<int> dp(n + 2);
    for (int i = n; i >= 1; i--) {
        dp[i] = dp[i + 1];
        if (S[i] == b) {
            dp[i] = dp[i + 1] + 1;
        }
    }
    
    i64 ans = 0;
    for (int i = 1; i + K <= n; i++) {
        if (S[i] == a) {
            ans += dp[i + K - 1]; 
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}