Codeforces Round 962 (Div. 3) 题解 A-F

A. Legs

Problem - A - Codeforces

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

  Problem - C - Codeforces
 

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

Problem - D - Codeforces

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

Problem - E - Codeforces

5.1翻译

给你一个长度为