20260901 每日 1.5 2.5 4.0

No.3141 Banlancing with X=>O Flip 1.5$

Note

给一个长度为 $N$ 括号序列 $S$，问能否通过大于等于 0 次下面操作，把 $S$ 变为合法括号串

将 $S$ 中子串包含的 )( 替换成 ()。

$1 \le N \le10^5$

可以观察到，题目中的操作实质上是类似冒泡排序的操作，总可以把左括号往左走，最终一定可以变成 N 个 ( 和 M 个 ) 的样子。

于是考虑如何让这个东西合法，显然充要条件是 $|(| = |)|$，直接 $O(N)$ 统计即可

int @n;
string @s;
ll cnt = 0;
rep(i, s.size()) {
	if(s[i] == '(') cnt ++; else cnt --;
}
if(!cnt) wt("Yes");
else wt("No");

No.844 split game 分割游戏 2.5$

https://yukicoder.me/problems/no/844

Note

有 $N$ 个 $1 \times 1$ 的方格横向一行，你可以选择一个坐标 $i$，然后在 $(i, i + 1)$ 方格之间划线，画一条线的收益是 $-A$，当两条线分割出一个区间的时候，如果其是给定的 $M$ 个区间 $[l_i, r_i]$ 中的一个，你将获得该区间对应的收益 $+p_i$。

你可以不断划线，问最大化收益。可以假定在 $i= 0$ 与 $i=N$ 处已经有两个线

$2 \le N\le 10^5, 1 \le M \le min(10^5, \frac{N(N+1)}{2})$

如果我们有上一次的选点 $j$，那么我们知道，当前选点 $i$ 如果断的话，就会产生 $[j + 1, i]$ 的那个收益，可以考虑 DP。

设 $dp[i]:=$ 最后一次断在 $i$ 的代价。

初始条件就是 $dp[0] = 0$。

如果上一次划线在 $j$，且 $[j + 1, i]$ 没有收益的话，那么 $dp[i] \ge dp[j] - A$，于是我们可以推出来转移:
$$
dp[i] = max_{j \lt i} dp[j] - A
$$
而如果 $[j + 1, i]$ 有收益的话，转移自然是：
$$
dp[i] = dp[j] + w(j + 1, i) - A
$$
这样就可以了，而式子 (1) 可以通过维护前缀最大来 $O(1)$ 查询。

记得特判 $i = N$ 的时候没有 $-A$ 代价。

using P = pair<int, ll>;
using VP = vector<P>;

int @n, @m; ll @a;
vector<VP> e(n + 1);
rep(m) {
	int @l, @r; ll @x;
	e[r].push_back({l, x}); 
} 

VLL f(n + 1, -ll_inf); // f_{i} := 最后一刀在 (i, i + 1) 之间的最大贡献
f[0] = 0;
ll mx = 0;
rep(i, 1, n + 1) {
	f[i] = mx - a;
	for(auto x : e[i]) {
		f[i] >?= f[x.first - 1] + x.second - (i == n ? 0 : a);
	}
	mx >?= f[i];
}
for(auto x : f) mx >?= x;
wt(mx);

No.2137 Stairs of Permutation 4.0$

https://yukicoder.me/problems/no/2137

Note

定义一个排列的分数 $f(P) := |\set{i:max(P_1,P_2,\ldots,P_i) = P_i}|$

给定排列长度 $N$，设所有长度为 $N$ 的排列的集合为 $S_N$ ，求 $\sum_{P\in S_N} f(P)^3$

$1 \le N \le 10^7$

首先先来考虑给定一个排列 $P$ 的情况下，如何求 $f(P)$？或者说，什么位置会给 $f(P)$ 产生贡献？

显然是每一个前缀最大值位置，换句话说，前缀最大值的种类数！

这里思考下一个问题：对于一个长度为 $N - 1$ 的排列 $P_{N-1}$，任意一个插入一个其中没有的数，请问插入什么数会让新的 $P_N$ 的 $f(P_N)$ 好计算？

试着考虑插入 $1$ 或 $N$ ？

显然是插入 $1$ 好计算，因为其不会影响 $f(P_{N-1})$，这个时候的新分数是显然不变的。

而这里我们知道，一个长度为 $N - 1$ 的排列，元素是 $[1,N-1]$，如果我们将其都 $+1$，之后插入 $1$，插入在什么位置才会让 $f += 1$ ？

肯定是首位置才会 $+1$。

这样其实可以考虑 DP 了！

定义 $dp[n][k] :=$ 长度为 $n$ 且 $f(P_{N}) = k$ 的排列个数

一个长度为 $N - 1$ 的排列，如果他的 $f = k$ 的话，插入 $1$ 之后：

插在最前面，新的 $f$ 是 $k + 1$
插在其他 $n - 1$ 个位置，$f$ 不变

那么我们可以写出状态转移：
$$
dp[n + 1][k] = dp[n][k - 1] + n \cdot dp[n][k]
$$
最终的答案其实可以写成：
$$
Ans = \sum_k k^3 \cdot dp[N][k]
$$
如果这里我们定义 $S^3(N) = Ans$ 的话，考虑其转移：
$$
S^3(N + 1) = \sum_k k^3 \cdot dp[N][k - 1] + N\sum_k k^3 \cdot dp[N][k]
$$
第二项刚好是 $N \cdot S^3(N)$，考虑第一项。

如果换元令 $j + 1 = k$ 的话，有：
$$
原式=\sum_j (j + 1)^3 dp[N][j] = \sum_j (j^3 + 3j^2 + 3j + 1) dp[N][j]
$$
如果我们定义 $S^t(N) = \sum_j j^t \cdot dp[N][j]$ 的话，其实可以把 $S^3(N + 1)$ 写出来对么：
$$
S^3(N + 1) = (N + 1)S^3(N) + 3S^2(N)+3S^1(N)+S^0(N)
$$
而我们想求 $S^3$ 就要求 $S^2$，其实分解的方式是等价的，最终就是：
$$
S^2(N + 1) = (N + 1) S^2(N) + 2S^1(N) + S^0(N)
$$
同样的 $S^1$ ：
$$
S^1(N + 1) = (N + 1)S^1(N) + S^0
$$
同样的 $S^0$：
$$
S^0(N + 1) = \sum_k dp[N][k - 1] + N \cdot S^0(N) = (N + 1) S^0(N)
$$
这样一来，我们就有了对应的四个递推式子！该考虑初始值了。

空排列的排列数有 $1$ 个，所以 $S^0(0) = 1$，而空排列没有贡献所以其余的 $S^t(0) = 0$。

于是就写完了！

#define MD 998244353
int @N;
Mint s3 = 0, s2 = 0, s1 = 0, s = 1;
rep(i, 1, N + 1) {
	s3 = i * s3 + 3 * s2 + 3 * s1 + s;
	s2 = i * s2 + 2 * s1 + s;
	s1 = i * s1 + s;
	s = i * s;
}
wt(s3);