Codeforces Round 1028 (Div. 2)

2025-05-31

A

哈哈哈，错了一发，因为我以为 ab 都是第一个人的。。。读题确实要仔细点

// Date: 2025-05-31
// Time: 22:36:31
void ChatGptDeepSeek()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(min(a, c) >= min(b, d)) cout << "Gellyfish\n";
    else cout << "Flower\n";
}

B

因为是排列，所以加的两个位置，必然至少有一个数字是前缀的最大值。其实不需要快速幂，拿个数组记一下就行。

// Date: 2025-05-31
// Time: 22:43:12
constexpr int mod = 998244353;

ll ksm(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vi p(n), q(n), pos1(n), pos2(n), r(n), mx(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
        pos1[p[i]] = i;
    }
    for(int i = 0; i < n; i++){
        cin >> q[i];
        pos2[q[i]] = i;
    }
    mx[0] = max(p[0], q[0]);
    for(int i = 1; i < n; i++){
        mx[i] = max(mx[i - 1], max(p[i], q[i]));
    }
    for(int i = 0; i < n; i++){
        int x = 0;
        if(pos1[mx[i]] <= i)
            cmax(x, q[i - pos1[mx[i]]]);
        if(pos2[mx[i]] <= i)
            cmax(x, p[i - pos2[mx[i]]]);
        r[i] = (ksm(2, mx[i]) + ksm(2, x)) % mod;
        cout << r[i] << " \n"[i + 1 == n];
    }
}

C

拿个简单的dp或者bfs就行，其实就是要算最少多少个数字的gcd可以等于 \(g\)。然后其余的数字只需要跟这个数字一起操作一次就会变成 \(g\)。

后面重交发现 std::gcd 比 __gcd 快好多。然后取 gcd 还是挺费时间的。

// Date: 2025-05-31
// Time: 22:53:29
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vi dp(5000 + 1, INF), a(n + 1);
    int g = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dp[a[i]] = 0;
        g = gcd(g, a[i]);
    }
    if(*min_element(ALL(a)) == g){
        cout << n - count(ALL(a), g) << '\n';
        return;
    }
    for(int i = 1; i <= n; i++){
        // vi ndp(dp);
        for(int j = 1; j <= 5000; j++){
            if(dp[j] != INF)
                cmin(dp[gcd(j, a[i])], dp[j] + 1);
        }
        // dp = ndp;
    }
    cout << dp[g] + n - 1 << '\n';
}

D

逆着考虑会好很多。就是我们先看后进行的操作。

先弄一个数组 \(l\) 表示对 \(c_i\) 的限制，刚开始 \(l = b\)。每次修改操作，意味着 \(l_x \ge l_z\), \(l_y \ge l_z\)，然后 \(l_z = 0\)。我们就跟着改就行，最终的答案就是数组 \(l\)。好像完全没有问题，代码很简单，但是自己想感觉根本不知道从哪开始。

// Date: 2025-06-06
// Time: 08:05:35
void ChatGptDeepSeek()
{
    int n, q;
    cin >> n >> q;
    vi b(n + 1), l(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        l[i] = b[i];
    }
    vc<array<int, 3>> op(q);
    for(int i = q - 1; i >= 0; i--){
        cin >> op[i][0] >> op[i][1] >> op[i][2];
    }
    for(auto [x, y, z] : op){
        cmax(l[x], l[z]);
        cmax(l[y], l[z]);
        if(z != x && z != y)
            l[z] = 0;
    }
    vi c(l);
    for(int i = q - 1; i >= 0; i--){
        auto [x, y, z] = op[i];
        c[z] = min(c[x], c[y]);
    }
    if(b != c){
        cout << "-1\n";
        return;
    }
    for(int i = 1; i <= n; i++){
        cout << (l[i] ? l[i] : 1) << " \n" [ i == n];
    }
}