C LCS

题意

构造三个长度为 的字符串 ，使得

可以发现将 具有相同部分的长度为 ，将这一段字符设为相同，之后对 ​ 两两之间相同的部分加上分别在后面加入不同的相同字符即可，最后对每个长度小于 的字符串在补全即可。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;
signed main() {
    int a, b, c, n;
    cin >> a >> b >> c >> n;
    string s1, s2, s3;
    int minx = (min(a, min(b, c)));
    a -= minx, b -= minx, c -= minx;
    // 三个相同的部分
    rep(i, 1, minx) s1 += 'o', s2 += 'o', s3 += 'o';
    // 两两之间相同的部分
    while (a--)
        s1 += 'x', s2 += 'x';
    while (b--)
        s2 += 'y', s3 += 'y';
    while (c--)
        s3 += 'z', s1 += 'z';
    if (s1.size() > n || s2.size() > n || s3.size() > n)
        return cout << "NO\n", 0;
    // 补全字符串
    while (s1.size() < n)
        s1 += 'a';
    while (s2.size() < n)
        s2 += 'b';
    while (s3.size() < n)
        s3 += 'c';
    cout << s1 << '\n' << s2 << '\n' << s3 << endl;
    return 0;
}

F Just a joke

题意

Alice and Bob 在玩游戏

现在有一张 ​​ 个点 ​​ 条边无向图，两个操作：选择图中的一条边将他删除 或 选择图中的一个无环连通块将它删除。

Alice 先手。当到某个玩家的回合时，不能对图进行操作时，就输了。

假设，Alice and Bob 不采用最优的解法，那么游戏最多操作数为 （先删所有的边，再删所有的点）

在一种操作下，每***作后，操作数

那么对于采用第二个操作，假设删去的连通块中有 个点 那么对应的有 条边，即操作数

可以发现，无论选择哪种操作，剩余的操作数的奇偶性不变

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;
signed main() {
    int n, m, x, y;
    cin >> n >> m;
    rep(i, 1, m) cin >> x >> y;
    if ((n + m) & 1)
        puts("Alice");
    else
        puts("Bob");
    return 0;
}

J Average

题意

有一个 的矩阵 ， 求矩阵中长度大于等于 ，宽度大于等于 的子矩阵最大平均值

假设我们选取一个这样的矩阵

	......​​	​
......	......	......
​​​	......​​​	​​​​

​​

化简一下就可以发现转换为了求一个数组中区间长度大于某值时的最大平均值（套板子即可）。

#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;
    double 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;
}