lzx 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-05 16:43:56
还算是正常发挥。
开场一看，前4题貌似都见过，遂掉以轻心。
先看 T1，试图推 dp 式子，发现不太行，花了 30min，未果。
于是看 T2，发现暂时也不会，发现与最短的长为奇数和偶数的路径长有关，但不会算，遂开 T3，发现 T3 前两天写过，只需要统计一下每个点的答案，然后加一下就行，然后全挂了。
这时心态已经有点崩了。
然后发现没有累加答案，而且没有还原贡献，赶紧改完，过了。
回去看 T1，发现只需要这一天买回来，第二天再卖出去即可，10min 内写完。
再看 T2，发现分层图就搞定了，完事。
发现每行只选一个，考虑容斥。
快速写完，发现假了，因为统计不合法方案时忘了限制每行只选一个了。
然后又想 dp，过了 84。
然后考虑只关心两者之间的差值，遂 100pts。
想写暴力，但是时间太短没写完.
要合理安排时间。
要稳住心态。
要加强对于简单模型的转化应用。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-28 17:30:43
第一场，感觉不太清醒，已经深刻认识到错误。（耳刮子已经打了）
咋是交互题，之前没做过。 花了 10min 看懂了题面，就是要花尽量少的次数得到权值和，然后只需要交一个函数就行。
很快想到了 $2nh$ 次询问，每个点询问 $h$ 次，加起来 /(n-1) 就行。
然后就卡住了，想到 9：50，不会了，开 T2,3。
等到 11:20 回来再看，发现如果每个点访问 $1$，那么根被加了两次，叶子加了一次，剩下的点加了三次，只需要把根找出来，减减加加就行。很快写完，预计 62pts。
又不会了，一直没有很好的消去贡献，但是感觉和正解很接近。
赛后讲题，发现就是如何凑贡献的问题，可以找出前两层的点，然后算出根的权值来，然后加一加就行了。
但是提交上的代码 CE 了，原因是我定义的 solve 函数是 solve(long long,long long)，但是应该是 solve(int,int)，然后就挂了。
一开始以为是 2-SAT，但是发现并不是，2-SAT 只能做判定和构造解。然后会了最低档的暴力，但是此时脑子已经不清醒了，试图研究特殊性质，但是并没有进展。
赛后讲题，就是从特殊性质入手。然后就是看成一堆区间，答案要么是一堆有交的 $a\lt b$，或者是一个 $a\gt b$ 和包含的他的一堆 $a\lt b$，线段树很好维护。
暴力又挂了，原因是左移右移数错位了。
只会阶乘暴力，想到了 dp，但是并没有很好的设出状态，推出式子。
赛后讲题，发现可以设 $f_{u,i}$，表示说 $u$ 子树内进出了 $i$ 次，转移是容易的。但是优化没听懂，掉线了。
几个问题：
1.在 T1 上花费了过多时间，且因为低级错误 CE，在本地 CE，爆出 undefine 的时候就应该意识到函数写错了，但是我以为是交互库的锅，把函数粘到了 grader 里，实现了自测。赛后看这是很可笑的。
2.在意识到题目可能过难时，我没有很好的稳住心态，脑子成了浆糊，导致 T2,3 应有的部分分没有拿到。
3.dp 太弱，设状态，推式子的能力都不足，应该加强训练。
4.对于简单的部分分实现，出现了掉以轻心的情况，犯了弱智错误。
5.策略出现了失误，比赛节奏被打乱。
6.体力，脑力都出现了掉线的情况。
感觉状态比前一天好多了。
这个一眼就很数位 dp，然后想，然后发现可以只关心每个数填了多少，感觉状态数不多，发现 $10^{10}$ 只有几万个，然后开写，但是写完发现没有暴力跑得快，$10^6$ 跑了 5s，心态有点崩。冷静算一下，复杂度太高，不太能接受。
一直在想如何优化状态，猜想是不是不关心具体每个数出现了多少次，而是像之前某个题一样只关心出现 $i$ 次的有多少，但是在这种情况下不会处理顶上界的情况。
此时已经九点多了，dp 没有进展，遂打暴力。发现 $r$ 为 $10$ 的若干次幂是容易的，可以爆搜/打表。于是打出了 $10^{18}$ 以内的。然后发现 $10^8$ 以内的可以用分块打表，很快写完。有点不太放心，因为文件大小来到了 95KB。
先去看后面的题。
后面再看，没太有进展。
出成绩，文件过长，表炸了。评测的时候老师的评测机开到 50KB，开到 100KB 重测后没有挂分。
想了一会，只会阶乘暴力。
然后发现要转化成一个排列，之后 dp，但是我不会了，没能想出来暴力 dp。
赛后讲题，发现要注意到先将 $a$ 数组排序，然后注意到最后一个未匹配的 B 类点之前的 A 类点都要匹配，之后的 B 类点都要匹配，基于此可以前后 dp，然后拼起来。和之前讲的某个题是一类套路。
读懂题了，感觉要挖掘一些性质。
研究了一会，发现 DAG 肯定 A 赢，推广一下，后续没有环的一定也不行。
然后就不会了。
赛后讲题，发现还要发现一些性质。
首先删掉只能有限次操作的点。
如果一个点只有一条出边，那么它只能到后面那个点，所以可以合并两个点。
启发式合并一下。
需要惊人的注意力。
好的方面是没有出现前一天的重大失误，比赛节奏策略也逐渐适应。
不好的方面是暴力分依旧没有拿满，回去要摆正好心态，好好练 dp 了。
状态回来一点了，但是还是有失误。
一看是异或，感觉和前两天 NOIP 模拟赛的 B 很像，因此直接设 $f_{i,j}$ 表示考虑了前 $j$ 位，数字为 $i$ 的代价。写完发现，大样例要跑 5s，回去看看，原来是复杂度算假了。最坏情况下他每次都要更新 $2^m$ 个点，T 飞了。
赶紧看看怎么修，但是到 9:30 没想出来，写了个 $c\le 3$ 跑了。
后面回来再看，没有发现什么好的性质。
赛后讲题，不用记位数，只需要每次暴力访问 $m$ 个可能更新到的点，暴力 bfs 更新，由于每个数最多被更新 $m$ 次，所以复杂度是对的。
没做出来，有点不应该。
2 min 读懂题，暴力模拟就能过第一个 sub。可以倒序考虑每次和哪个位置交换，但是复杂度好像不对，就没写（实际上是可以过 sub2 的）。继续想，没想出来。
讲题，咋是数学题。把开始的 $x$ 看成矩阵，异或就是广义矩阵乘。把每次的乘的矩阵命名为 $A$。因为倒序考虑，所以 $xA^i \bmod i$ 的结果我是知道的，先只考虑 $2^k$，那我就知道了结果的底 $i$ 位。由于 $x$ 的每一位都是原来的一些位的线性组合，所以我们就得到了 $i$ 个方程。但是方程数有点少，考虑多用一点。我们知道了 $\bmod i$ 的余数，我们就知道了 $\bmod$ $i$ 的因数的余数，所以我们就知道了 $\bmod$ $\operatorname{lowbit} i$ 的余数，那我们知道了更多方程，自由的位数就更少了。
3min 读懂题，实际上就是要有一个排列满足第 $i$ 行第 $p_i$ 列为 $1$ 的概率。
首先想到暴力全排列，然后想到，这个东西可以 dp，每次枚举出来每位是 0/1，$f_{i,s}$ 表示前 $i$ 行，选了 $ s$ 中的列，能不能选出来的全是 $1$，转移是容易的。
然后又不会了。
$n\le 7$ 的做法是考虑不枚举，dp 套 dp，然后说有效状态数不多，可以通过。
$n\le 9$ 要用 Hall 定理，没听懂。
好的方面：
暴力拿满了，思考也比较充分，没有出现低级失误，能像一个正常人类一样想题了。
问题:
对于基础的算法应用转化理解不透彻，把简单问题复杂化了，掌握不完全。
第一眼以为是 2-SAT，然后发现不能处理 $l,r$ 的限制，于是果断放弃（2-SAT 学魔怔了），然后想别的做法，然后想到可以把 $m$ 条限制看成边，一个连通块内确定了一个点就确定了一整个连通块，所以可以枚举编号最小的点，有 25pts。然后就卡住了，想了一会，没有进展，想特殊性质也没想出来，心态有点崩果断弃题。
赛后得知可以用 trie 维护编号最小的点的可行区间，长知识了。
第一眼没读懂题，再读一遍，手模一下样例，懂了。注意到 $n\le 200$ 可以暴力跑出来，然后去想特殊性质。
想了一会，发现 AB 性质就是保证永远不会出现 his，A 性质保证只有一开始会有 his，只需要维护一下开始的 he，两种一起跑一下，有 35pts。
继续特殊性质，注意到 his 很麻烦，可能是解题关键。如果任意时刻都没有超过三个 he，说明只有最开始几个串有 his，所以可以暴力跑出前 $6$ 个，然后和前面一样做。
再看，感觉 D 性质没有什么用。发现只有 hihi...his 和 hihihi...he 是难处理的，但是不太会处理。
赛后讲题，得知可以维护一下每个字符什么时候变，每个间隔什么时候插入即可。
一看就是性质题，但是推了 30min 没推出来，果断放弃。
正解及其 Ad-hoc 要先给他推到一条线上，然后再做类似数位 dp。掉线了。
还是要稳定好心态，要打好暴力分。
要加强对于数据结构的应用，要加强自己的代码能力。
终于过题了\ll\ll。
先看 T1，一下子会了 $n^2$，有 50pts。然后有点卡住，先去想链，发现可以直接线段树做，那么 $2\times 10^5$j加上特殊性质就有 86pts，时间还早，有充分时间在想一会。
发现问题其实是维护路径信息，那么能不能把询问离线下来，挂到 lca 上一块做。先想了 dsu on tree，发现不太行。又想点分治，可以把询问挂到点分树的 lca 上，然后暴力 dp 一下，就做完了。复杂度 $O(nk^2\log n+qk)$，有点卡常不过问题不大，开了 3s，先看看后面的题，没读懂，先不管了，开写。9：20 写完，大样例挂了，有点慌，一看 dp 式子假了，更慌了。
先上个厕所冷静一下，没事，能修。10：20 写+调完，发现大样例要跑 3.8s，空间要用 400MB 以上，有点危险，关掉 long long，应该没啥问题了。
写完 T1，再重新读一下题，会了 20pts 暴力，先写。写完发现卡住了，想一会到 11:00，没有进展，果断弃题。
讲题掉线了。
没读懂题，再读一遍，没看懂他给了 $f$ 数组，为啥还要给 fa 函数，有点迷。而且一点思路都没有，弃了。
赛后讲题，原来 50 的部分分（fa 函数）是为了能把两个数组都自己用（因为空间卡的很死，不能再开数组），还要借助链式前向星的思想，用 head 和 nxt 实现以下，很巧妙，有点人类智慧。
要大胆冲一些自己有把握的分
要通读所有题。
要增强码力，减少调试时间。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-01 19:45:10
一眼 dp，$f_{i,0/1}$ 表示到第 $i$ 个点，第 $i$ 个点选/不选环上,转移是容易的。
赛后咋挂成 $9$ 了，完了。原来是第一遍 dp 应该不选，写成选了。该罚。
一开始想的是线段树上维护每一块肉，然后选，发现不太好做。
想离线，找每块肉被那个人选走，发现直接把每个线段搞到端点上，维护下区间最小值，表示被那个人选走，直接就做完了。然后就做完了。
一眼会了 $O(n^3)$。然后想考虑每次插入算贡献，但是不会做。想了大约 1h，果断写暴力。
正解是要注意到选的点一定是连续的单调字段的端点，然后就可以算贡献了。
$O(n^2)$ 暴力显然是容易的，果断写暴力。
正解要注意到有一些点是必须选的，然后处理一下就行。
会了暴力和字符集只有 {a,b}，然后注意到为了连续一定要是形如一段 a，一段 b，一段 c...
然后又不会了。
正解是先把所有的退成 a 然后每次将一个后缀变大，然后有线段树维护一下贡献就行了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 08:23:01
给你 $n$ 和 $n$ 的一个排列，$\forall 1\le i\le n$ 求出排列的所有区间里，由大小不超过 $i$ 的数构成的最长的“之字形”子序列的长度之和是多少。
其中，一个长为 $k$ 的序列是“之字形”序列，当且仅当对于所有满足 $1\le i \le k-2$ 的 $i$，满足以下条件之一：
$n\le 2\times 10^5$。
首先，我们可以想到，枚举限制（最大值），然后 dp 求出每个区间中不超过最大值的数所构成的最长的之字形子序列的长度是多少。枚举最大值是 $O(n)$ 的，枚举区间，做 dp 可以一起，总复杂度 $O(n^3)$。不能接受，但是可以过 40 分。
我们可以观察到，如果我们需要做 dp，那么一次至少需要 $O(n)$ 的复杂度，难以优化，所以我们需要考虑能否在不 dp 的情况下求出满足要求的子序列的长度。
我们发现，对于某一个区间来说，如果它是单调的，那么只有区间的两个端点对于答案是有贡献的，中间的不影响答案。由于整个序列就是由若干个极长的单调区间组成的，所以我们发现，我们可以将贡献拆到每个数上去，一个数只有在区间中作为开头、结尾或者是一个“转折点”（两边都比他大或者两边都比他小）时才会有贡献，我们可以对于几种情况分类讨论。
我们发现，每个数贡献到的区间数就是它的贡献。
考虑固定最大值（也就是说有一些位置可能为空，以下的 $i$，$l$，$r$ 均不是空位置）。我们令当前的位置为 $i$，它左边的位置为 $l$，右边的位置为 $r$，那么有以下讨论：
于是我们就可以从小到大加入每个数，计算新加入的贡献，重算左右两边的贡献，其他的不用管（因为 $l$，$r$ 没有变）。可以用 set 维护已经加入的点，复杂度 $O(n \log n)$，可以通过。
#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
int p[N];
int ans;
set<int> st;
void upd(int pos,int x)
{
int l=-1,r=-1,sum=0;
auto it=st.lower_bound(pos);
it++;
if(it!=st.end()) r=*it;
it--;
if(it!=st.begin()) it--,l=*it;
if(l==-1||r==-1) sum+=pos*(n-pos+1);
else
{
sum+=(pos-l)*(r-pos);
sum+=(pos-l)*(n-r+1);
sum+=(r-pos)*l;
if((a[l]<a[pos])==(a[r]<a[pos])) sum+=l*(n-r+1);
}
ans+=x*sum;
}
void ins(int pos)
{
int l=-1,r=-1;
auto it=st.lower_bound(pos);
if(it!=st.end()) upd(*it,-1),r=*it;
if(it!=st.begin()) it--,upd(*it,-1),l=*it;
st.insert(pos);
upd(pos,1);
if(l!=-1) upd(l,1);
if(r!=-1) upd(r,1);
}
signed main()
{
\/\/freopen(".in","r",stdin);
\/\/freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],p[a[i]]=i;
for(int i=1;i<=n;i++)
{
ins(p[i]);
cout<<ans<<endl;
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-17 10:13:32
首先，我们可以想到，将 $i$ 向 $a_i$ 连边，表示球 $i$ 在盒子 $a_i$ 中。
这样我们就得到了一棵基环内向树。
我们考虑每次对盒子 $i$ 操作在干什么。
其实就是把所有连向 $i$ 的点拿出来，按任意顺序连成一个环。
但是我们考虑，每次连成环的过程中，我们无法得知应该按怎样的顺序去排列环，而且我们并不知道这张图的初始状态是怎样的，所以我们考虑倒着操作。
考虑将 $i$ 从 $n$ 到 $1$ 枚举的过程中，每次如何变化这张图。
实际上就是每次把一个环全部断开，然后全都连到 $i$ 上。
但是这样做是有问题的。
我们在正着做的时候，由于我们每次拿出了所有连向 $i$ 的点，所以每次对于 $i$ 操作完，点 $i$ 一定要么入度为 $0$，要么处在某一个环上，且除了环上的点没有点连向他，这就限制了我们每次操作 $i$ 的时候，必须保证当前图满足操作后的条件。
那么可以想到，如果我们在操作过程中发现当前的 $i$ 不合法，那么肯定就无解了。
那么我们每次应该操作哪个环才能最优呢？
我们考虑每次断开的环如果不在当前连通块，那么每个点的可操作性是不变的（可以自己画一画）；如果在当前连通块，那么我们发现，原来可操作的还能操作，如果当前点入度为 $0$，原来一些在当前点到环的路径上的点，可能从不能操作变为可操作，所以证明，我们每次操作当前连通块内的环一定是最优的。
所以我们可以暴力扫，每次找到当前环，然后暴力更改。
这样做乍一看是 $O(n^2)$ 的，实际上可以分析到 $O(n\sqrt n)$，可以均摊。
我们令环长为 $L$，每次的花费实际上就是 $O(L)$ 的。（可能还会多一点环之前的链，但是由于操作一次后链就变成环了，所以我们认为这还是环）。
总花费是 $O(\sum L)$ 的。
设 $S$ 为当前图上每个点的入度的平方和，显然，$S\le n^2$。
我们考虑操作一次后，$S$ 是如何变化的，对于原来在环上的点，它们的入度 $-1$；对于 $i$，他的入度 $+L$。
我们令 $ind_i$ 表示 $i$ 节点的入度，那么 $S$ 的变化就是 $(ind_{i}+L)^2+\sum_{\text{x on ring}} (ind_x-1)^2-ind_i^2-\sum_{\text{x on ring}} ind_x^2=L^2+2\times ind_i\times L-\sum_{\text{x on ring}} 2\times ind_x+1$。
所以 $S$ 的变化每次是 $O(L^2)-O(n)$ 的。
要变化 $n$ 次，那么 $\sum L^2$ 最多是 $O(n\sqrt n)$ 级别的。
实际上跑的飞快。
更详细的证明可以看这里。
提交记录。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-03 16:06:57
省流：100+100+eps+eps，寄麻了，去不了 WC 了。
更一手：100+80+30+16 /ll
一直在 lca，感觉会了很多东西，也是信心满满了。
但是猎奇的周二休息是真的难绷。
lca 赛前加长周，还有 ICPC 赛制娱乐赛，巴结到 chb 大手子了，被带飞了。但是模拟赛一直在寄，一直在安慰自己在攒 rp。
途中得知由于酒店原因我们都换成大床房了，省去了找室友环节。
原本定的是 27 号学校要体测，然后 Pigsyy 没来，但是又改成 28 号了，没逃过，比较难绷。
星期三还有保留的赛前动员环节，早早回到小机房，但是快开始了才下去，然后只剩下第一排了，被迫坐在第一排。
感觉布置的很温馨啊，赢。
由于 zms 要回初中体测，不能出席，所以 Dtw 用电脑放出了他的照片摆在座位上，大体是这样的，比较难绷。
还有 lxn 讲话环节，然后经典 deepseek 发言稿，还有 I don't care 环节。
经典切蛋糕环节，Iceturky 先发制人把奶油抹到 Pigsyy 脸上，然后教室里就不受控制了，本人单杀了 KSCD_ 和 Iceturky，这个环节比较好玩。
给 typ（班主任） 送蛋糕，但是不在，于是我们一人顺了他一块喜糖。
摆疯了。
爽睡失败，8：20 到达机房，然后发现只有 quyuan 在。
lxn 提醒要学一下 Manacher，然后学会了。
之后 KSCD_ 来了，被裹挟着打了一点板子。经典点双，然后调不出来了，FiraCode 和 xya 去打球了，立下 flag 说调出来就去，然后正好错过，找了一圈没找到，没打上球。
吃完午饭上车，睡了半路，然后到达酒店办入住。
结果等到最后，前台说我的房间还没有打扫出来，随去投奔 KSCD_。发现他的房间是亲子房，有一个用沙发拼的小床，还有卡哇伊的毯子和一个巨大的玩偶，有点厉害。
被裹挟打板子，快吃饭的时候俩人决定竞速树剖板子，然后都调不出来了，然后被 zibenlun 打电话催着下楼拍照了，成为了最后到的两个人。
饭后回到自己房间，感觉一个人睡大床比较爽啊，然后酒店的配置也比较高级，赢。
Iceturky 和家长住一起，然后房间里有一个滑梯，Iceturky 还给拍了第一视角滑滑梯的视频，结果差点飞出去，难绷。
去试机，和 KSCD_ 一起，结果谁也不认识，无法面基，寄麻了。
今年居然有试机题目，还是去年 NOIP，尝试 edit，然后发现过于难写了，所以弃了。键盘感觉比 wfyz 的好用，赢。
回去的路上 lxn 说今天打游戏的绝对考不好，还有毒奶环节，绷。
回去发了朋友圈，然后一车人点赞，感动。
爽睡成功，赢。
去吃早饭，以为自己是最晚的，然后发现 KSCD_ 和 Iceturky 先后到餐厅，比我还晚。
lxn 在群里发让起床的回个信，我说等会房间在回，然后 quyuan 说不用回了，回头发现 lxn 就在后面。
回房打了一点点板子，然后摆一摆，就去吃饭了。
收拾好东西一直比较亢奋，没睡着，但是也不困，还好。
进场后一直在试机，跟前一天晚上一样，感觉没那么紧张了。
人杰地灵。
顺开，T1 不知道是贪心还是 dp，T2 是 MST 状物，先看 T1。
想了若干分钟，然后又看了一眼特殊性质，发现只有在不合法的之后才会调整，调整完不会不合法，直接反悔就行了，糖丸了。
调了一会，过了，然后看 T2，发现 $k$ 只有 $10$，可以 $2^k$ 枚举，然后原图的边显然只有 MST 上的有用，然后开写，发现读错题了，$k$ 个乡镇是单独的，不是原图上的点，不过无伤大雅。
发现 $2^k$ 次 MST 好像不可接受，有点寄。发现边可以归并，能省掉 $\log$，开写，大约 16：20 过掉大样例。
之后看了一会 T3，场上感觉是 hash 和一些神奇数据结构，不太擅长，于是看 T4，胡了一车特殊性质，然后想不下去了，17：00 左右开写，然后发现挂了，有点急，去厕所冷静一下，猛猛喝水，吃块士力架。
到了 17:50 没调出来，有点崩，先去写 T3 最低档暴力，过了小样例就扔一边了。又去写 T4 阶乘暴力，又挂了，寄麻了，到结束也没调出来。
出来发现 KSCD_ 和 cybrex 也打炸了，FiraCode 打的不错，车上冷静了一下，回家睡觉。
你说这个成绩不可接受吗，其实也不是，就是感觉很遗憾，没有把能拿到的分都拿到，有点可惜。
还是功夫不到家，调试代码的能力太弱，浪费了过多时间，心态到后期也崩了，所以菜就多练。
还有一个月，NOIP 加油吧，CSP 就当成 NOIP 模拟赛了。
长风破浪会有时，直挂云帆济沧海。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-11 20:40:50
顾名思义，分步转移是一种类似人走路一样的一步一步转移的方式。
分步转移常常用于有多个维度的 dp 转移，它可以将多个维度一起转移转化为一个维度一个维度的转移，从而降低转移的复杂度。
dp 的几个维度之间可能有关联，但是不能影响到权值的计算，我们称之为“弱关联”。
例如，对于二维的状态 $(a,b)\to (a',b')$，dp 的转移中有形如 $w(a',b')$ 的权值，那么分步之后不会影响我们的权值计算，依然可以采用分步转移进行优化。
如果 dp 的权值依赖于上一个状态，有多维状态之间的联系，那么就不能用分步转移的方式。
举个例子，对于二维的状态 $(a,b)\to (a',b')$，如果转移中包含形如 $w(a',b)$ 或者 $w(a,b')$ 的值，就不适用于分步转移，因为分步之后无法计算新的权值。
干讲可能有些抽象，有几个例子可以让大家辅助理解。
简要题意：在树上选两条路径，使他们的点权和最大。
直接做显然是困难的。
一条路径 $u\to v$ 显然可以分成 $u\to \operatorname{lca}$ 和 $v\to \operatorname{lca}$ 两部分。
我们考虑如果是选一条路径，那么我们就是直接选直径，我们在选直径的时候是如何考虑的呢？
就是直接在子树内选最长和次长链，然后尝试拼起来。
所以我们可以考虑模仿这个过程，设 $f_{u,0/1/2/3}$ 分别表示在 $u$ 节点的子树内，目前分别选了一条不完整的链（即可以向上继续延伸）、一条完整的链（不能向上）、一条完整的和一条不完整的链、两条完整的链的最大权值。
转移的话就是考虑将不同的情况拼在一起，需要自己推一推，有一些细节，但是总体难度不高。
这道题就是把选路径的过程拆分成了多种情况，然后一步一步的补全两条链，从而实现转移，体现了拆分分步的思想。
P12738 [POI 2016 R2] 口吃 Stutter - 洛谷
简要题意：你有两个序列 $\{a_i\}$ 和 $\{b_i\}$，你要选出两个序列的最长的满足以下要求的子序列：
空间限制 32 MB。
首先，对于一个 $a_i$，它如果要计入子序列中，一定是与前面或者后面的离他最近的进行匹配，放到子序列相邻的位置上，否则一定不优，对于 $b_i$ 同理。
显然，我们有暴力 dp 的做法。
我们可以直接设 $f_{i,j}$ 表示 $\{a_i\}$ 用前 $i$ 个数，$\{b_i\}$ 用前 $j$ 个数的最长长度。
转移是容易的，直接效仿求 LCS 的 dp 转移即可，设 $nxta_i$ 表示序列 $a$ 中 $i$ 后面第一个与它相等的数的位置，$nxtb_i$ 的定义类似。
转移就是 $f_{i,j}\to f_{i+1,j}$，$f_{i,j}\to f_{i,j+1}$，$(f_{i,j}+2)\times [a_{i+1}=b_{j+1}]\to f_{nxta_{i+1},nxtb_{j+1}}$。
但是此时空间复杂度为 $O(n^2)$，难以接受。
一个显然的想法是将枚举的时候将第一位压掉，但是很有问题啊，我们丢失了一维信息之后，我们转移没法转了。
由于我们扩展出来的子序列与原来选的没有关系，只与 $a_{i+1}$ 与 $b_{j+1}$ 是否相等有关系，所以我们考虑分步转移。
设 $f_{i,j,0/1/2/3}$ 分别表示 $\{a_i\}$ 用前 $i$ 个数，$\{b_i\}$ 用前 $j$ 个数，现在应该转移下一对数中 $a$ 中的第一个数、$b$ 中的第一个数、 $a$ 中的第二个数、$b$ 中的第二个数的最长长度，然后要求 $1、2、3$ 状态满足 $a_i/b_j$ 必须是最后一个选的数（为了满足转移的要求）。
$f_{i,j,0} \to f_{i+1,j,0}$，$f_{i,j,0}\to f_{i,j+1,0}$，$f_{i,j,0}+1 \to f_{k,j,1}$，$f_{i,j,1} \times[a_i=b_k] \to f_{i,k,2}$，$f_{i,j,2}\times[a_k=b_j] \to f_{k,j,3}$，$f_{i,j,3}\times[a_i=b_k] \to f_{i,k,0}$。
显然转移和上面差不多，每次枚举到在另一个序列上相等的就转移，答案就是所有 $0$ 状态的最大值。
现在我们再对新的状态压掉第一维，我们发现不会出问题了，因为我们省去了对于 $nxt$ 的转移。
时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，常数有点大。
所以由此可见，通过分步转移的方式，我们拆分的原有的 dp 状态，可以优化一部分题目的时间。
P7648 [COCI 2012/2013 #5] MNOGOMET - 洛谷
题意过于复杂，不在赘述。
我们发现，如果直接 dp 记录时间，人，比分，队伍等信息，会让复杂度变的非常高，不可接受。
我们现在考虑发掘一点点性质。
由于每次射门后，球都回到自己队伍的 $1$ 号队员手中，所以我们可以把每一次射门看作一步，每次射门之间都是独立的情况。
我们将球的可传导关系刻画到图 $G$ 上。
设 $g_{0/1,t,i}$ 表示说，求球最开始在某个队伍的 $1$ 号队员手中，经过 $t$ 时间后，到 $i$ 号球员手中的概率。
$g_{0/1,t,u} \times [(u,v)\in G]\to g_{0/1,t+1,v}$。（箭头只表示转移关系）
然后设 $w_{0/1,0/1,t}$ 表示球开始在某个队手上，$t$ 秒后在某个队手上，射门后球进了的概率，$l_{0/1,0/1,t}$ 表示球开始在某个队手上，$t$ 秒后在某个队手上，射门后球没进的概率。
这个是好算的，直接枚举每个人，用 $g$ 算出来即可。
设 $f_{t,i,j,0/1}$ 表示经过 $t$ 秒，比分为 $i:j$ ，球现在在某个队的 $1$ 号选手的手上的概率。
这个直接枚举经过的时间，也是好转移的。
$f_{t,i,j,0}\times w_{0,0,t'-t} \to f_{t',i+1,j,0}$，$f_{t,i,j,0}\times w_{0,1,t'-t} \to f_{t',i,j+1,1}$。
$f_{t,i,j,1}\times w_{1,0,t'-t} \to f_{t',i+1,j,0}$，$f_{t,i,j,1}\times w_{1,1,t'-t} \to f_{t',i,j+1,1}$。
$f_{t,i,j,0}\times l_{0,0,t'-t} \to f_{t',i,j,0}$，$f_{t,i,j,0}\times l_{0,1,t'-t} \to f_{t',i,j,1}$。
$f_{t,i,j,1}\times l_{1,0,t'-t} \to f_{t',i,j,0}$，$f_{t,i,j,1}\times l_{1,1,t'-t} \to f_{t',i,j,1}$。
但是还有问题，我们的问题是求出每一粒进球后比赛结束的概率。
如果某个状态之后还有射门，那我们不用管。
现在的问题是，如果某一次射门之后没有射门了？
我们再设 $q_{0/1,t}$ 表示开始球在某个队手中，经过 $t$ 秒都没有射门的概率。
$q_{0/1,t}=\sum_u g_{0/1,t,u}$。
时间复杂度 $O(T^2n^2)$。
所以我们用分步转移的方式降低了时间复杂度。
参考了题解：https://www.luogu.com.cn/article/82old07u 的思路。
分步转移是一种 dp 状态的设计方式，通过拆分或合并转移中本质相同的过程或状态，可以降低复杂度，达到我们的目的。
其核心思想是，要发掘 dp 状态和转移本身的性质，找出正确的分步方式，合并一些本质相同的状态或过程，抑或是将一个过程拆分成多步来达到简化转移的目的，设计出正确的状态。
作为一种小 trick，可以降低一些思考的难度，也有一些例题和应用。
部分参考了文章：https://www.cnblogs.com/A-Quark/p/16448270.html 和 https://www.cnblogs.com/cqbzlym/p/18996536 的例题及表述，在此表示感谢。
参考了题解：https://www.luogu.com.cn/article/82old07u 的思路，在此表示感谢。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-18 17:00:44
做这题的时候读错了好几次题，生气了。
首先，由于我们只关心位置数组的贡献和，位置数组之间的排列顺序我们是不关心的，所以我们将拍到桶里，设 $cnt_i$ 表示位置 $i$ 在原位置数组里的出现次数，不难发现，$cnt$ 与原位置数组是一一对应的。
然后我们可以发现，由于每一次移动的时候，表现为所有人向某一个位置集中，所以有人的位置一定是一个区间，表现在 $cnt$ 上就是我们的非零的 $cnt_i$ 的 $i$ 一定形成了一个区间，我们将这个区间称为 $[L,R]$。
我们通过手玩一下可以发现，每个一组 $cnt_i$ 除了在区间端点上的，其他的都是奇数。为啥呢？我们考虑每次移动过程在 $cnt$ 数组上的表现，要么是整体移动，要么是把相邻的两个（在端点上）或三个合并起来，那合并后不在端点上的原来也一定不在，所以如果合并前满足限制，那么合并后也满足。由于最开始的时候 $cnt$ 数组全是 $1$，所以我们的限制是对的。
那么满足了这些要求的一定合法吗？
我们可以由最开始的数组进行考虑，从 $cnt_L$ 开始从左往右一个一个的合并，一定能合并出当前的 $[L,R]$ 内的每一个数，然后再对它进行位置的偏移即可。
现在我们得到了一些关于 $cnt$ 的性质，可以对他进行计数了。
虽然我们最终求的是所有位置数组的权值和，但是我们考虑，我们可以将所有去掉非零部分后一样的 $cnt$ 数组一块考虑，因为它只有权值不一样。
端点处的奇偶性我们可以分类讨论，引入 $x$ 和 $y$，他们的取值都是 $1$ 或 $2$，令 $cnt_L=2g_L+x,cnt_R=2g_R+y$，其中 $g_L$ 和 $g_R$ 都是非负整数，这样，我们就成功表示出了端点处的值。我们如法炮制，$\forall i \in (L,R)$ 的整数 $i$，令 $cnt_i=2g_i+1$。
所以我们可以对于 $g$ 进行计数，那么在去掉 $x,y$ 和给每个位置分配的 $1$ 之后，我们还剩下 $tot=n-x-y-R+L-1$ 的和需要分配给 $[L,R]$ 中的每一个位置，显然 $tot$ 要是偶数，至于分配的话就是 $tot$ 除以 $2$ 然后隔板法。
然后来处理权值和的部分。我们令区间长度为 $len$，由于我们是隔板法分配，所以每个区间内的每一个位置被分配的权值的期望都是 $\frac{tot}{len}+1$（端点处需要注意单独处理，因为是偶数时会多 $1$），所以每个位置在每一种方案中的 $cnt_i$ 的和是可以结合上面的部分算出来的。再考虑原序列的权值，那我们现在缺的就是 $a$ 序列中所有长为 $len$ 的区间的区间和之和。即为 $\sum_{1\le L\le n-len+1} \sum _{len\le R \le n} a_i$。
这个东西很很可以前缀和啊，我们推一推式子。令 $sum_i$ 表示 $a_i$ 的前缀和。 $$\sum_{1\le L\le n-len+1} \sum_{len\le R \le n} a_i=\sum_{len\le R \le n} sum_R-\sum_{1\le L\le n-len+1}sum_{L-1}$$ 于是我们对 $sum_i$ 再做一次前缀和就行了。
终于做完了。
::::info[Code]
#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
const int p=998244353;
int fpm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p,b>>=1;
}
return res;
}
int fac[N<<1],inv[N<<1];
void init()
{
fac[0]=inv[0]=1;
for(int i=1;i<=4e5;i++) fac[i]=fac[i-1]*i%p,inv[i]=fpm(fac[i],p-2);
}
int C(int n,int m)
{
if(n<m) return 0;
return fac[n]*inv[m]%p*inv[n-m]%p;
}
int mod(int x)
{
while(x>=p) x-=p;
while(x<0) x+=p;
return x;
}
void add(int &x,int y)
{
x=x+y;
while(x>=p) x-=p;
while(x<0) x+=p;
}
int T;
int n,a[N],s[N];
void solve()
{
int ans=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],add(ans,n*a[i]%p),add(a[i],a[i-1]);
for(int i=1;i<=n;i++) s[i]=mod(s[i-1]+a[i]);
for(int len=2;len<=n;len++)
{
for(int x=1;x<=2;x++) for(int y=1;y<=2;y++)
{
int tot=n-x-y-len+2;
if(tot<0||tot&1) continue;
int num=C(len+tot\/2-1,len-1);
add(ans,num*mod(tot*fpm(len,p-2)%p+1)%p*mod(s[n]-s[len-1]-s[n-len])%p);
if(x==2) add(ans,num*a[n-len+1]%p);
if(y==2) add(ans,num*mod(a[n]-a[len-1])%p);
}
}
cout<<ans<<endl;
}
signed main()
{
\/\/freopen(".in","r",stdin);
\/\/freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
init();
cin>>T;
while(T--) solve();
return 0;
}
::::
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-25 20:19:03
趁它还是紫题,赶紧来写一发。
给你一个字符串 $s$ ，你可以对于 $s$ 的一个子串进行翻转，问你翻转后 $s$ 的子串中满足各个字符都不相同的最长子串的长度。
首先，我们观察可以发现，对于翻转后合法的一个子串，其翻转前是两个子串，而且他们的字符互不相同，我们是不关心他们的前后顺序的。
因此，题意转化为求字符串 $s$ 的两个字符没有交集子串拼接起来的最大长度是多少。
其次，我们观察到只有前 $20$ 个字符，因此我们可以状压表示字符的出现，一个子串的状态的第 $i$ 位为 $1$ 表示这一个字符在这个子串中出现了。
于是，思路就有了，我们可以将 $s$ 的每一个没有重复字符的子串的状态处理出来（我们将其中一个子串设为 $s1$ ），然后再找另一个子串（设为 $s2$ ），满足在 $s1$ 和 $s2$ 中出现的字符没有交集，求最大长度。
那么我们就可以运用高维前缀和解决。
但是，除了高维前缀和，我们还可以有另一种解释。在对 $s1$ 的状态取反后，我们获得的另一个状态中表示的字符不一定都出现了，可能出现了它的一个子集，那也是符合题意的，于是我们可以枚举状态 $i$ 的子集，找其中贡献最大的，但也不用全都枚举，因为会造成重复枚举，只需要枚举出现的字符的数量比 $i$ 少 $1$ 的状态 $x$ 即可（因为 $i$ 的其他子集 $x$ 已经枚举过了）。
时间复杂度显然是可以接受的。
于是我们就做完了。
\/\/区间翻转后,子串的字符集不会发生改变,其实就是求两个子串拼一起的最大价值
#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
string s;
int len[1<<20];
int sum[1<<20]; \/\/高维前缀和
int ans;
signed main()
{
\/\/freopen(".in","r",stdin);
\/\/freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>s;
for(int i=0;i<s.size();i++)
{
int da=0;
for(int j=i;j<s.size();j++)
{
if(da&(1<<(s[j]-'a'))) \/\/ 看似两层循环,实际上最多20
{
break;
}
da|=(1ll<<(s[j]-'a'));
len[da]=j-i+1;
}
}
for(int i=0;i<(1ll<<20);i++)
{
sum[i]=len[i];
}
for(int i=0;i<(1ll<<20);i++)
\/\/高位前缀和,但还可以换个思路,实际上在统计答案时
\/\/我当前状态的取反后的状态不一定是满的,此时它的子集也是符合要求的,也要统计,可以结合下面的代码
{
for(int j=0;j<20;j++)
{
if(i&(1ll<<j)) sum[i]=max(sum[i],sum[i^(1ll<<j)]);
}
}
for(int i=0;i<(1<<20);i++)
{
ans=max(ans,sum[((1<<20)-1)^i]+sum[i]);
}
cout<<ans;
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-11 19:31:12
题目传送门：Codeforces
给你一个矩阵，第 $i$ 行第 $j$ 列写着 $i^j$，问矩阵中有多少不同的数。
首先我们可以发现，出现了多少数与指数密切相关，那么考虑第 $d$ 行，我们令 $d$ 在之前都没有出现过（$d \neq 1$），那么我们可以将第 $d$ 行，第 $d^2$ 行，第 $d^3$ 行一直到最大的小于 $n$ 的第 $d^k$ 行单独提取出来看，我们发现出现的数的数量只取决于指数，而且发现提取出来的矩阵的第 $i$ 行第 $j$ 列的数的指数为 $i \times j$。
综合考虑，我们还发现，这个规律对于任何的底数都成立，于是在统计答案时把当前统计到的行打标记，在下一次遍历到的时候避免重复统计即可。
对于提取出来的矩阵，我们发现最多只有 $\log_{2}{n}$ 行，既然对于每个底数答案不变，那么我们可以预处理出来对于提取出来的前 $i$ 行的答案。
复杂度 $O(n \log n)$。
不理解可以结合代码食用。
#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int n,m;
int sum;
bool vis[N],us[N*20];\/\/vis: 这一行有没有被统计过 ; us:这个指数有没有出现过
int cnt[40];\/\/前i行的答案
int ans=1;\/\/第一行不用统计,直接是1
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=20;i++)
{
for(int j=1;j<=m;j++)
{
if(!us[i*j])
{
sum++; \/\/sum从0开始,统计前i行的答案
us[i*j]=1;
}
}
cnt[i]=sum;
}
for(int i=2;i<=n;i++)
{
if(!vis[i]) \/\/如果这一行没被统计过,那么统计
{
int p=i;
int cur=0;
while(p<=n)
{
cur++;
vis[p]=1;
p*=i;
}
ans+=cnt[cur];
}
}
cout<<ans;
return 0;
}
鲁ICP备2025150228号