2024-11月一些算法比赛（一）

[[ slider_text ]]

[[ item.c ]]

2024-11月一些算法比赛（一）

发布时间 2024-11-25 作者：秋千月 来源：算法小站

ST表 dp计数 状态压缩dp 双指针

## 牛客周赛 68
### D
**[红魔馆的馆主（二）](https://ac.nowcoder.com/acm/contest/95928/D)**
**问题描述**
给定一个序列，要你选出$$i < j$$，最多有多少种选法，使得$$a_i \cdot a_j$$是$$495$$的倍数？

**算法分析**
这种问题，一般从$$495$$的素因子分解入手，$$495 = 3 \cdot 3 \cdot 5 \cdot 11$$
也就是说，组成$$495$$，**至少需要提供**`2 个 3， 1 个 5， 1 个 11`

于是自然，我们可以想到用`dp[ how many 11 ][ how many 5 ][ how many 3 ]`
表示说，前缀中能够提供`(how_many_11, how_many_5, how_many_3)`的数有多少个

这样，针对不修改的情况，就可以 dp 了，具体来说，考虑$$a_i$$
看一下`a[i]`中能提供`几个 3， 几个 5， 几个 11`，不妨设为`cnt3, cnt5, cnt11`
那么我们还需要几个 3，几个 5，几个 11 呢？
分别是`max(0, 2-cnt3), max(0, 1-cnt5), max(0, 1-cnt11)`
实际上就是`dp[ max(0, 1-cnt11) ][ max(0, 1-cnt5) ][ max(0, 2-cnt3) ]`，将其加到`res`即可

那么$$a_i$$本身能提供几个$$3$$，几个$$5$$呢，实际上，能提供$$x \in [0\cdots \min(2, cnt3)]$$个`3`
取 min 是因为我们只需要`2`个，多的不要
记`up3 = min(2, cnt3), up5 = min(1, cnt5), up11 = min(1, cnt11)`，这样$$x \in [0, up3], y \in [0, up5], z \in [0, up11]$$
就可以维护好 `dp`了，`dp(x, y, z) += 1`

> 好了，那么把$$a_i + 1$$怎么处理

以上不修改的答案算出来是`res`
因为是**单点修改**，可以考虑修改之后，答案会怎么变化的
枚举修改$$a_i$$，那么`dp`值中应该先扣除`i`这个位置的贡献，按照之前的方法，`dp(x, y, z) -= 1`即可
答案会怎么变化呢？记`delta`表示答案的变化量
应该先扣除之前算出来的`delta -= dp[ max(0, 1-cnt11) ][ max(0, 1-cnt5) ][ max(0, 2-cnt3) ]`

然后令`now = a[i] + 1`，根据这个`now`计算**新的**`cnt3, cnt5, cnt11`
再另`delta += dp[ max(0, 1-cnt11) ][ max(0, 1-cnt5) ][ max(0, 2-cnt3) ]`即可

和全局的`ans = max(ans, res + delta)`即可

最后**还原现场**，把原来旧的贡献再加回来，`dp(x, y, z) += 1`

## AtCoder Beginner Contest 379
### E
**[E - Sum of All Substrings](https://atcoder.jp/contests/abc379/tasks/abc379_e)**
**问题描述**
给你一个字符串，需要输出$$\sum\_{i = 1}^{n}\sum\_{j = i}^{n}f(i, j)$$
其中$$f(i, j)$$表示把$$[i, j]$$子串看成十进制时候的值

**算法分析**
> 考虑枚举右端点

不难发现$$i$$作为右端点，对答案的贡献是$$dp(i) = dp(i-1) \cdot 10 + i \cdot S_i$$
进一步展开写
```katex
\begin{cases}
dp_1 = S_1  \\
dp_2 = 10S_1 + 2S_2  \\
dp_3 = 10^2 S_1 + 10\cdot 2S_2 + 3S_3 \\
dp_4 = 10^3 (1S_1) + 10^2 (2S_2) + 10^1(3S_3) + 10^0(4S_4)
\end{cases}
```
按照$$10$$的幂指分类，我们假设$$n = 4$$
```math
ans_4 = 10^3 (1S_1) + 10^2(2S_2 + 1S_1) + 10^1 (3S_3 + 2S_2 + 1S_1) + 10^0 (4S_4+3S_3+2S_2 +1S_1)
```

综上所述，我们有$$ans = \sum\_{i = 1}^{n} 10^{n-i} \left( \sum\_{j = 1}^{i} jS_j \right)$$

> 这个怎么计算

不难发现，$$\sum\_{j =1}^{i} jS_j = A_i$$，可以通过前缀和预处理

这样$$ans = \sum\_{i = 1}^{n} 10^i \cdot A\_{n-i}$$，这像什么？是不是有点像位运算？
考虑$$10^1  A\_{n-1} + 10^2  A\_{n-2} + 10^3 A\_{n-3} + \cdots $$

好像是第一位填$$A\_{n-1}$$，第二位填$$A\_{n-2}$$，以此类推，但是$$A_i$$都是很大的数啊，怎么办呢？

考虑递推的阶段，比如$$B + 10\cdot C$$怎么算？**一位一位来看**

```math
\displaystyle
\begin{aligned}
b_0+10^0 +  &b_1 \cdot 10^1 + b_2 \cdot 10^2 + \cdots  + &b_m \cdot 10^m &   \\
&c_0 \cdot 10^1 + c_1 \cdot 10^2 +\cdots + & c_{m-1}\cdot 10^m &+ c_m \cdot 10^{m+1} 
\end{aligned}
```

比如看第$$1$$位，$$\sum 10^i A\_{n-i}$$，$$c_0 \cdot 10^1$$之后，不会再出现对$$10^1$$有贡献的位了
这样从低位到高位考虑的时候，算完一个低位，就可以扔掉它

具体来说，从低位到高位考虑，考虑第$$i$$位，意味着之前$$[0\cdots i-1]$$位都被扔掉了
对第$$i$$位有贡献的，也就只有当前的$$i$$对应的值，此时令$$sum = sum + A\_{n - i}$$，$$sum \bmod 10$$就是第$$i$$位的数

接下来考虑更高的位，把第$$i$$位舍去，$$sum = sum / 10$$，这样迭代之后，就可以求解了

### F
**[Buildings 2](https://atcoder.jp/contests/abc379/tasks/abc379_f)**
**问题描述**
建筑$$i$$能看到$$j$$，当且仅当$$k \in [i+1, j-1]$$中的所有建筑的高度，$$H_k \leqslant H_j$$
现在给定若干询问，每个询问给定$$l, r$$，问在区间$$[r+1 \cdots n]$$中，能够**同时被`l, r`两栋建筑都看到的**建筑，有多少个

**算法分析**
> 建筑$$j$$被看到之后，$$[j+1\cdots n]$$中有多少个建筑可以被看到呢？

不难发现，如果建筑$$j_0$$被看到了，那么之后能被看到的建筑满足$$h(j_0) \leqslant h(j_1) \leqslant h(j2) \cdots \leqslant h(j_m)$$
其中$$r+1 \leqslant j_1$$，并且$$j_m \leqslant n$$

**这个问题，等价于**
**给你一个序列，问**下标$$j$$这个位置，右边有多少个$$\geqslant a_j$$的数（包括$$a_j$$本身）

这可以用**单调栈**解决，普通的单调栈，从后往前扫描，记$$to_i$$表示$$i$$右边第一个$$\geqslant a_i$$的数的**下标**
那么问有多少个$$\geqslant a_i$$的数就更简单了
维护好$$i$$进栈之后，直接`seen[i] = stk.size()`，返回**size**，就是右边有多少个$$\geqslant$$它的数了

> 进一步分析，建筑要被$$l, r$$都看到，要满足什么条件呢？

不难发现，记$$[l, r]$$最高的建筑的高度是`mx`，那么$$j \in [r+1, n]$$中的建筑要能被看见
当且仅当$$h_j \geqslant mx$$，并且必须是$$[r+1, n]$$中第一个$$\geqslant mx$$的数

那么就可以用**线段树二分**来做
1）先找到$$[l, r]$$中最大的建筑高度`mx`
2）线段树在区间`[r+1, n]`中，找`min_left`，满足第一个$$\geqslant mx$$的位置，找到这个位置`p`
3）最后`seen[p]`就是答案

> 坑点，如果建筑`l`的高度就是`[l, r]`区间的最大值（或者和最大值相等）怎么办？

这个时候，$$l$$是一定可以看到`[l, r]`区间的所有建筑的
那么`[r+1, n]`中的建筑能不能被看见，是根据`[l+1, r]`的最大值来决定的
这个时候，令`H = max[l+1, r]`，只需要再找一个`[l+1, r]`的最大值即可

### G
**[G - Count Grid 3-coloring](https://atcoder.jp/contests/abc379/tasks/abc379_g)**
**问题描述**
给定一个 grid，如果你遇到`?`，你可以填上`1, 2, 3`任意一种数，问你方案数
当然有一些限制，就是相邻的方格（有公共边），不能是同一种数

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

**考虑三进制状态压缩**，和 [G - Everlasting LIDS](https://atcoder.jp/contests/abc378/tasks/abc378_g) 这个杨表的 dp 有点类似

```bash
// 其他一些操作，诸如转置矩阵，使得 H >= W 之类的，省略

void solve() {
	//...
    vector<int> pw(w+1, 0);
    pw[0] = 1;
    for (int i = 0; i < w; i++) pw[i+1] = pw[i] * 3;

map<int, mint> dp, ndp;
    dp[0] = 1;

for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        map<int, mint> ndp;

for (int x = 0; x < 3; x++) {
            for (const auto &[sta, dpv] : dp) {
                if ( grid[i][j] != '?' && grid[i][j] - '1' != x ) continue;
                int le = sta % 3, top = sta / pw[w-1];

if (j > 0 && le == x) continue;
                if (i > 0 && top == x) continue;

int nsta = (sta * 3 + x) % pw[w];
                ndp[nsta] += dpv;
            }
        }

swap(ndp, dp);
    }
    mint ans = 0;
    for (auto [sta, dpv] : dp) ans += dpv;
    printf("%d\n", ans.val());
}
```

## AtCoder Beginner Contest 381
### D
**[D - 1122 Substring](https://atcoder.jp/contests/abc381/tasks/abc381_d)**
**问题描述**
给定一个序列，问最长的连续子序列，满足子序列是 1122 的
子序列是 1122，当且仅当，长度为偶数，并且$$a(i) = a(i+1)$$，并且每一个数恰好出现`2`次
换句话说，取`i, i+2, i+4, ...`，这些下标的数，都是两两不同的

**算法分析**
不难想到用**滑动窗口**来做，滑动窗口有没有什么比较好的写法呢？
**[最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/description/)**这个滑动窗口的经典问题
```bash
string minWindow(string s, string t) {
    int n = s.size();

map <char, int> need, now;
    for (auto x : t) need[x]++;

auto ok = [&]() -> bool {
        for (auto [x, num] : need) {
            if (now[x] < num) return false;
        }
        return true;
    };
    
    int j = 0;
    int ans = n+1, pos = 0;
    string res = "";

for (int i = 0; i < n; i++) {
        j = max(j, i);
        while (!ok() && j < n) now[s[j]]++, j++;

// [i, j)
        if (ok() && j - i < ans) {
            ans = j-i, pos = i;
        }
        now[s[i]]--;
        if (now[s[i]] == 0) now.erase(s[i]);
    }
    ans > n ? res = "" : res = s.substr(pos, ans);
    return res;
}
```
一般可以写成
```bash
int j = 0;
for (int i = 0; i < n; i++) {
	j = max(j, i);
	while ( [i...j] 窗口需要继续扩展，并且 j < n ) mp[ a[j] ]++，维护相关信息，j++;
	
	[i, j) 就是 i 开始往后扩展，满足条件的区间
	if [i, j) 区间满足条件:		更新 ans
	
	将 i 这个点的信息删除, mp[ a[i] ]--
}
```

> 这个问题也是如此

只是，这个问题需要注意的**坑点**，在于形如`1 1 2 2`的子串，长度是偶数
而我们在用滑动窗口的时候，是按`i -> i += 2`来扩展窗口，那么会出现如下情况
```bash
[x x x x ... O] O
x [x x x ... O  O]

很可能会遇到，下面一种结果更优
但是我们按 i += 2 来扩展滑动窗口的时候，下面一种情况考虑不到
```
这其实也很好解决，只需要新建一个数组`b`，`b`数组把`a`的第一个元素**扔掉**
然后对`b`元素再跑一遍滑动窗口，取一个最优解即可

> 滑动窗口好久没写了，有一个好写的方法要记一下

1）for 慢指针$$i$$，然后跑快指针$$j$$，跑之前记得`j = max(j, i)`
2）快指针$$j$$尽可能往前走，直到走到不能走为止，$$[i, j)$$是满足的区间
3）快指针**悬停等待**，然后慢指针`++i`，在`+`之前呢，要把$$i$$位置上相应的信息删掉，并且维护好
也不用担心慢指针跑太过了，跑过了说明前面都不满足，我们一开始执行`j = max(j, i)`
保证了如果都不满足，就以$$i$$当前位置，作为起点，重新开始跑

## 牛客周赛 67
### E	
**[小苯的区间选数](https://ac.nowcoder.com/acm/contest/95016/E)**
给定两个区间$$[l_1, r_1], [l_2, r_2]$$，在区间中各取一个数，计算两个数的和$$sum$$，使得$$sum$$的数位和最大

**算法分析**
假设我们选了$$l_1 \leqslant x \leqslant r_1, l_2 \leqslant y \leqslant r_2$$，要使得$$x+y$$数位和最大
注意到限制$$l_1 + l_2 \leqslant x+y \leqslant r_1+r_2$$
实际上，我们只需要考虑在$$[l,r] \leftarrow [l_1+l_2, r_1+r_2]$$中选一个数，使得数位和最大

**这就是经典的数位 dp 问题**
回顾一下，数位 dp 如何做的呢？假设只有一个下界，我们要找出$$\geqslant l$$的数
令`dp(i, larger)`，需要一个`larger`来记一下，当前的数的前缀是否大于`l`的前缀
如果前缀`> l 的前缀`，那么`i`这一位就可以从`0`开始放，否则就要从`d[i]`开始放

那么上下界也一样，`dp(i, larger, smaller)`表示当前考虑第$$i$$位，下界的前缀是`larger`
上界的前缀是`smaller`
```bash
dx = 下界的第 i 位
dy = 上界的第 i 位
lo = larger ? 0 : dx
hi = smaller ? 9 : dy

然后考虑放入当前位 i，枚举放入 c = [lo...hi]
res = max(res, c + dfs(i+1, larger | (c > dx), smaller | (c < dy)) )
```

### F
**[小Z的树迁移](https://ac.nowcoder.com/acm/contest/95016/F)**
树上的每一条边都有一个权值，$$q$$个询问，给出`u d`，`u`表示目前在的节点，`d`表示往下移动的次数
要求向下移动，路径上的边权和最大，输出最大边权和，没有合法路径输出`-1`

**算法分析**
> 假设小 Z 在`u`点，那么能够到达的点要满足什么条件？

不难发现，能够到达的点一定是深度为$$dep_v = dep_u + d$$的点，于是需要一个`dep`表
记一下`dep(d) = {v1, v2, ...., vk}`

> 怎么满足路径边权和最大？

来看一下边权和怎么表示？因为是一棵树，可以用**树上差分**的思路，如果我们要求$$u \to v$$的边权和
因为是一棵树，所以从根节点 root 到`u`的路径是唯一的
可以记$$dp_u$$表示根节点$$1 \to u$$的路径权值和，那么$$u \to v$$的路径权值和就可以表示成$$dp_v - dp_u$$

这样，我们需要的条件就可以形式化地如下表示
1）在`nowd = dep[u] + d`这个深度的**点集**`dep[ nowd ]`中找一个$$v$$，使得
2）`v`满足$$\max(dp_v) - dp_u$$，也就是说使得$$dp_v$$最大
3）并且$$v \in$$`u 的子树`

> 那么，`v 在 u 的子树中`，这应该如何表示？

子树，一定是`dfs 序`中**连续的一段**，所以满足条件的`v`有一个范围，假设$$u$$的子树在`dfs`序中$$[l_u, r_u]$$
那么满足条件的$$v \in [le, ri] \subseteq [l_u, r_u]$$，这可以**二分查找 + ST 表求出答案**

> 这样我们就可以设计算法了

`dfs`的时候，对`dfs 序的编号`打表，记一下`dep(d) = { l(v1), l(v2), ...., l(vk) }`
`dfs`结束，算完`dp`值的时候，对每一个深度`d`，按`dfs 序编号 l(v)`从小到大排序
这样我们**建两个一一对应的表**
```bash
对某个深度 d
dfs 序编号表：
dep(d) = { l(v1), l(v2), ...., l(vk) }

对应的 dp 值的表，令 v1 = rm[ l(v1) ] （记得映射回原来的点）
depw(d) = { dp(v1), dp(v2), ..., dp(vk) }

对 dp 值建 ST 表
table(d) = { ST 表，维护 dp 值 }
```
这样我们就可以很愉快地查询了
对于询问$$u, d$$，只需要在`dep( d(u)+d )`中，`le = lower_bound(l(u)),  ri = upper_bound(r(u)) - 1`
然后在对应的ST表中查询，即在`table(d)`查询$$[le, ri]$$的区间最值，就是答案，复杂度$$O(n\log n)$$

## 关于 lower_bound 的一些问题

在处理序列问题的时候，经常需要用到 lower_bound，lower_bound 可以自定义比较函数
那么具体来说呢，有如下需要注意的点
```bash
lower_bound( [begin, end), key )
返回 [begin, end) 中第一个 >= key 的位置

upper_bound( [begin, end), key )
返回 [begin, end) 中第一个 > key 的位置

lower_bound( [begin, end), key, [=](elem, key) {...} )
返回 [begin, end) 中第一个使得 (elem, key) = false 的位置
注意 elem 参数要写在前面

upper_bound( [begin, end), key, [=](key, elem) {...} )
返回 [begin, end) 中第一个使得 (key, elem) = true 的位置
注意，这里我们要把 key 放在前面一个参数里
（可以死记硬背下来，up 就是提前，key 放在前面的参数中）
```

上一篇：杨氏矩阵（杨表）下一篇：积性函数，莫比乌斯反演（一）

看完文章有啥想法