Educational Codeforces Round 180 (Rated for Div. 2)

25号上午考最后一门数据库，考完就可以尽情写题了，最近一个月都没咋写。

刚才大概数了一下，目前这个博客里的CF博客数量好像是24篇，有点太少阿，虽然也是有几场还没有写博客，但是也很少。

以后必须每场打完就开始写，因为很多时候也是等st，不如早点把博客写了呢...

这场打的勉强还行，排名稍微像人类一点了。E没有思路啊。明天就看看题解吧～（应该是今天）。

A

直接每局就行。

cpp

// Date: 2025-06-23
// Time: 22:34:41
void ChatGptDeepSeek()
{
    int a, x, y;
    cin >> a >> x >> y;
    if(x > y) swap(x, y);
    for(int b = x; b <= y; b++){
        if(abs(b - x) < abs(a - x) && abs(b - y) < abs(a - y)){
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

B

发现最多只需要操作一次，若不为单调递增或递减，则必最多只需要操作一次。

因为这样想，假如对于 $i$ ，有 $a_{i - 1} < a_{i}, a_{i} > a_{i + 1}$ ，所以 a_i 一定可以和 $m i n (a_{i - 1}, a_{i + 1})$ 合并变成 $m a x (a_{i - 1}, a_{i + 1})$ ，小于也是同理，所以若不为有序的，则必只需要操作一次。

cpp

// Date: 2025-06-23
// Time: 22:41:58
void ChatGptDeepSeek()
{
    // x, 
    // 1 3 4 5 6 4 3
    int n;
    cin >> n;
    vi a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];

    }
    for(int i = 1; i < n; i++){
        if(abs(a[i] - a[i + 1]) <= 1){
            cout << "0\n";
            return;
        }
    }
    for(int i = 2; i < n; i++){
        if(a[i - 1] < a[i] && a[i + 1] < a[i]){
            cout << "1\n";
            return;
        }
        if(a[i - 1] > a[i] && a[i + 1] > a[i]){
            cout << "1\n";
            return;
        }
    }
    // 1 4 5 1
    cout << "-1\n";
}

C

当时想得稍微有点复杂，想得也有点慢，用了树状数组，然后我很担心会 fst，因为 1000 * $10^{5}$ 的树状数组，感觉可能会 T 吧，看他们都是二分写的。不过也过了，而且时间挺快的。

就是分析限制，我们就假设选两个小的数是 $a_{l}$ , $a_{r}$ ，第三个数字假如是 $x$ ，则 $x < a_{l} + a_{r}$ 且 $a_{l} + a_{r} + x > a_{n}$ ，显然符合条件的 $x$ 在一个区间里，如果事先给 $a$ 排好序，这里 $a$ 的顺序不影响答案，所以肯定一开始排个序好搞点。

因为 $n \leq 5000$ ，所以双重循环枚举小的两个数字肯定没问题，再用二分来找出合法的第三个数字的区间，当然用树状数组也行，不过确实是稍微麻烦一点。

cpp

// Date: 2025-06-23
// Time: 22:49:48
constexpr int N = int(1e5);
struct Fenwick{
    vector<int> b;
    Fenwick (int n){
        b.assign(n, 0);
    }
    int lowbit(int x){return (x) & (-x);}
    void add(int i, int x){
        while(i < b.size()){
            b[i] += x;
            i += lowbit(i);
        }
    }
    int query(int i){
        int res = 0;
        while(i){
            res += b[i];
            i -= lowbit(i);
        }
        return res;
    }
    int get(int l, int r){
        return query(r) - query(l - 1);
    }
};
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vi a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    // vc<vl> dp(2, vl (N + 1));
    sort(ALL(a));
    // vl dp(3 * a[n] + 1);
    /*
    拿的这三个数
    它们的和要大于最大的数字
    且两个小的数字的和要大于最大的那个数字
    */
    // x + y > z && x + y + z > mx
    // z < x + y, z > mx - x - y
    // z []
    Fenwick tr(a[n] + 1);
    // for(int i = 1; i <= n; i++){
    //     tr.add(a[i], 1);
    // }
    ll ans = 0;
    // for(int l = 1; l < n; l++){
        
    //     for(int r = l + 1; r <= n; r++){
    //         int R = a[l] + a[r] - 1, L = a[n] - a[l] - a[r] + 1;
    //         L = max(a[r], L);
    //         if(L > R) continue;
    //         int cnt = 
    //         // cerr << format("a[l] = {}, a[r] = {}, L = {}, R = {}, cnt = {}, l = {}, r = {}\n", a[l], a[r], L, R, cnt,l , r);
            
    //         ans += cnt;
    //     }
    // }
    for(int r = n; r >= 1; r--){
        
        for(int l = r - 1; l >= 1; l--){
            int R = a[l] + a[r] - 1, L = a[n] - a[l] - a[r] + 1;
            L = max(a[r], L);
            R = min(R, a[n]);
            if(L > R) continue;
            ans += tr.get(L, R);
        }
        tr.add(a[r], 1);
    }
    cout << ans << '\n';
}

然后刚才用二分重写了一个，std::lower_bound 确实爽阿。

cpp

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

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a.begin() + 1, a.end());
    /*
    a[l] + a[r] + x > a[n], x < a[l] + a[r]
    x > a[n] - a[l] - a[r]
    */
    long long ans = 0;
    for(int l = 1; l <= n; l++){
        for(int r = l + 1; r < n; r++){
            auto L = upper_bound(a.begin() + r + 1, a.end(), a[n] - a[l] - a[r]) - a.begin();
            auto R = lower_bound(a.begin() + r + 1, a.end(), a[l] + a[r]) - a.begin() - 1;
            if(L <= R)
                ans += R - L + 1;
        }
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t; cin >> t; while(t--)
    solve(); return 0;
}

D

又是一个不难的D题，稍微想下画画图就看出来啦。

首先必须存在度为2的点，否则无论如何，不可能存在合法的方案。

那么很简单了，就让其他点都恰好只有一条路径，度为2的那个点的子结点的边反一下就行。注意选取的度为2的点，不能是 dfs 选的根节点，然后就没啥要注意的了，直接写就行。

cpp

// Date: 2025-06-23
// Time: 23:34:39
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vc<vi> g(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int vertex = -1;
    for(int i = 2; i <= n; i++){
        if(g[i].size() == 2){
            vertex = i;
            break;
        }
    }
    int root = 1;
    if(vertex == -1){
        if(g[1].size() == 2){
            root = 2;
            vertex = 1;
        }else{
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    vc<pii> ans;
    auto dfs = [&](auto &&self, int u, int pre, int s) -> void{
        if(u == vertex) s ^= 1;
        for(auto v : g[u]){
            if(v == pre) continue;
            if(s) ans.push_back({u, v});
            else ans.push_back({v, u});
            self(self, v, u, s ^ 1);
        }
    };

    dfs(dfs, root, 0, 1);
    for(auto [u, v] : ans)
        cout << u << " " << v << '\n';
}

E

upd: 考完了，但并没有刷题，只是把这个 E 题看了一下，直接启动的题解，因为过的人算挺少。但是这题挺有意思的，要是多想一下就好了，虽然不一定能想得出来。

如果一个节点不是绿色，那么这颗子树必然颜色全都相同，否则假如这里有其他颜色，则到根节点必须经过不同的颜色。

但如果自己想，就算想到了这个，可能也很难写。由于我是看了题解的，所以要用dp，这还真没想过要dp。

让 $c n t_{u}$ 表示 $u$ 为绿色时，以 $u$ 为根节点的子树的染色方式，如果 $u$ 为黄色或者蓝色，都只会有一种染色方式。所以 $u$ 的子树的染色方式是 $c n t_{u} + 2$ 。

因为每个子树都可以被独立的染色，因此 $cnt_v = (cnt_{u1} + 2)(cnt_{u2} + 2) \ldots (cnt_{uk} + 2) $，其中 $u 1, u 2, \dots, u k$ 是 $v$ 的子节点。

然后就可以用 $d p$ 求了：让 $d p_{m}$ 是 $m$ 种染色方法的树的最小节点数，注意到每个节点的染色数是它的子节点的染色数的乘积，那么 $d p_{m} = m i n (d p_{m}, d p_{\frac{m}{x}} + d p_{x - 2})$ ，其中 $x$ 为 $m$ 的因子。

这里怎么理解呢？相当于是我们去找一个已经染色数为 $\frac{m}{x}$ 的树，那么我们只要再加一个染色树为 $x$ 的树，那么新的树的染色树就会正好是 $m$ ，因为多一个子节点，就可以乘子节点的染色数。那么为什么是 $x - 2$ 呢？因为我们的 $d p$ 表示的是根节点为绿色的染色需要的节点数量，它作为子节点时，染色数量是要 $+ 2$ 的，所以我们这里直接减。

直接枚举 $m$ 和因子，时间复杂度是 $O (M \sqrt{M})$ ,也可以 $O (M \log M)$ 。

cpp

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

constexpr int M = int(5e5);
constexpr int inf = int(1e9);
int dp[M + 1];

void solve(){
    int m;
    cin >> m;
    cout << (dp[m] != inf ? dp[m] : -1) << '\n';
}
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    for(int i = 1; i <= M; i++)
        dp[i] = inf;
    dp[1] = 1;
    for(int m = 2; m <= M; m++){
        for(int p = 1; p * p <= m; p++){
            if(m % p) continue;
            if(p > 2) dp[m] = min(dp[m], dp[m / p] + dp[p - 2]);
            if(m / p > 2) dp[m] = min(dp[m], dp[p] + dp[m / p - 2]);
        }
    }
    int t; cin >> t; while(t--)
    solve(); return 0;
}

$M \log M$ 的,哇这个枚举因子很快啊。

cpp

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

constexpr int M = int(5e5);
constexpr int inf = int(1e9);
int dp[M + 1];

void solve(){
    int m;
    cin >> m;
    cout << (dp[m] != inf ? dp[m] : -1) << '\n';
}
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    for(int i = 1; i <= M; i++)
        dp[i] = inf;
    dp[1] = 1;
    for(int a = 1; a <= M; a++){
        for(int b = 1; b * (a + 2) <= M; b++)
            dp[(a + 2) * b] = min(dp[(a + 2) * b], dp[a] + dp[b]);
    }
    int t; cin >> t; while(t--)
    solve(); return 0;
}

Educational Codeforces Round 180 (Rated for Div. 2) ​

A ​

B ​

C ​

D ​

E ​

Educational Codeforces Round 180 (Rated for Div. 2)

A

B

C

D

E