Phantom Bird

外观

做韩国佬题目（KOI）

约 1289 字大约 4 分钟

OI

2025-8-5

KOI Round 1 几乎全是暴力，纯属浪费感情。

以下是 Round 2，有些题依然很水。

P12661 [KOI 2023 Round 2] 不稳定数列

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=3e5+100;
int a[maxn], f[maxn];
int la[2];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    for (int i=1; i<=n; i++){
        f[i] = f[la[1&~a[i]]] + 1;
        la[1&a[i]] = i;
    }
    
    cout << max(f[la[0]], f[la[1]]);
    
    return 0;
}

P12662 [KOI 2023 Round 2] 滑冰练习

每个点都有一个速度限制 ViV_i。
可以任意提升速度，但若要降低速度，每次只能从上一个点的速度减少 11

max⁡vi=min⁡j≥i(Vj+j−i)=min⁡j≥i(Vj+j)−i\max v_i = \min_{j \ge i}(V_j + j-i) = \min_{j \ge i}(V_j+j) - i

计算 Vj+jV_j+j 的后缀最小值即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=5e5+100;
int V[maxn], m[maxn], ans;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> V[i];
    }
    
    // 最终速度 
    n++;
    V[n] = 0;
    
    m[n+1] = 0x3f3f3f3f3f3f3f3full;
    for (int i=n; i>=1; i--){
        m[i] = min(m[i+1], V[i] + i);
        ans += m[i] - i;
    }
    
    cout << ans;
    
    return 0;
}

P12663 [KOI 2023 Round 2] 湖边的蚁穴

幻视基环树独立集。

注：方法为断一条环上的边。
由于边连接的两点至少有一个原图的最大独立集上出现
分别令两点为根并只计算根节点不选的最大独立集
然后取最大值即可。

本题：

两个选择：要么选择大房间不选小房间，要么选择小房间而不选大房间，
其他都不是最优的。
拆环 + 记录额外状态 + dp 即可。

状态设计：f[上一个大房间是否被选择][第一个大房间是否被选择]

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=25e4+100;

int c[maxn];
int f[2][2];
int f_copy[2][2];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> c[i];
    }
    
    f[1][1] = 1;
    f[0][0] = c[1];
    f[1][0] = f[0][1] = -0x3f3f3f3f3f3f3f3f;
    
    for (int i=2; i<=n-1; i++){
        memcpy(f_copy, f, sizeof f);
        memset(f, -0x3f, sizeof f);
        for (int r1=0; r1<=1; r1++) {
            f[0][r1] = c[i] + max(f_copy[0][r1], f_copy[1][r1]);
            f[1][r1] = 1 + f_copy[0][r1];
        }
    }
    
    int ans = 1 + f[0][0];
    for (int i=0; i<=1; i++) {
        for (int j=0; j<=1; j++) {
            ans = max(ans, c[n] + f[i][j]);
        }
    }
    
    cout << ans;
    
    return 0;
}

P12666 [KOI 2023 Round 2] 草地上的蚁穴

来看看我写的题解吧。
洛谷似乎人手不够，直到 08-07 16:18 才过审

题意

定义树上的两个节点是和平的，当且仅当在它们之间增加一条边后最大独立集不变。求树上的和平点对数量。

分析

实际上不需要基环树上最大独立集的知识也能做。

正难则反。考虑那些不和平的对。在所有最大独立集中，它们必须都被选中。否则我们可以以一个不都被选中的独立集为基础加边，那么加边后这个集合仍为独立集。

因此，该问题实际上等价于求最大独立集必然包含的节点数 MM，而答案即为所有点对减去不和平的点对，即 (N2)−(M2)\binom{N}{2} - \binom{M}{2}。

如何寻找最大独立集必然包含的节点？
先求原树的最大独立集，再求不选某个点之后的最大独立集，若它们不等，则所有最大独立集必然包含这个点。

于是做法很明了了。换根 DP 即可。

如果你不会换根 DP

  • 把根节点换成与根节点相邻的节点时，其他节点的子树不会改变（如下图绿框）。
  • 由于树形 DP 只局限于一个子树， 因此，这些子树的 DP 值也不会改变。
  • 于是在换根之后，只需重新计算*两个节点的 DP 值即可。

*请注意：
不能直接重新计算，否则会被菊花图卡成 O(n2)O(n^2)。
但是变化的部分也只有这两个节点。因此，计算出换根前后加或减了哪一项是 O(1)O(1) 的。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long  // 有 N*(N-1)/2 的计算

const int maxn = 25e4+100;
vector<int> G[maxn];
int f[maxn][2];  // f[当前节点][当前节点选不选]
int tmp[2];
int mis, m;

void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1] = 1;
    
    for (int v: G[u]) {
        if (v == fa) {
            continue;
        }
        
        dfs(v, u);
        
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

inline void chroot(int old_root, int new_root) {
    // 先把边断掉 
    f[old_root][0] -= max(f[new_root][0], f[new_root][1]);
    f[old_root][1] -= f[new_root][0];
    
    // 再建立新边
    f[new_root][0] += max(f[old_root][0], f[old_root][1]);
    f[new_root][1] += f[old_root][0];
}

void dp(int u, int fa) {
    if (fa != -1) {
        chroot(fa, u);
    }
    
    if (f[u][0] != mis) {
        m++;
    }
    
    for (int v: G[u]) {
        if (v != fa) {
            dp(v, u);
        }
    }
    
    if (fa != -1) {
        chroot(u, fa);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    
    for (int i=1; i<=n-1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs(1, -1);
    mis = max(f[1][0], f[1][1]);
    
    dp(1, -1);
    cout << (n*(n-1)/2 - m*(m-1)/2);
    
    return 0;
}

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)