AtCoder Beginner Contest 430

atcoder, 题解

A Candy Cookie Law

题目描述

给四个数字, , , , 若 的同时 ,输出 .

参考代码

#include<bits/stdc++.h>


#define int long long
#define pii std::pair<int,int>


void solve() {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    if ((c >= a && d >= b) || c < a) {
        std::cout << "No" << std::endl;
    } else {
        std::cout << "Yes" << std::endl;
    }
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while (T --) solve();
    return 0;
}

B Count Subgrid

B Count Subgrid

题目描述

的矩阵中包含多少种不同的 的子矩阵.

解题思路

遍历矩阵，将每个子矩阵都转化为字符串存入 ， 大小即为答案.

参考代码

#include<bits/stdc++.h>


#define int long long
#define pii std::pair<int,int>


void solve() {
    int n, m;
    std::cin >> n >> m;
    std::map<std::string, int> mp;;
    std::vector<std::string> a(n);
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n - m + 1; i ++) {
        for (int j = 0; j < n - m + 1; j ++) {
            std::string s = "";
            for (int l = 0; l < m; l ++) {
                for (int r = 0; r < m; r ++) {
                    s += a[i + l][j + r];
                }
            }
            mp[s] ++;
        }
    }
    std::cout << mp.size() << std::endl;
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while (T --) solve();
    return 0;
}

C Truck Driver

C Truck Driver

题目描述

一个字符串 中存在多少个数对，使得这个子串(),满足字符 个数 , 字符 个数

解题思路

数据范围不允许使用暴力，那么只能使用二分，循环左边，二分右区间，二分条件就是,但是我们不能直接一个二分查找，可以想到在一个区间内可能存在多个满足条件的值.

我们只有分别二分满足的位置 ，然后去取得两个的交集，其中， 是有可能小于 的.

参考代码

#include<bits/stdc++.h>


#define int long long
#define pii std::pair<int,int>


void solve() {
    int n, a, b;
    std::cin >> n >> a >> b;
    std::string s;
    std::cin >> s;
    std::vector<int> ct1(n + 1, 0), ct2(n + 1, 0);
    for (int i = 0; i < n; i ++) {
        ct1[i + 1] = ct1[i] + (s[i] == 'a');
        ct2[i + 1] = ct2[i] + (s[i] == 'b');
    }
    int ans = 0;
    for (int i = 0; i < n; i ++) {
        int l = i, r = n + 1, ll = i, rr = n + 1;
        while (std::abs(l - r) > 1) {
            int mid = (l + r) >> 1;
            if (ct1[mid] - ct1[i] >= a) r = mid;
            else l = mid;
        }
        while (std::abs(ll - rr) > 1) {
            int mid = (ll + rr) >> 1;
            if (ct2[mid] - ct2[i] < b) ll = mid;
            else rr = mid;
        }
        ans += std::max(rr - r, 0ll);
    }


    std::cout << ans << std::endl;
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while (T --) solve();
    return 0;
}
Built with MDFriday ❤️