Codeforces Round 962 (Div. 3) 题解 A-F
A. Legs
1.1翻译
农夫约翰的农场又迎来了美好的一天。
农夫约翰来到农场后，数了数 n条腿。众所周知，农场里只住着鸡和牛，一只鸡有 2 条腿，而一头牛有 4 条腿。
假设约翰农场主数清了所有动物的腿，那么他的农场里最少有多少动物？
1.2思路
求最少有几只动物，n先除4再除2就行。
1.3代码
void solve() {
cin >> n;
int k = n / 4;
n -= k * 4;
int p = n / 2;
cout << p + k << "\n";
}B. Scale
Problem - B - Codeforces
2.1翻译
就是说，给你一个n*n的01网格，网格中每个01块都是相同的长宽，让你缩小k倍，例如：
8 2
00001111
00001111
00001111 --> 0011
00001111 --> 0011
11110000 --> 1100
11110000 --> 1100
11110000
2.2思路
我们只需要从（1，1）位置开始i和j加k输出就可以，自己模拟几下就找到规律
2.3代码
char mpp[N][N];
void solve() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> mpp[i][j];
}
}
for (int i = 1; i <= n; i += k) {
for (int j = 1; j <= n; j += k) {
cout << mpp[i][j];
}
cout << "\n";
}
}C. Sort
3.1翻译
就是说，给你两个长度为n的字符串，询问q次。
每次给出l，r的区间让你判断区间字符串是否匹配，不匹配就得去修改a的字符，需要修改几次才能让两个区间相同
3.2思路
首先需要判断l和r大小，确定循环；
统计一下区间字符串中字符不同的数量，输出即可。
一开始用map来做，后来超时了，就做了优化。
3.3代码
const int N = 2e5 + 10;
int a_count[26][N], b_count[26][N];
void Count(const string& a, const string& b, int n) {
for (int i = 0; i < 26; ++i) {
a_count[i][0] = b_count[i][0] = 0;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
a_count[j][i + 1] = a_count[j][i] + (a[i] == 'a' + j);
b_count[j][i + 1] = b_count[j][i] + (b[i] == 'a' + j);
}
}
}
int get(int l, int r, int n) {
int cnt = 0;
for (int i = 0; i < 26; ++i) {
int ap = a_count[i][r] - a_count[i][l - 1];
int bp = b_count[i][r] - b_count[i][l - 1];
cnt += max(0, bp - ap);
}
return cnt;
}
void solve() {
int n, k;
cin >> n >> k;
string a, b;
cin >> a >> b;
Count(a, b, n);
while (k--) {
int l, r;
cin >> l >> r;
if (l > r) cout << get(1, r, n) + get(l, n, n) << "\n";
else cout << get(l, r, n) << "\n";
}
}
3.4超时版
const int N = 2e5 + 10;
map<char, int>p;
void solve() {
int n, k;
cin >> n >> k;
string a, b;
cin >> a >> b;
while (k--) {
int l, r;
cin >> l >> r;
p.clear();
if (l <= r) {
for (int i = l - 1; i <= r - 1; i++)
p[b[i]]++, p[a[i]]--;
}
else {
for (int i = l - 1; i <= n - 1; i++)
p[b[i]]++, p[a[i]]--;
for (int i = 0; i <= l - 1; i++)
p[b[i]]++, p[a[i]]--;
}
int cnt = 0;
for (char i = 'a'; i <= 'z'; i++)
if (p[i] > 0) cnt += p[i];
cout << cnt << "\n";
}
}D. Fun
4.1翻译
给定两个整数 n 和 x ，求 ab+ac+bc≤n 和 a+b+c≤x 的个正整数的三元组( a,b,c)的个数。
注意顺序问题(例如 ( 1,1,2 ) 和 ( 1,2,1 ) 被视为不同)， a ， b ， c 必须严格大于 0 。
4.2思路
由第一个式子可知，a*b<=n，所以b有大约有 nlogn个选择，可以循环ab求解
由两个式子可推导出c ≤（n−ab）/（a+b）和 c ≤ x−a−b,我们只需要选择范围最小的那一个即可。
4.3代码
#define ll long long
void solve() {
int n, k;
cin >> n >> k;
ll c = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; i * j <= n; j++) {
ll t1 = i * j, t2 = i + j;
if ((n - t1) / t2 > 0 && k - t2 > 0) c += min((n - t1) / t2, k - t2);
}
cout << c << "\n";
}E. Decode
5.1翻译
给你一个长度为 𝑛 的二进制字符串 𝑠 。对于每一对整数 (𝑙,𝑟) . (1≤𝑙≤𝑟≤𝑛) 中，数出(𝑥,𝑦) (𝑙≤𝑥≤𝑦≤𝑟) 这样的整数对的个数。 (𝑙≤𝑥≤𝑦≤𝑟) 中的 00 等于子串 𝑠𝑥𝑠𝑥+1...𝑠𝑦 中的 1 。
输出所有可能的 (l,r)(𝑙,𝑟) modulo 109+7109+7 的计数之和。
5.2代码
#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
typedef unsigned long long ull;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mm(a, b) memset(a, b, sizeof(a))
#define mp make_pair
#define ll long long
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e6 + 10;
ll n, sum, p[N], f[N], k;
string s;
void solve() {
cin >> s;
n = s.length();
for (ll i = 0; i <= 2 * n; i++) f[i] = 0;
for (ll i = 1; i <= n; i++) {
ll pp = p[i - 1];
if (s[i - 1] == '1') p[i] = pp + 1;
else p[i] = pp - 1;
}
sum = 0;
for (ll i = 0; i <= n; i++) {
ll id = p[i] + n;
sum = (sum + f[id] * (n - i + 1)) % mod;
f[id] = (f[id] + (i + 1)) % mod;
}
cout << sum << '\n';
}
int main() {
ios;
ll t;
cin >> t;
while (t--) solve();
return 0;
}
F. Bomb（参考jiangly的思路）
6.1代码
#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include<set>
using namespace std;
typedef unsigned long long ull;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mm(a, b) memset(a, b, sizeof(a))
#define mp make_pair
#define ll long long
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e6 + 10;
typedef pair<ll, ll> Pair;
Pair get(int v, vector<int>& a, vector<int>& b, int n) {
ll sum = 0;
ll cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] >= v) {
ll t = (a[i] - v) / b[i] + 1;
cnt += t;
sum += a[i] * t - t * (t - 1) / 2 * b[i];
}
}
return Pair(cnt, sum);
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
int l = 0, r = inf;
while (l < r) {
int x = (l + r) / 2;
if (get(x, a, b, n).first <= k) r = x;
else l = x + 1;
}
Pair res = get(l, a, b, n);
if (l > 0) res.second += (k - res.first) * (l - 1);
cout << res.second << "\n";
}
int main() {
ios;
ll t;
cin >> t;
while (t--) solve();
return 0;
}