四月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

四月算法竞赛选题（一）

发布时间 2025-04-20 作者：zhangminchen 来源：算法小站

线段树 dp计数 最短路 三分 中位数

## 钉耙编程春季联赛 6
### 1009 键帽
**[键帽](https://acm.hdu.edu.cn/contest/problem?cid=1155&pid=1009)**
**问题描述**
如果一个小写字母字符串中，不存在超过$$m$$个元音字母相邻，就认为它是好串
现在问长度为$$n$$的小写字母字符串中，有几个好串？对$$10^9 + 7$$取模

**算法分析**
> dp 方程怎么写？

定义$$dp(i, k, 0/1)$$表示第$$i$$个位置，已经有$$k$$个相邻元音字符，并且最后一个位置`不是 or 是`元音字符的方案数
```math
\displaystyle
dp(i, k, 0) \leftarrow \begin{cases} dp(i-1, k, 0) \cdot \binom{21}{1}  \\ 
dp(i-1, k, 1) \cdot \binom{21}{1} \end{cases}
```
```math
\displaystyle
dp(i, k, 1) \leftarrow \begin{cases} dp(i-1, k, 0) \cdot \binom{5}{1} \\
dp(i-1, k-1, 1) \cdot \binom{5}{1}\end{cases}
```
> 主要就是 dp 的优化，考虑我们只需要知道前缀，能不能把$$k$$这一维给优化掉？
另外还需要注意的是，不合法的是，多于$$\geqslant m+1$$个，**连续的元音字母**，总的元音字母有多少个不需要管

于是我们有一个想法，能不能在**恰好出现**$$m+1$$个元音字母的时候，**立刻**在方案数中，把不合法的剔除？

> 不能出现连续$$m$$个，那么只要一出现，就立刻从方案数中剔除（**一出现立刻剔除**）

实际上，我们可以优化掉$$k$$这维，因为我们求的是（下面用了滚动数组）
```math
\displaystyle
\sum_{k = 0}^{\min(m, i)} dp(k, 0) = \sum_{k=0}^{\min(m, i-1)} (  last(k, 0)   \cdot 21 ) + \sum_{k = 1}^{\min(m, i-1)} (last(k, 1) \cdot 21)
```
如果我们记
```math
\displaystyle
f(i, 0) = \sum_{k = 0}^{\min(m, i)} dp(k, 0), \quad f(i, 1) = \sum_{k = 1}^{\min(m, i)} dp(k, 1)
```
那么我们有$$f(i, 0) = (f(i-1, 0) + f(i-1, 1)) \cdot 21$$

对于$$f(i, 1)$$也类似，同样有$$f(i, 1) = (f(i-1, 0) + f(i-1, 1)) \cdot 5$$

> 下面考虑剔除

注意到对于$$i \leqslant m$$的情况，上述式子**没有问题**
仅考虑$$i > m$$的情况，只要$$i > m$$，那么$$i$$位置就存在**连续$$m+1$$个元音字母**的可能性
此时，对于$$f(i, 1)$$，那么存在`[i-m, i]`都是元音字母的状态，而$$i-m-1$$这个位置是**辅音字母**，再往前都是合法的
这个时候，$$i$$位置，$$f(i, 1)$$就存在一种**恰好不合法的状态**，将其扣除，$$f(i, 0)$$没有不合法状态

每次一出现这样的不合法状态，就立马扣除，只在$$f(i, 1)$$中扣除，这样就是**不重不漏**了
```math
del = f(i-m-1, 0) \cdot 5^{m+1}, \quad f(i, 1) = f(i, 1) - del
```

## Codeforces Round 963 (Div. 2)
### D
**[D. Med-imize](https://codeforces.com/contest/1993/problem/D)**
**问题描述**
给定$$n, k$$，长度为$$n$$的序列，一次操作可以选择$$a$$的，**连续的**长度为$$k$$的子数组，
并且将其从$$a$$中移除，剩下的元素不改变顺序

现在只要$$|a| > k$$，你就需要重复上述操作，问这样操作能够得到的数组中，中位数最大是多少？

**算法分析**
![](/media/content_img/cf963d1.png)
![](/media/content_img/cf963d2.png)

## 三分单峰函数求最值
![](/media/content_img/ternary-search.png)

```bash
void solve(int cas) {
    auto f = [&](int x) -> i64 {
        //
    };

int l = 1, r = 1e9;
    while (r - l > 3) {
        int ml = (2*l + r) / 3, mr = (2*r + l) / 3;

if (f(ml) > f(mr)) r = mr;
        else l = ml;
    }

i64 ans = 0;
    for (int i = l; i <= r; i++) chmax(ans, f(i));
}
```

## Educational Codeforces Round 166
### D
**[D. Invertible Bracket Sequences](https://codeforces.com/contest/1976/problem/D)**
定义正规的括号序列，当且仅当形如`() (), (())`，下面定义括号序列的反转
将所有的`(`替换成`)`，将所有`)`替换成`(`
现在给你一个正规括号序列`s`，问如果把`[l, r]`子串翻转之后，使得`s`仍然是正则的，这样的$$(l, r)$$对数

**算法分析**
> 括号合法的充要条件是什么？

对于`(`，记为`+1`，否则记为`-1`，必须满足前缀和数组`S`
```math
\displaystyle
\begin{cases}
S_n = 0 \\
\min_{i=1}^{n} S_i \geqslant 0
\end{cases}
```
![](/media/content_img/edu166d1.png)
![](/media/content_img/edu166d2.png)

## Codeforces Round 965 (Div. 2)
### D
**[D. Determine Winning Islands in Race](https://codeforces.com/contest/1998/problem/D)**
> 有向图

给你$$n$$个点，定义**主路**，$$n-1$$条，连接$$(i, i+1), 1 \leqslant i \leqslant n-1$$，另外还有$$m$$条**可选路径**
注意，Elsie 可以用主路也可以用可选路径，但是 Bessie 只能用主路，这是一个**有向图**，所有的路都是从**编号较小的连到较大的**

下面 Elsie 和 Bessie 轮流，Bessie 先开始，Bessie 在起点$$s$$，Elsie 在起点$$1$$，策略如下
如果当前位于点$$i$$上，如果$$i \to j$$有路径，可以走到点$$j$$上，同时点$$i$$**消失**，意味着所有和$$i$$相邻的路径也消失，同时

1.如果没有任何一条边和$$i$$相连，那么$$i$$点会消失，同时位于$$i$$上的人被淘汰
2.如果两个人同时在点$$i$$上，那么一个人从$$i$$走到其他点$$j$$之后，$$i$$自动消失，同时另一个人被淘汰
3.消失的边，或者点，不能再被使用了
4.如果一个人被淘汰了，接下来他的回合会被跳过

这样的游戏结束，当且仅当有一个人到达$$n$$点，Bessie 获胜的条件是他先到达$$n$$点
对于$$1 \leqslant s \leqslant n - 1$$，决策 Bessie 能不能获胜，假设两个人都采用最佳策略

**算法分析**
![](/media/content_img/cf965d.png)

## 钉耙编程春季联赛7
### 1004最早连续串
**[最早连续串](https://acm.hdu.edu.cn/contest/problem?cid=1156&pid=1004)**
给定一个01串，若干询问，问第一个出现连续的`k`个`0 or 1`的位置`[p, p+k-1]`，然后反转这个区间

**算法分析**
> 满足条件的区间有什么特点？

实际上，对于每个位置$$i$$，$$lasts(i)$$表示$$i$$往前，（保证字符和$$s_i$$相同的情况下），能延伸的**最长的长度**
`lasts(i, 0), lasts(i, 1)`，分别表示`s[i] = {0 / 1}`情况下，能延伸的最长长度
那么我们要求，满足$$lasts(i) \geqslant k$$的最小的$$i$$，这可以用线段树二分求解
线段树维护`lasts[...]`的`max`值即可

> 那么修改呢？

修改操作也不难，假设我们改了目标区间`[l, r]`，比如`[l...r] = 0`，只要计算`[1...l-1]`后缀`0`的长度
以及`[r+1...n]`前缀`0`的长度，这两者都可以用线段树维护，合并的时候考虑一下细节即可
每个区间维护`pre[0/1], suf[0/1]`就可以很方便解决了

## 删边最短路
### Codeforces Round 558 F
**[F. Indecisive Taxi Fee](https://codeforces.com/problemset/problem/1163/F)**
给定$$n$$个点$$m$$条边的无向图$$G$$，边$$i$$的代价是$$w_i$$，现在问如果修改$$w_i \to x$$
那么$$1 \to n$$的最小代价是多少

**算法分析**
> 删边最短路

![](/media/content_img/cf558f1.png)
![](/media/content_img/cf558f2.png)

#### 算法实现
```bash

template <typename T>
class Graph {
public:
    struct _Edge {
        int from;
        int to;
        T cap;
    };
    int _n;
    vector<_Edge> e;
    vector<vector<int> > g;
    vector<T> dis;
    vector<int> onpath, le, ri, istree;
    vector<pair<int, int> > pre;

Graph() {}
    Graph(int n) {
        init(n);
    }

void init(int n) {
        this->_n = n;
        e.clear();
        g.assign(n+5, {});
        dis.assign(n+5, INF);

onpath.assign(n+5, 0), le.assign(n+5, 0), ri.assign(n+5, 0);
        istree.assign(maxn, 0), pre.assign(n+5, make_pair(-1, -1));
    }

int addEdge(int from, int to, T cap = 1) {
        int id = (int) e.size();
        g[from].push_back(id), g[to].push_back(id);
        e.push_back({from, to, cap});
        return id;
    }

void dijkstra(int s, int sgn = 0) {
        dis.assign(this->_n + 5, INF);

priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>> > heap;
        dis[s] = 0;
        heap.push({dis[s], s});

while (heap.size()) {
            T expected = heap.top().first;
            int x = heap.top().second;
            heap.pop();
            // if and only if, when dis[x] == exactly shortest path!
            if (dis[x] != expected) continue;

for (auto id : g[x]) {
                auto [from, to, cap] = e[id];
                int y = x ^ from ^ to;
                if (dis[y] > dis[x] + cap) {
                    dis[y] = dis[x] + cap;
                    if (sgn == 0) pre[y] = make_pair(x, id);

if (sgn == 1 && !onpath[y]) le[y] = le[x];
                    if (sgn == 2 && !onpath[y]) ri[y] = ri[x];
                    heap.push({dis[y], y});
                }
            }
        }
        return;
    }

// out dijkstra tree
    vector<int> getEdge(int s, int t) {
        vector<int> has(this->_n + 5, 0);

for (int eid = 0; eid < (int) e.size(); eid++) {
            auto [from, to, cap] = e[eid];
            if (dis[from] > dis[to]) swap(from, to);

if (dis[from] + cap == dis[to]) {
                if (!has[to]) {
                    has[to] = 1;
                }
            }
        }

vector<int> path;

auto dfs = [&](auto &dfs, int u) -> void {
            if (u <= 0) return;
            auto [from, eid] = this->pre[u];
            dfs(dfs, from);

path.emplace_back(u);
            if (eid != -1) istree[eid] = 1;

};
        dfs(dfs, t);

for (auto u : path) {
            onpath[u] = 1;
            le[u] = ri[u] = u;
        }

return path;
    }
};

// ============================================================================ //

void solve(int cas) {
    int n, m, q;
    cin >> n >> m >> q;

using pii = pair<int, int>;
    using arr = array<int, 3>;
    vector<arr> edges;

Graph<i64> g(n);

for (int i = 0; i < m; i++) {
        int u, v, z;
        cin >> u >> v >> z;

g.addEdge(u, v, z);
        edges.emplace_back(arr{u, v, z});
    }

g.dijkstra(1);
    auto path = g.getEdge(1, n);
    // debug(g.onpath);

g.dijkstra(1, 1);
    auto f1 = g.dis;

g.dijkstra(n, 2);
    auto f2 = g.dis;

//debug(g.le);

// discrete
    int M = 0;
    map<int, int> idx, rm;
    for (auto u : path) idx[u] = ++M, rm[M] = u;

// segtree
    lazy_segtree<i64, op, i64, mapping, comp, id> tr(vector<i64>(M+5, INF), M);
    // debug(g.onpath);

auto upd = [&]() -> void {
        for (int i = 0; i < edges.size(); i++) {
            auto [u, v, w] = edges[i];

if (g.istree[i]) continue;

i64 z = f1[u] + w + f2[v];
            auto _x = g.le[u], _y = g.ri[v];
            auto x = idx[_x], y = idx[_y];

if (x <= y - 1) tr.modify(1, 1, M-1, x, y-1, z);

swap(u, v);
            z = f1[u] + w + f2[v];
            _x = g.le[u], _y = g.ri[v];
            x = idx[_x], y = idx[_y];

if (x <= y - 1) tr.modify(1, 1, M-1, x, y-1, z);
        }
    };
    upd();

while (q--) {
        int i, x;
        cin >> i >> x;
        i--;

auto [u, v, w] = edges[i];
        if (! g.istree[i] ) {
            // not tree edge
            i64 res = f1[n];
            chmin(res, 1LL * f1[u] + f2[v] + x);
            chmin(res, 1LL * f1[v] + f2[u] + x);

cout << res << "\n";
        }
        else {
            // tree edge
            if (x < w) {
                i64 res = 1LL * f1[u] + x + f2[v];
                chmin(res, 1LL * f1[v] + x + f2[u]);
                cout << res << "\n";
                continue;
            }

i64 res = 1LL * f1[n] - w + x;
            chmin(res, 1LL * f1[u] + x + f2[v]);
            chmin(res, 1LL * f1[v] + x + f2[u]);

auto j = min(idx[u], idx[v]);
            // debug(j);
            
            i64 may = tr.query(1, 1, M-1, j, j);
            chmin(res, may);

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

上一篇：2025年一月算法比赛（三）已经是最后一篇啦

看完文章有啥想法