A

树形dp 观察

可以删点，加点，问把一个二叉树变成avl的最少操作次数？

avl的要求就是左右子树都是avl树，且左右子树高度差不超过1.

注意到这是个递归定义，可以考虑树形dp，计算出一个点的两个子树变成avl树的最小代价，然后再用这两个一个变成avl的子树，和当前点拼起来，就能计算当前点为根的子树变成avl的最小代价

但是，想让当前点为根的子树是avl，不仅需要两个子树都是avl，还需要知道两个子树的高度，然后看他们满不满足子树高度差不超过1的这个约束。而子树高度可以是任意取值，所以考虑把子树高度也放在dp状态里

也就是 $dp(i,j)$ 表示以 $i$ 为根的子树，变成高度为 $j$ 的avl树，的最小代价。那么我们转移时，如果当前枚举的状态是 $dp(i,j)$ ，那么两个子树的的高度，要么是 $(j-1,j-1)$ ，要么是 $(j-1,j-2)$ 。

如果某一个儿子并不存在，那么想把它变成高度为 $j$ 的avl树，就只能全用加点操作，加出来一颗avl树。由于我们想让操作次数最少，就需要知道得到一个高度为 $j$ 的avl最少需要多少个点，设这个值为 $g(j)$ ，手玩可以发现，高度为 $j$ 的最小avl树，其实就是高度为 $j-1,j-2$ 的最小avl树分别当左右子树得到的，也就是 $g(j)=g(j-1)+g(j-2)+1,g(0)=0,g(1)=1$ ，这可以预处理出来，儿子不存在时直接查表

这样转移复杂度是 $O(n\max(h))$ ，取决于我们高度这个维度开多大。注意到，这个 $g$ 的转移式其实就是类斐波那契，增长很快，高度26时，通过加点得到一个这样的avl树所需的点数就超过原始树的总点数(2e5)了，所以与其增加点得到一个高度26的avl树，不如用删除操作把原树全删了。

所以高度大于26都是无意义的状态，只用开到26，故复杂度 $O(n \log{n})$

void solve(){
    int n;
    cin>>n;
    vi l(n+1),r(n+1);
    rep(i,1,n){
        cin>>l[i]>>r[i];
    }
    vi fib(n+1);
    vvi dp(n+1,vi(30,1e9));
    dp[0][0]=0,dp[0][1]=1;
    rep(i,2,27){
        dp[0][i]=dp[0][i-1]+dp[0][i-2]+1;
    }
    auto &&dfs=[&](auto &&dfs,int u)->void{
        if(!u)return;
        dfs(dfs,l[u]);
        dfs(dfs,r[u]);
        rep(i,2,27){
            dp[u][i]=min({
                dp[l[u]][i-1]+dp[r[u]][i-1],
                dp[l[u]][i-1]+dp[r[u]][i-2],
                dp[l[u]][i-2]+dp[r[u]][i-1]
            });
        }
        dp[u][1]=dp[l[u]][0]+dp[r[u]][0];
        dp[u][0]=dp[u][1]+1;
    };
    dfs(dfs,1);
    int ans=1e18;
    rep(i,0,27){
        ans=min(ans,dp[1][i]);
    }
    cout<<ans<<'\n';    
}

B

自动机/前后缀分解

在一个字符串找到合法日期子序列的个数，日期包含8位，4位年份，2位月份，2位天数。

官解的做法大约是 $O(n)$ 的，这相当于一个多模式串匹配问题，用一个神秘自动机来做，这确实很难。

但实际上数据弱了，放过去了一种暴力做法，这个做法写起来就简单了。注意到我们可以把年份和日期分开，也就是前后缀分解。考虑一个前缀里的所有合法年份个数，和一个后缀里的所有合法月份日期个数，乘起来就是在这个地方分解的贡献。

这样可能会算重，准确的做法是吗，当前分解为 $[1,i],[i+1,n]$ ，考虑以 $i$ 结尾的合法年份个数，以及 $[i+1,n]$ 里的所有合法月份日期个数(不要求以 $i+1$ 开头)，乘起来就是这个分解的贡献。

这要求我们预处理以 $i$ 为结尾的合法年份个数，为了考虑闰年我们还要计算以 $i$ 结尾的合法闰年个数，这其实很简单，状态机dp即可， $dp(i,j)$ 最后一次匹配在 $i$ ，匹配到了模式串的第 $j$ 个位置的方案数。

然后我们还要知道每个后缀里的合法月份日期个数，类似地这需要我们计算出以 $i$ 为开头的合法月份日期个数，从n开始，倒着做状态机dp即可。但问题是合法年份的约束比较简单，不全0即可，合法闰年也只要考虑模100，模4，模400即可，模式比较简单。但月份的模式并不简单，而且这里还要倒着匹配，如果想扫一遍dp就得到所有月份日期的个数，有点难。所以这里一个取巧(暴力)的方法是，枚举所有月份日期串，一共366个(包含2.29)，对于每个月份日期串，就是一个完全确定的字符串匹配，没有任何难度了。

这样做复杂度 $O(366*4*n)$ ，可以过。出题人设成一秒可能是想卡掉这个做法，但最后没卡掉，基本没人写正解，都是这样做的

F

思维

网格图上，开始有两个距离为1的点，每次移动可以让一个点绕另一个点旋转90度。问移动到一组目标位置的最小移动次数

手玩可以发现，不改变朝向，直接横着，竖着平移，移动一格需要2次，斜着平移也就是xy两个方向都移动一格，也只需要两次操作。

进一步，不改变朝向的前提下，从一个位置移动到另一个位置，可以西安斜着平移到x或y维度等于目标位置，然后横着或竖着平移移动过去。那么移动次数就是xy两个维度的距离较大值*2

现在唯一的问题就是可能初始和目标的朝向不一样，开始需要一次操作把朝向变成相同的，这有四种移动方式。移动后的初始位置也都不一样了，后续移动次数不一样。一种省脑子的写法就是枚举这四种情况，取min即可，反正只有四种。

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

int getD(int a, int b, int c, int d, int e, int f, int g, int h) {
    int mx = abs(min(a, c) - min(e, g));
    int my = abs(min(b, d) - min(f, h));
    return max(mx, my);
}

int sign(int a, int b, int c, int d) {
    if (a == c) return 1;
    return 0;
}

void solve() {
    int sx1, sy1, sx2, sy2, tx1, ty1, tx2, ty2;
    cin >> sx1 >> sy1 >> sx2 >> sy2 >> tx1 >> ty1 >> tx2 >> ty2;
    if (sign(sx1, sy1, sx2, sy2) == sign(tx1, ty1, tx2, ty2)) {
        cout << getD(sx1, sy1, sx2, sy2, tx1, ty1, tx2, ty2) * 2 << "\n";
    } else {
        int ans = INF;
        if (sign(sx1, sy1, sx2, sy2) == 1) {
            ans = min(ans, getD(sx1, sy1, sx1 + 1, sy1, tx1, ty1, tx2, ty2) * 2 + 1);
            ans = min(ans, getD(sx1, sy1, sx1 - 1, sy1, tx1, ty1, tx2, ty2) * 2 + 1);
            ans = min(ans, getD(sx2 + 1, sy2, sx2, sy2, tx1, ty1, tx2, ty2) * 2 + 1);
            ans = min(ans, getD(sx2 - 1, sy2, sx2, sy2, tx1, ty1, tx2, ty2) * 2 + 1);
        } else {
            ans = min(ans, getD(sx1, sy1, sx1, sy1+1, tx1, ty1, tx2, ty2) * 2 + 1);
            ans = min(ans, getD(sx1, sy1, sx1, sy1-1, tx1, ty1, tx2, ty2) * 2 + 1);
            ans = min(ans, getD(sx2, sy2 + 1, sx2, sy2, tx1, ty1, tx2, ty2) * 2 + 1);
            ans = min(ans, getD(sx2, sy2 - 1, sx2, sy2, tx1, ty1, tx2, ty2) * 2 + 1);
        }
        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

题解还有个喵喵做法，就是从两个点的中点来看，我们每次可以执行的旋转操作实际上就是中点xy坐标移动 $0.5$ ，旋转四十五度看就是上下左右移动一格，那这其实就是曼哈顿距离

G

笛卡尔树/单调栈，组合数学球盒问题

每次可以删掉最左或最右，或把min加入序列a,两种操作加起来恰好n次。问能得到的不同的序列a的个数

这里a的长度是不确定的，所以首先要想一个不重不漏计算所有a的方法。一个比较好的方式就是枚举a的最后一个元素，这样不同情况之间是没有重叠的，并且也能覆盖到所有情况。

如果一个元素x能作为a的最后一个元素，那么必须把比a小的元素都删掉，也就是跑个单调栈的话，得到的区间 $(l,r)$ 之外的元素必须都删掉，之内的元素可删可不删，也就是最后剩余没删的元素，一定是 $(l,r)$ 的一个子集。由于查询最小值加到a这个操作和删除操作一共n次，a序列度等于n-删除次数，等于n-(n-剩余区间长度)，等于剩余区间长度。这个剩余区间长度是 $[0,r-l-1]$ ，也就是以x为结尾的a序列的长度可能可能是 $[0,r-l-1]$

接下来考虑可能出现在序列a里的元素，实际上也就是删除过程中出现过的所有最小值。这里用单调栈思考就不好想了。考虑引入笛卡尔树。笛卡尔树上的所有祖先，实际上就是包含当前区间的更大区间的最小值，也就是我们这里要找的删除过程中出现过的所有最小值。所以序列a里可能出现的元素个数就是x在笛卡尔树里的深度dep。引入笛卡尔树后，其实前面讨论的那个 $r-l-1$ 就是x子树的大小sz

( $PS:$ 这里简单讲一下笛卡尔树，n个节点对应序列里的n个元素，每个节点有俩值，一个是元素下标，一个是元素值。首先他对于下标是个二叉搜索树，也就是左儿子的下标比根小，右儿子下标比根大，然后他对于元素值还是个堆，也就是每个子树的根的元素值一定是整个子树的最小值。那么一个子树里的所有下标，实际上组成了一个连续区间，且这个区间内所有元素都不小于根节点，实际上这个区间也就是跑单调栈得到的区间。然后一个点x在笛卡尔树上的所有祖先，实际上就是 $[1,n]$ 这个区间一步步缩小到当前这个x子树对应的区间的过程中，出现过的所有最小值)

于是问题转化成，有dep种元素，每种元素选任意个，最小的元素（也就是x）必选至少一次，组成一个长度不超过sz的单调序列，问方案数。如果长度确定是 $i$ 这就是个基础球盒问题，序列里的每个位置看成球，可选元素看成盒子，方案数就是 $C(dep-1+i,dep-1)$ 。

注：这里如果不保证这个最小的元素必选，也就是每种元素都是可以选任意个，方案数就是 $C(dep+i,dep)$ ,这里规定最后一个元素必须是x了,转换成前缀和来看，就等价于从 $\sum a_i<=x$ 变成了 $\sum a_i=x$ ，方案数自然变了

然后现在长度是不确定的，需要求和。求和范围本来应该是a序列长度范围 $[1,sz]$ ，但因为我们已经确定了最后一个元素一定是x，这占了一个位置，故剩余序列的长度范围是 $[0,sz-1]$

$\sum_{i=0}^{sz-1} C(dep-1+i,dep-1)$

这里有另一个定理

$\sum_{i=0}^{k} C(n-1+i,n-1)=C(n+k,n)$

这个式子的证明可以这样考虑，左侧就是把 $i$ 种球，放到 $n$ 个盒子里，允许空盒，球种类数 $i$ 不超过 $k$ ，右侧相当于是增加了一种盒子,然后把未出现的球都放进这个新盒子了。两侧描述的情况是等价的。右侧就是一个 $k$ 种球， $n+1$ 个盒子的球盒问题，方案数也就是把盒子数 $t=n+1$ 带入球盒问题的原式 $C(t-1+k,t-1)=C(n+k,n)$

利用这个定理的话可以求出来我们前面那个求和式子

$\sum_{i=0}^{sz-1} C(dep-1+i,dep-1)=C(dep+sz-1,dep)$

对于每个元素，我们求一下这个式子然后累加即可。这可以在建出笛卡尔树后dfs计算

void solve(){
    int n;
    cin>>n;
    vi a(n+1);
    rep(i,1,n){
        cin>>a[i];
    }
    stack<int>s;
    vi l(n+1),r(n+1);
    rep(i,1,n){
        int cur=0;
        while(s.size()&&a[s.top()]>a[i]){
            cur=s.top();
            s.pop();
        }
        if(cur)l[i]=cur;
        if(s.size()){
            r[s.top()]=i;
        }
        s.push(i);
    }
    vi sz(n+1,1);
    auto &&dfs=[&](auto &&dfs,int u,int dep)->int{
        int res=0;
        if(l[u])res=(res+dfs(dfs,l[u],dep+1))%M2,sz[u]+=sz[l[u]];
        if(r[u])res=(res+dfs(dfs,r[u],dep+1))%M2,sz[u]+=sz[r[u]];
        res=(res+C(sz[u]+dep-1,dep))%M2;
        return res;
    };
    int pos1;
    rep(i,1,n){
        if(a[i]==1){
            pos1=i;
            break;
        }
    }
    int ans=dfs(dfs,pos1,1);
    ans=(ans+1)%M2;
    cout<<ans<<'\n';
}

J

字符串io

猫娘题，内涵24年天梯赛。需要一次读一行带空格的字符串，需要用getline。并且用这个的话可能会读到前一次输出的换行，需要把前面的最后一个换行用getchar读掉，并且注意这玩意和关流cin不太兼容，要把关流删掉，否则会出现神秘bug

void solve() {
    int n;
    cin>>n;
    cout<<n<<" nya\n";
    getchar();
    while(n--){
        string s;
        getline(cin,s);
        s+=" nya\n";
        cout<<s;
    }
}

25暑期第九场

A

B

F

G

J