2026春季W1(3.2~3.8)

CR1082Contest

C1&C2

C1：按照从右到左的顺序处理，每当看到一个元素 \(a[i]\) ，就会消除堆栈顶的 \(a[i]+1\) ，最后剩余在栈中的数就是无法删除的数。

C2：

1. \(f(b)\) 的贪心划分机制

有效子段必须满足连续递增（\(b_i \le b_{i-1} + 1\)）且严格大于起点（\(b_i > b_L\)）。因此，贪心扫描时的断开条件仅有两个：

• 硬性断点：\(b_i > b_{i-1} + 1\)
• 下界阻断：\(b_i \le b_L\)依据此规则划分出的最少子段数即为 \(f(b)\)。

2. 全局状态转移数组

由于断点条件在全局视角下独立，位置 \(i\) 的下一个断点 \(nxt[i]\) 是固定的（若无则指向 \(n+1\)）：

\[nxt[i] = \min(HB[i], NLE[i]) \]

• \(HB[i]\)：右侧首个满足 \(a_j > a_{j-1} + 1\) 的位置。
• \(NLE[i]\)：右侧首个满足 \(a_j \le a_i\) 的位置（用单调栈预处理）。

3. 树上贡献统计 (\(O(n)\))

因为 \(nxt[i] > i\)，可将 \(nxt[i]\) 视作 \(i\) 的父节点构成隐式树。求所有查询的子段和，等价于求所有树边被经过的总次数。
节点 \(u\) 及其子树每次跳向 \(nxt[u]\) 对全局总和的贡献值为：

\[\text{Contribution}_u = (nxt[u] - u) \times (\text{dist}[u] + sz[u]) \]

(其中 \(sz[u]\) 是以 \(u\) 为根的子树大小，\(\text{dist}[u]\) 是该子树内所有节点到 \(u\) 的距离之和)

4. 线性拓扑优化（免建树/免 DFS）

核心优化：严格的编号单调性（\(nxt[i] > i\)）即代表天然的拓扑序。
我们完全无需实际建图或使用 DFS。只需一个简单的 for 循环从 1 到 \(n\) 正向遍历，即可顺推完成所有树形 DP 信息的向上传递，彻底避免爆栈并极大压低时间常数。

const int mxn = 2e6+10;
int n;
int a[mxn];
int hb[mxn];
int nme[mxn];
int nxt[mxn];
int siz[mxn], dep[mxn]; // 用于树状向上传递信息
void LonelyLunar_solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        nme[i] = n + 1;
    }
    // 1. 逆序求最近硬性断点 (hb)
    int lst = n + 1;
    for(int i = n; i >= 1; i--){
        hb[i] = lst;
        if(i > 1 && a[i] > a[i-1] + 1) lst = i; 
    }
    // 2. 单调栈求下一个小于等于的元素 (nme)
    stack<int> st;
    for(int i = 1; i <= n; i++){
        // 核心修正：求小于等于，因此遇到 >= 当前值的元素就出栈
        while(!st.empty() && a[st.top()] >= a[i]){
            nme[st.top()] = i;
            st.pop(); 
        }
        st.push(i);
    }
    // 初始化 DP 数组，范围要开到 n+1 接收最终汇聚的数据
    for(int i = 1; i <= n + 1; i++){
        siz[i] = 1;
        dep[i] = 0; 
    }
    int res = 0;
    // 3. O(n) 正向传递信息，彻底取代 DFS！
    for(int i = 1; i <= n; i++){
        nxt[i] = min(nme[i], hb[i]);
        // 当遍历到 i 时，由于前面的子节点都已经把信息累加上来了，
        // 此时的 dep[i] 和 siz[i] 已经是最终确定的值。
        // 直接计算当前点到其父节点的这条边对全局的贡献：
        res += (nxt[i] - i) * (dep[i] + siz[i]);
        
        // 向上（向父节点 nxt[i]）传递当前子树的累加信息
        siz[nxt[i]] += siz[i];
        dep[nxt[i]] += dep[i] + siz[i];
    }
    cout << res << endl;
}

CR1082Contest

D

1. 明确收益公式与贪心方向

每一次“剪切-粘贴”操作的额外收益可以简化为：
收益 = 剪下子树的权值和 \(\times\) (新挂接点的深度 - 原父节点的深度)
因为题目保证权值均为正数，所以子树权值和永远大于 0。这就推导出了两个绝对的贪心结论:

• 往哪儿贴？（找最深）：为了让乘积最大，剪下来的子树一定要贴到剩余部分里最深的节点下面。
• 剪哪个？（剪整根）：如果我们决定在某个儿子的分支里动刀，直接剪掉这个直接儿子，永远比剪它下面的子孙更划算。因为儿子的权值和更大，且它本来挂得更浅（能产生更大的深度落差）。

2. 第1遍 DFS：收集基础情报

在不考虑任何操作的情况下，我们先遍历一次整棵树（自底向上），为每个节点 \(u\) 算好四样东西：

• \(dep_u\)：当前节点的深度。
• \(s_u\)：以 \(u\) 为根的子树权值和。
• \(max\_dep_u\)：以 \(u\) 为根的子树里，最深节点的深度。
• \(f_u\)：如果不做任何操作，以 \(u\) 为根的初始总代价。

3. 第2遍 DFS：动态规划求最大收益

我们定义 \(ans[u]\) 为：仅仅在 \(u\) 的子树内部，执行至多一次操作能带来的最大额外收益。
对于节点 \(u\)，我们只需要看它的直接儿子们。为了快速知道“如果剪掉儿子 \(v\)，剩下的分支最深有多深”，我们提前找出所有儿子里 \(max\_dep\) 的最大值和次大值。
接着遍历 \(u\) 的每一个儿子 \(v\)：

• 如果剪掉 \(v\)，剩余部分的最深深度（记为 \(M_v\)）可以通过刚才的最大值或次大值直接 \(O(1)\) 拿到。
• 剪掉 \(v\) 并跨分支拼接的收益 = \(s_v \cdot (M_v - dep_u)\)。
• 状态转移：\(ans[u]\) 的最终结果，就是在以下选项中取最大值：
  1. 儿子 \(v\) 内部自己操作的最大收益（即 \(ans[v]\)，代表不跨分支）。
  2. 刚刚算出的“剪掉 \(v\) 跨分支拼接的收益”。
  3. 维持 0（代表什么都不做）。
     对于题目要求的任意节点 \(r\)，它作为局部根节点的最终答案，就是它的初始总代价 \(f_r\) 加上最大额外收益 \(ans[r]\)。

ABC441EProblem

考虑一个数 \(cur\)。当前字符为'A'时 \(cur+1\) ，当前字符为'B'时 \(cur-1\) ，为'C'时不变，问题转化为求 \(i, j\)，当 \(i < j\) 时，\(pre_i < pre_j\)

ABC448Contest

E

(矩阵)快速幂专场，学习新思路。
\(\lfloor N/M \rfloor\) 可以转化为 \(\frac{N-N \bmod M}{M}\) ，令\(R \ = \ N \bmod M\) ，\(Q \ = \ \frac{N-R}{M}\) ，则原式可以转化为：

\[(N-R) \cdot M^{-1} \bmod 10007 \]

则我们转化为了求 \(N \bmod 10007\) 和 \((N \bmod M ) \bmod 10007\)。

回过头关注新数字的组成，是由 \(l[i]\) 个 \(c[i]\) 首尾拼接得到，我们可以先令 \(c[i] \ = \ 9\)，于是原式变成 \(l[i]\) 个9，将其表示为 \(10^{l[i]}-1\)，再将9转化为 \(c[i]\) (此处先除以9后乘以 \(c[i]\))，就可以得到 \(N\) 的构成表达式：

\[N = c[i] \cdot \frac{10^{l[i]}-1}{9} \]

为了拼接这个式子，需要先将数字 \(V\) 向左移位（乘 \(10^{l_i}\)），再加上新数字。得到每次拼接后的新数值递推式：

\[V_{\text{new}} = V \cdot 10^{l_i} + c_i \cdot \frac{10^{l_i} - 1}{9} \]

我们先计算 \(N \bmod 10007\)（维护变量 \(V_P\)）：

因为 \(10007\) 是素数，且与分母 \(9\) 互质，我们可以直接使用乘法逆元和普通快速幂。 \(9\) 在模 \(10007\) 下的逆元是 \(1112\)（因为 \(9 \times 1112 = 10008 \equiv 1 \pmod{10007}\)）。初始设 \(V_P = 0\)。遍历每一段 \((c_i, l_i)\)：用普通快速幂算出 \(P = 10^{l_i} \pmod{10007}\)。直接代入公式更新 \(V_P\)：

\[V_P = \left( V_P \cdot P + c_i \cdot (P - 1) \cdot 1112 \right) \pmod{10007} \]

然后我们计算 \(N \bmod M\)（维护变量 \(V_M\) 即余数 \(R\)）

因为 \(M\) 可能与 \(9\) 不互质，不能求逆元，我们使用矩阵快速幂来避开除法，完成状态转移。
对于在末尾拼接一个 \(c_i\)，状态转移可以写成矩阵形式：

\[\begin{bmatrix} V_{\text{new}} & 1 \end{bmatrix} = \begin{bmatrix} V & 1 \end{bmatrix} \begin{bmatrix} 10 & 0 \\ c_i & 1 \end{bmatrix} \]

连续拼接 \(l_i\) 个 \(c_i\)，等价于该矩阵连乘 \(l_i\) 次。
维护方法：
初始设 \(V_M = 0\)。遍历每一段 \((c_i, l_i)\)：

1. 构造底数矩阵 \(A = \begin{bmatrix} 10 & 0 \\ c_i & 1 \end{bmatrix}\)。
2. 用矩阵快速幂算出 \(T = A^{l_i} \pmod M\)
3. 利用结果矩阵 \(T\) 更新 \(V_M\)：

\[V_M = (V_M \cdot T_{00} + 1 \cdot T_{10}) \pmod M \]

对于 \((N-R) \cdot M^{-1} \bmod 10007\) ，我们已经全部求出括号内的内容，相减再与 \(M\) 的逆元相乘即可。

类似题目： ABC129F(该题目的区别在于不确定加入数字的位数，需要根据数字位数分段计算)F - Takahashi's Basics in Education and Learning

牛客周赛Round132Contest

E

注意两点，第一是要想起来可以搜索别死磕数学公式，第二是卡常+边界处理， \(bool\) 数组转 \(int\) 然后用当前处理样例序号代替每次\(memset\) 可以降低运行时间，然后就是一个裸 \(BFS\)。