2025年一月算法比赛（一）

[[ slider_text ]]

[[ item.c ]]

2025年一月算法比赛（一）

发布时间 2025-04-18 作者：秋千月 来源：算法小站

笛卡尔树 数位dp 二分图 数论分块

## Codeforces Global Round 28
### E
**[E. Kevin and Bipartite Graph](https://codeforces.com/contest/2048/problem/E)**
给定左边$$2n$$个点，右边$$m$$个点的**完全二分图**，现在用$$[1, n]$$的一种颜色，给边染色
如果不存在所有边都是一种颜色的环，我们认为这个方案是好的
现在需要判断，对二分图能不能构造出一个好的染色方案？如果可以，输出方案

**算法分析**
![](/media/content_img/CF28-E1.png)
![](/media/content_img/CF28-E2.png)

### F
**[F. Kevin and Math Class](https://codeforces.com/contest/2048/problem/F)**
**问题描述**
给定$$a_1, a_2, \cdots, a_n$$和$$b_1, b_2, \cdots, b_n$$，可以选择两个数$$l \leqslant r$$
并且取$$x = \min (b_l, \cdots, b_r) $$，然后将$$(a_l\cdots a_r)$$这些数，都改成$$\lceil a_i / x \rceil$$
要使得$$a$$全部变成$$1$$，问最小的操作次数

**算法分析**
![](/media/content_img/cf28f1.png)
![](/media/content_img/CF28-F2.png)

#### 算法实现
```bash
void solve() {
    int n;
    cin >> n;
    vector<i64> a(n+1, 0), b(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

vector<int> l(n+1, 0), r(n+1, 0);
    int root = 0;

auto build = [&]() -> void {
        stack<int> stk;
        for (int i = 1; i <= n; i++) {
            int last = 0;
            while (!stk.empty() && b[stk.top()] > b[i]) {
                last = stk.top();
                stk.pop();
            }

if (!stk.empty()) r[stk.top()] = i;
            else root = i;

l[i] = last;
            stk.push(i);
        }
    };
    build();

const int m = 63;

vector<vector<i64> > dp(n+5, vector<i64>(m+5, inf<i64>));
    auto dfs = [&](auto &dfs, int u) -> void {
        if (!l[u] && !r[u]) {
            dp[u][0] = a[u];
            for (int i = 1; i <= m; i++) dp[u][i] = (dp[u][i-1] + b[u] - 1) / b[u];
            return;
        }

if (l[u]) dfs(dfs, l[u]);
        if (r[u]) dfs(dfs, r[u]);

if ((l[u] && r[u]) == 0) {
            auto v = (l[u] == 0 ? r[u] : l[u]);
            for (int i = 0; i <= m; i++) chmin(dp[u][i], max(a[u], dp[v][i]));
            for (int i = 1; i <= m; i++) chmin(dp[u][i], (dp[u][i-1] + b[u] - 1) / b[u]);
            return;
        }

for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= i; j++) chmin(dp[u][i], max( {a[u], dp[l[u]][j], dp[r[u]][i-j]} ));
        }

for (int i = 1; i <= m; i++) chmin(dp[u][i], (dp[u][i-1] + b[u] - 1) / b[u]);
    };
    dfs(dfs, root);

int res = 0;
    for (int i = 0; i <= m; i++) if (dp[root][i] == 1) {
        res = i;
        break;
    }

cout << res << "\n";
}
```

## AtCoder Beginner Contest 390
### D - Stone XOR
**[D - Stone XOR](https://atcoder.jp/contests/abc390/tasks/abc390_d)**
给定$$n$$个背包，执行以下操作任意次
选择两个背包$$i, j$$，将背包$$i$$中的物品全部放到背包$$j$$中，然后清空背包$$i$$
现在记最后操作完，背包的物品重量是$$b_i$$，求解$$b_1 \oplus b_2 \oplus \cdots \oplus b_n$$有多少个不同的值

**算法分析**
![](/media/content_img/ABC390E.png)
另外，还有枚举子集的做法，考虑哪些数未被放入
![](/media/content_img/ABC390E2.png)

## 牛客寒假算法基础集训营3
### G
**[智乃与模数](https://ac.nowcoder.com/acm/contest/95335/G)**
输入一个$$n$$，现在把所有$$i \in [1, n], n \bmod i$$的结果，单调减排列，问前$$k$$个数的和

**数论分块**
![](/media/content_img/coder3-G1.png)
![](/media/content_img/coder3-G2.png)

## 牛客周赛72
### E.小红的01串（五）
**[E.小红的01串](https://ac.nowcoder.com/acm/contest/98256/E)**
给你一个 01 串，可以将`?`替换成`0 or 1`，使得串表示的数是`13`的倍数，求方案数
![](/media/content_img/coder72E.png)

上一篇：最大流，最小割和匹配（一）下一篇：2025年一月算法比赛（三）

看完文章有啥想法