Znzryb's Blog
0%

Posted on Edited on

思路讲解

+,-,+,-的走就可以了。

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78859553

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://chatgpt.com/c/689c99ac-b064-8324-881c-c407b94bd235

G-Permutation 题目极简笔记（Notion 块级公式版）

1. 问题核心

  • 操作：两端删除元素，或查询当前最小值并把它追加到 a。

  • 共执行 n 步，问不同的 a 序列数量。

  • 输入保证为排列（每个 1…n 恰好一次）。

2. 关键性质

  1. 最小值“时代”严格递增（因为是排列，无重复）。

  2. 按“最后一个时代所属的区间”分类：

  • 不重：每个 a 只有一个最后时代；
  • 不漏：每个 a 都有最后时代。
  1. 分类后只需两个量：
  • m：到达最后时代时的区间长度（剩余元素数）；
  • d：经历的时代个数（最小值更新次数 + 1）。

3. 计数模型（每个时代的 Query 次数）

下面是 q 的约束（最后一个时代至少查询一次；总查询次数不超过 m）：
qd≥1,q1,…,qd−1≥0,∑i=1dqi≤mq_d \ge 1,\quad q_1,\dots,q_{d-1} \ge 0,\quad \sum_{i=1}^{d} q_i \le m

固定总查询次数 Q 的分配方案数（隔板法）为：
(Q+d−2d−1)\binom{Q + d - 2}{d - 1}

4. 求和得到闭式

对所有可行的 Q（从 1 到 m）求和，有：

∑Q=1m(Q+d−2d−1)=(m+d−1d) \sum_{Q=1}^{m} \binom{Q + d - 2}{d - 1} = \binom{m + d - 1}{d}

因此，某个区间作为“最后时代”的贡献为：

(m+d−1d) \binom{m + d - 1}{d}

5. 最终答案

把所有区间（作为最后时代）累加，再加 1（空序列）：

Ans=∑all intervals(m+d−1d)+1 \mathrm{Ans} = \sum_{\text{all intervals}} \binom{m + d - 1}{d} + 1

6. 实现要点（思路提要）

  • 用 RMQ/ST 或单调栈 + 分治，拿到每个“最后时代”区间的 m 与 d；

  • 对每个区间加上上面的组合数；最后整体再加 1。

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78844877

上面这段代码非常好，下面仅仅只是为了测试一下zkw线段树的这个功能以及常数

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

这道题目的想法实际上非常暴力。

DP状态定义

  • dp[u][h]：以节点u为根的子树，改造为正好高度h的AVL树的最小操作次数（代价）。
    • 注意：高度正好h，根u保留。
    • 如果无法做到，设为INF（大数）。

问题描述

这道题给你一棵以节点1为根的二叉树（节点数n ≤ 2×10^5），但它可能不是AVL树（即高度平衡二叉树：每个节点左右子树高度差不超过1）。你可以通过三种操作来改造它：

  1. 删除一个叶子节点。

  2. 选择一个没有左孩子的节点，添加一个新节点作为它的左孩子。

  3. 选择一个没有右孩子的节点，添加一个新节点作为它的右孩子。

目标是求最小操作次数，使整棵树变成AVL树。注意：操作可以任意次，包括删除原有节点或添加新节点，但根节点1必须保留（因为AVL树定义包括根）。

多测试用例，T ≤ 10000，但总∑n ≤ 2×10^5。

解题思路

我们用树形动态规划（DP）来解决这个问题。核心是计算每个子树的最小代价，使其成为指定高度的AVL树。

关键概念

  • AVL树的定义：如题所述，空树高度0；否则高度 = max(左高, 右高) + 1，且|左高 - 右高| ≤ 1，且左右子树也是AVL。

  • 操作的本质：

    • 删除叶子：相当于 pruning（修剪）不需要的部分。
    • 添加孩子：相当于在空位上建新子树。
    • 要平衡树，我们可能需要删除整个子树（代价 = 子树大小，因为要逐个删除叶子），然后从头建一个平衡的子树（代价 = 新添加的节点数）。

  • 最****小节点数的AVL树：对于高度h的AVL树，最小节点数m[h]满足：

    • m[0] = 0（空树）
    • m[1] = 1（单节点）
    • m[h] = 1 + m[h-1] + m[h-2]（类似斐波那契，最小化节点：一侧高度h-1，另一侧h-2）
    • 这可以预计算，h最高取60就够，因为m[60]已经很大，超过n的范围。

DP状态定义

  • dp[u][h]：以节点u为根的子树，改造为正好高度h的AVL树的最小操作次数（代价）。

    • 注意：高度正好h，根u保留。
    • 如果无法做到，设为INF（大数）。

  • 最终答案：min over h (dp[1][h])，因为根树高度可以任意，只要平衡。

最关键的这个部分已经给出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
vector<vll> dp(N+5,vll(H+5,INF));
dp[0][0]=0;
dp[0][1]=1;
FOR(h,2,H){
    dp[0][h]=dp[0][h-1]+dp[0][h-2]+1;
}
function<void (ll,ll)> dfs=[&](ll u,ll p){
    bool isleaf=true;
    vll wp;
    for(auto v:g[u]){
        if(v==p) continue;
        dfs(v,u);
        wp.EB(v);
        isleaf=false;
    }
    if(isleaf){
        dp[u][1]=0;
        dp[u][0]=1;
        FOR(h,2,H){
            dp[u][h]=dp[0][h]-1;
        }
        return;
    }
    if(SZ(wp)==1){
       wp.EB(0);
    }
    ll v=wp[0],v2=wp[1];
    vll ldp(H+5,INF),lldp(H+5,INF);
    FOR(h,1,H){
        ldp[h]=dp[v][h-1];
    }
    FOR(h,1,H){
        ldp[h]+=min({dp[v2][h-1],dp[v2][h-2<0?0:h-2]});
    }
    FOR(h,1,H){
        lldp[h]=dp[v2][h-1];
    }
    FOR(h,1,H){
        lldp[h]+=min({dp[v][h-1],dp[v][h-2<0?0:h-2]});
    }
    FOR(h,1,H){
        dp[u][h]=min(ldp[h],lldp[h]);
    }
    dp[u][0]=dp[u][1]+1;
    
};
dfs(1,1);

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

AC代码

https://www.luogu.com.cn/record/230330272

https://www.luogu.com.cn/record/230330447

最优解。

image

心路历程（WA，TLE，MLE……）

线段树内部之间不要相互调用

P1471 方差

千万不要这么干，因为不仅更新的时候要调用，下传标记也要调用，你能保证两个线段树的懒标记状态一样吗？这个是不可能的，因为你也不可能同时更新，询问两个线段树，除非把他们合为一个。

image