Codeforces Round 962 (Div. 3) 题解
A. Legs https://codeforces.com/contest/1996/problem/A
翻译:
农夫约翰的农场又迎来了美好的一天。
农夫约翰来到农场后,数了数 n条腿。众所周知,农场里只住着鸡和牛,一只鸡有 2 条腿,而一头牛有 4 条腿。
假设约翰农场主数清了所有动物的腿,那么他的农场里最少有多少动物?
思路
求最少有几只动物,n先除4再除2就行。
void solve() {
cin >> n;
int k = n / 4;
n -= k * 4;
int p = n / 2;
cout << p + k << "\n";
}
B. Scale https://codeforces.com/contest/1996/problem/B
翻译
就是说,给你一个n*n的01网格,网格中每个01块都是相同的长宽,让你缩小k倍,例如:
8 2
00001111
00001111
00001111 --> 0011
00001111 --> 0011
11110000 --> 1100
11110000 --> 1100
11110000
思路
我们只需要从(1,1)位置开始i和j加k输出就可以,自己模拟几下就找到规律
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 https://codeforces.com/contest/1996/problem/C
翻译
就是说,给你两个长度为n的字符串,询问q次。
每次给出l,r的区间让你判断区间字符串是否匹配,不匹配就得去修改a的字符,需要修改几次才能让两个区间相同
思路
首先需要判断l和r大小,确定循环;
统计一下区间字符串中字符不同的数量,输出即可。
一开始用map来做,后来超时了,就做了优化。
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";
}
}
超时版
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";
}
}