2025年2月写的一些codeforces题（二）

[[ slider_text ]]

[[ item.c ]]

2025年2月写的一些codeforces题（二）

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

dp 树上问题 DSU on Tree

## DSU On Tree 和树分治的比较
### DSU On Tree 大致流程
![](/media/content_img/dsuontree01.png)

### 点分治大致流程
![](/media/content_img/ver-divide01.png)

## Educational Codeforces Round 132
### E
**[E. XOR Tree](https://codeforces.com/contest/1709/problem/E)**
给你一棵$$n$$个顶点的树，每个节点有一个权值，简单路径的权重，是路径上节点的权值`xor`和
如果一棵树，**不存在**权值为`0`的简单路径，就说树是好的
现在牛可以执行操作任意次，每次操作，任意选择树的顶点，用任意的正整数去替换顶点的权值
要使得树变成好树，最少要多少次这样的操作

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

**考虑用动态 DSU On Tree**
![](/media/content_img/EDU132E02.png)

## 牛客周赛 81
### E
**[建筑入门](https://ac.nowcoder.com/acm/contest/101921/E)**
给你一个数字三角形
```bash
   1
  2 3
 4 5 6
7 8 9 10
....
```
现在要你构造一个稳定的数字三角形，稳定的定义，就是说
一个数左下方和右下方两个位置的值，都比他**严格的大**，现在要求你构造一个稳定的三角形
使得第$$i$$行的数都是$$a_i$$，并且$$a_i$$严格递增，还要使得$$a$$的和恰好是$$k$$

**算法分析**
![](/media/content_img/nowcoder81E-1.png)
![](/media/content_img/nowcoder81E-2.png)

## Educational Codeforces Round 174
### C
**[C. Beautiful Sequence](https://codeforces.com/contest/2069/problem/C)**
定义一个序列是美丽的，当且仅当
1.它的长度是$$3$$
2.对于每一个元素，都能够在它左边找到一个比自身严格小的数
3.对于每一个元素，都能够在它右边找到一个比自身严格大的数
现在给你一个序列$$a$$，每个元素只能取`1, 2, 3`，问子序列中，是美丽序列的方案数

**算法分析**
不难发现，子序列要满足美丽的，当且仅当它形如`1 2 2 ...(若干个 2) ... 2 3`
首尾分别是`1, 3`，中间放$$k\geqslant 1$$个`2`，最暴力的想法，当然是枚举每个`1`
然后枚举这个`1`右边`3`的位置，看一下中间有几个`2`，比如说有`k`个

那么方案数就加上$$\displaystyle \binom{k}{1} + \binom{k}{2} + \cdots + \binom{k}{k} = 2^k - 1$$

这样做复杂度不对，考虑优化，用**动态规划**
这个问题，相当于类似**找上升子序列 LIS 的方案数**
定义`dp(x)`，表示当前满足条件的子序列，**以 x 结尾的方案数**，转移考虑每个位置选还是不选
```bash
初始时候，一个都不选，dp[0] = 1

if a[i] = 1:
	不选，dp[1] = last[1] (当前是 1 结尾，上个状态也必须以 1 结尾)
	选，dp[1] += last[0]，因为不允许连续的 1，所以上个状态必须以 0 结尾
	
if a[i] = 2:
	不选，dp[2] = last[2]
	选，dp[2] += last[1] + last[2]，可以有连续的 2，也可以接在 1 后面
	
if a[i] = 3:
	不选，dp[3] = last[3]
	选，dp[3] += last[2]，不能有连续的 3，只能接在 2 后面
```

## CodeTON Round 9
### E
**[E. Shohag Loves Inversions](https://codeforces.com/contest/2039/problem/E)**
给你一个序列`a`，一开始`a = [0, 1]`，令$$k$$表示`a`中逆序对的个数，你可以如下操作若干次
将`k`插入`a`中的任何一个位置，现在问，当序列长度是`n`的时候，能够得到几种不同的序列？
输出方案数

**算法分析**
![](/media/content_img/codeton9-e1.png)
![](/media/content_img/codeton9-e2.png)
![](/media/content_img/codeton9-e3.png)
![](/media/content_img/codeton9-e4.png)

上一篇：2025年2月写的一些codeforces题下一篇：Catalan 数

看完文章有啥想法