2025牛客多校第九场 G.排列 A.AVL树 F.军训 个人题解

F.军训

数学 #曼哈顿距离

题目

思路

首先很容易想到的是，一定可以通过旋转到达目标状态，不会有-1的情况
接下来是一个关键的观察：关注双脚所在中点的移动

发现实际上中点移动一个单位曼哈顿距离就代表一次旋转
因此进行坐标变换即可
代码实现

1. #include<iostream>
2. #include<vector>
3. #include<map>
4. #include<cmath>
5. #include<set>
6. using namespace std;
7. using ll = long long;
8. #define rep(i, a, b) for(int i = (a); i <= (b); i ++)
9. #define per(i, a, b) for(int i = (a); i >= (b); i --)
10. #define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
11. constexpr ll inf = 1e9 + 5;
12. #define int ll
13. #define double long double
14. void trans(double&x,double&y){
15.     double u=x+y,v=x-y;
16.     x=u,y=v;
17. }
19. void eachT() {   
20.     int sx1,sy1,sx2,sy2,tx1,ty1,tx2,ty2;
21.     cin>>sx1>>sy1>>sx2>>sy2>>tx1>>ty1>>tx2>>ty2;
22.     double sx=1.0*(sx1+sx2)/2,sy=1.0*(sy1+sy2)/2;
23.     double tx=1.0*(tx1+tx2)/2,ty=1.0*(ty1+ty2)/2;
24.     trans(sx,sy),trans(tx,ty);
25.     double dis=abs(sx-tx)+abs(sy-ty);
26.     cout<<(int)dis<<'\n';
27. }
29. signed main(){
30.     ios::sync_with_stdio(false);
31.     cin.tie(0), cout.tie(0);
32.     ll t = 1;
33.     cin >> t;
34.     while (t--) {
35.         eachT();
36.     }
37. }

复制代码

G.排列

组合数 #笛卡尔树 #dfs

题目

思路

考虑一组样例：

\[5,3,6,4,1,7,2\]
操作分为删去与打印两种，若想要打印数字\(i\)，则\(i\)必须为当前序列的最小值
因此发现打印的可行性具有一定的顺序，比如我想打印\(4\)，那么必然要先将\(1,2,3\)删去
而删去的过程中又必然会将某些经过的点提前删去，因此尝试画出路径图：

发现这实际上就是一棵笛卡尔树！

• 树中节点的左右关系与原序列中的一致
  
• 树中的父亲节点必定比左右儿子要小，对应着必须先走过小的节点才能走到大的节点
  

接下来就是如何“数数”了：
我们可以通过打印序列的最后一个元素是谁，来进行分类
这样分类的依据就在于，每次打印的元素必然是序列中的最小元素，因此枚举每个数作为最后一个打印的数，不会出现情况间的重复与遗漏

以数字\(4\)为例，想要走到四号节点，必然需要先删去某些节点

• 比4大的1、3必然要删除
  
• 原序列中，在3左边、1右边的所有数都要删除，这样才能删掉1、3
  综上 ，发现保留下来的数正好就是4所在的子树（蓝色区域）
  

由于删除操作已经占了\(n-size\)次，那么能够打印序列的最大长度正是\(size\)
若把左边看作最后一次打印的元素，右边看作第一次打印的元素，那么会发现打印序列是一个单调不增序列，并且开头元素固定为4
开头固定的单调不减序列有多少种方案数？
自然是使用占位置的隔板法进行统计：

• 能够出现在打印序列中的数字必然是比4小且靠中间的位置，即沿着4往根部走，途中遇到的所有数字
  
• 能够打印的数字的数量即为4的深度-1，\(dep-1\)，即1、3两个数字
  
• 因此有\(l_{4},l_{3},l_{1}\)三块隔板，\(l_{i}\sim l_{i-1}\)间填数字\(i-1\)即可构造单调不增序列
  
• \(l_{1}\)的右边没有东西，填0代表空着，这也对应了长度小于\(size\)的情况
  因此方案数计算公式为：
  

\[C_{size+dep-1}^{dep}\]
在dfs回溯过程中，\(size,dep\)均已知，可以直接算答案
因此一遍dfs即可算出答案
代码实现

[code]#include#include#include#include#includeusing namespace std;using ll = long long;#define rep(i, a, b) for(ll i = (a); i = (b); i --)#define see(stl) for(auto&ele:stl)cout>x;        if(st.empty())st.push(x);        else{            if(x