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#
题目描述#
的矩阵中包含多少种不同的 的子矩阵.
解题思路#
遍历矩阵，将每个子矩阵都转化为字符串存入 ， 大小即为答案.
参考代码#
#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#
题目描述#
一个字符串 中存在多少个数对，使得这个子串(),满足字符 个数 , 字符 个数
解题思路#
数据范围不允许使用暴力，那么只能使用二分，循环左边，二分右区间，二分条件就是,但是我们不能直接一个二分查找，可以想到在一个区间内可能存在多个满足条件的值.
我们只有分别二分满足的位置 ，然后去取得两个的交集，其中， 是有可能小于 的.
参考代码#
#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;
}