2021牛客暑期多校训练营4

C

题意：构造三个串 $s_1,s_2,s_3$ 使得 $LCS(s_1,s_2) = a ,LCS(s_2,s_3) = b ,LCS(s_1,s_3) = c$

思维题。python代码比汉语更容易懂。

a,b,c,n=map(int,input().split())
mn = min([a,b,c])
s1,s2,s3='','',''
for _ in range(mn):s1+='o';s2+='o';s3+='o'
a-=mn;b-=mn;c-=mn
for _ in range(a):s1+='a';s2+='a'
for _ in range(b):s3+='b';s2+='b'
for _ in range(c):s3+='c';s1+='c'
while len(s1)<n: s1+='x'
while len(s2)<n: s2+='y'
while len(s3)<n: s3+='z'
if len(s1)>n or len(s2)>n or len(s3)>n:print('NO')
else :print(s1,s2,s3,sep='\n')

更python的写法

a, b, c, n = map(int, input().split())
mn = min(a, b, c)
s1 = 'o' * mn; s2 = 'o' * mn; s3 = 'o' * mn
a -= mn; b -= mn; c -= mn
s1 += 'a' * a; s2 += 'a' * a
s2 += 'b' * b; s3 += 'b' * b
s1 += 'c' * c; s3 += 'c' * c
if len(s1) > n or len(s2) > n or len(s3) > n: print('NO')
else: print(s1 + 'x' * (n - len(s1)), s2 + 'y' * (n - len(s2)), s3 + 'z' * (n - len(s3)), sep='\n')

F

我的做法是：考虑连通分量数量 + 环数量的奇偶性

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int ht[N];
int fa[N];
void init_set(int n) {
    for (int i = 1; i <= n; ++i) fa[i] = i;
}
int Find(int x) {
    if (x != fa[x]) fa[x] = Find(fa[x]);  //路径压缩
    return fa[x];
}
int res = 0;
void merge(int x, int y) {
    x = Find(x); y = Find(y);
    if (x == y) ++res;
    else fa[y] = x;
}
int main() {
    int n, m, u, v;
    cin >> n >> m;
    init_set(n);
    rep(i, 1, m) {
        cin >> u >> v;
        merge(u, v);
    }
    rep(i, 1, n) if (Find(i) == i)++ res;
    puts(res & 1 ? "Alice" : "Bob");
    return 0;
}

I

可以对序列中的一些数+1，求所能获得的最小逆序对

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const int mod = 1e9 + 7;
#define lowbit(x) ((x) & (-x))
ll tree[N];
inline void add(int i, ll x) {
    for (int pos = i; pos < N; pos += lowbit(pos)) tree[pos] += x;
}
inline ll query(int n) {
    ll ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}
inline ll query(int l, int r) { return query(r) - query(l - 1); }
ll a[N], n;
bool vis[N];
signed main() {
    sc(n);
    rep(i, 1, n) sc(a[i]);
    ll ans = 0;
    add(a[1], 1);
    rep(i, 2, n) {
        ans += query(a[i] + 1, n);
        add(a[i], 1);
    }
    for (int i = n; i; --i) {
        if (vis[a[i] - 1]) --ans; // 这说明a[i], a[i]-1 这一逆序对存在 那么可以通过对后方的数+1来消除这个逆序对
        else vis[a[i]] = 1;
    }
    pr(ans);
    return 0;
}

J

原题。浮点二分。

约分后可转化为a的最大均值 + b的最大均值（长度大于等于k）即为所求

$n\log n$ 的做法就是二分答案然后每次用前缀和做一个滑窗来处理。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, x, y;
double maxAverage(vector<int> &nums, int k) {
    double L = INT_MAX, R = INT_MIN;
    for (int x : nums) {
        if (x <= L) L = x;
        if (x >= R) R = x;
    }
    int len = nums.size();
    double sum[len + 1];
    memset(sum, 0, sizeof(sum));
    while (R - L > 1e-8) {
        double mid = (L + R) / 2;
        double min_pre = 0;
        bool flag = false;
        for (int i = 1; i <= len; i++) {
            sum[i] = sum[i - 1] + nums[i - 1] - mid;
            if (i >= k && sum[i] - min_pre >= 0) {
                flag = true;
                break;  //只要有一组满足平均值大于mid就可以跳出内循环
            }
            if (i >= k) min_pre = min(min_pre, sum[i - k + 1]);
        }
        flag ? L = mid : R = mid;
    }
    return L;
}
signed main() {
    scanf("%d%d%d%d", &n, &m, &x, &y);
    vector<int> a(n), b(m);
    for (int &x : a) scanf("%d", &x);
    for (int &x : b) scanf("%d", &x);
    printf("%.10f\n", maxAverage(a, x) + maxAverage(b, y));
    return 0;
}