Practice.

A. Make A Equal to B

题意

给定两个长度为 \(n\) 的二进制序列 \(a, b\)，定义操作如下：

选择任意 \(i\)，将 \(a_i\) 改为 \(1 - a_i\)；
任意排序 \(a\)

输出操作数的最小值。

思路

很显然，我们直接统计两个序列中 \(0, 1\) 的个数，然后在将 \(0\) 的个数变为一致需要的操作数和将 \(1\) 的个数变为一致需要的操作数中取最小值即可。此时，答案为最小操作数 \(+ 1\)。

当然，如果只需改一次，我们就不用排序了，所以我们顺便计算一下按原顺序排列的情况下有多少数不一样，最后和答案取最小值即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    cin >> n;
    int c1 = 0, c2 = 0, d1 = 0, d2 = 0;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(a[i] == 0) c1 ++;
        else c2 ++;
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if(cur != a[i]) ans ++;
        if(cur == 0) d1 ++;
        else d2 ++;
    }
    ans = min(ans, (abs(c1 - d1) + abs(c2 - d2)) / 2 + 1);
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

思路后面那个容易没考虑到捏

B. Playing with GCD

题意

给定一个长度为 \(n\) 的数组 \(a\)，输出是否能构造出一个长度为 \(n + 1\) 的数组 \(b\)，满足 \(a_i = gcd(b_i, b_{i + 1})\)。

思路

首先，只有当 \(gcd(lcm(a_{i - 1}, a_i), lcm(a_i, a_{i + 1})) = a_i\) 的时候才有解，否则我们会很轻松将 \(a_i\) 变为 \(k a_i\)，甚至为 \(1\)。

那么，我们直接计算出所有的 \(b_i\)，然后枚举即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 2);
    for(int i=1;i<=n;i++) cin >> a[i];
    b[1] = a[1], b[n + 1] = a[n];
    for(int i=2;i<=n;i++) b[i] = lcm(a[i - 1], a[i]);
    bool f = true;
    for(int i=1;i<=n;i++){
        if(gcd(b[i], b[i + 1]) != a[i]) f = false;
    }
    cout << (f ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

但其实我并不会严格证明（x

C1. Good Subarrays (Easy Version)

题意

定义如果一个序列 \(p\) 满足所有 \(p_i \geq i\)，那么这个序列是好的。

给定一个序列 \(a\)，输出它的所有连续子序列中好序列的个数。

思路

我们固定左边界来计算右边界能到达哪里，显然，当 \(a_r < r - l + 1\) 时 \(r\) 不满足题意。

因为右边界肯定不会回退（既然 \(p_i \geq i\)，那么 \(p_i > i - 1\)），那么我们可以直接循环，得到一个 \(O(n)\) 复杂度的解法。

这种暴力做法不可以用到 \(C2\) 中，而是需要改进为 \(dp\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++)cin >> a[i];
    int ans = 0;
    int r=1;
    for(int l = 1;l<=n;l++) {
        while (r <= n && a[r] >= r - l + 1) r++;
        ans += r - l;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

就很无脑