2025牛客多校G题解：AVL树、排列、军训题如何解答？

F.军训 数学 #曼哈顿距离 题目 思路 首先很容易想到的是，一定可以通过旋转到达目标状态，不会有-1的情况 接下来是一个关键的观察：关注双脚所在中点的移动 发现实际上中点移动一个单位曼哈顿距离就代表一次旋转 因此进行坐标变换即可 代码实现 #include<iostream> #include<vector> #include<map> #include<cmath> #include<set> using namespace std; using ll = long long; #define rep(i, a, b) for(int i = (a); i <= (b); i ++) #define per(i, a, b) for(int i = (a); i >= (b); i --) #define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n'; constexpr ll inf = 1e9 + 5; #define int ll #define double long double void trans(double&x,double&y){ double u=x+y,v=x-y; x=u,y=v; } void eachT() { int sx1,sy1,sx2,sy2,tx1,ty1,tx2,ty2; cin>>sx1>>sy1>>sx2>>sy2>>tx1>>ty1>>tx2>>ty2; double sx=1.0*(sx1+sx2)/2,sy=1.0*(sy1+sy2)/2; double tx=1.0*(tx1+tx2)/2,ty=1.0*(ty1+ty2)/2; trans(sx,sy),trans(tx,ty); double dis=abs(sx-tx)+abs(sy-ty); cout<<(int)dis<<'\n'; } signed main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); ll t = 1; cin >> t; while (t--) { eachT(); } } A.AVL树 树上dp #dp #dfs 题目 思路 本题是一个比较巧妙的树上dp，状态设置较为特殊 状态含义： \(dp[u][h]\)表示将节点\(u\)及其子树修改为高度为\(h\)的\(AVL\)树所需要的最少操作次数 状态转移： \[\begin{align} &dp[u][h]=min\{ dp[u][h],dp[lson][h-1]+dp[rson][h-1] \}\\ \\ &dp[u][h]=min\{ dp[u][h],dp[lson][h-2]+dp[rson][h-1] \}\\ \\ &dp[u][h]=min\{ dp[u][h],dp[lson][h-1]+dp[rson][h-2] \} \end{align} \] 由于两棵子树的高度差不能超过1，所以枚举左右子树的三种情况进行状态转移 注意到转移最开始的时候需要调用\(dp[u][0]\)的值，其含义为：将\(u\)及其子树完全删除所需要的最少操作次数，因此该值即为\(u\)的子树大小\(size\)，跑一遍\(dfs\)预处理即可 最麻烦的事情是\(dp[0][h]\)，若\(u\)没有左儿子，那么其\(lson\)的值即为\(0\)，此时dp需要访问\(dp[0][h]\)的值，代表构建一棵高度为\(h\)的\(AVL\)树所需要的最小操作次数 画出高度为\(2,3,4,5\)的最简\(AVL\)树，会发现子树之间存在特别的递推关系： 当前子树必定等于其爷爷节点的另一个子树， 当前子树大小等于孙子子树大小加上另一个儿子子树大小再加上自己本身 即： \[dp[0][h]=dp[0][h-1]+dp[0][h-2]+1 \] 至此可以完成树上dp的全过程 代码实现 #include<iostream> #include<vector> #include<unordered_map> #in