A

题意：给你一个长度为n的排列a，现要求你构造一个长度为n的排列b使得 $\le a[i+1]+b[i+1] ... \le a[n]+b[n]$

思路：
因为a和b都是一个长度为n的排列，那么我们一定可以构造出 $a [i] + b [i] = a [i + 1] + b [i + 1] ... = a [n] + b [n]$ 并且这个和一定为n+1。
感兴趣可以自己下去证明一下，感觉这类题我们可以找那种特殊边界去构造就行。

代码：

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy secondusing namespace std;typedef pair<int, int> PII;const int N = 4e5 + 10, INF = 1e18;int n, m, k, _, x;
int arr[N];
char s[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> arr[i];int sum = n+1;for(int i = 1; i <= n; i ++) cout << sum-arr[i] << " ";cout << endl;
}signed main()
{IOS;cin >> _;while(_--)solve();return 0;
}

B

题意：给你两个长度为n的数组a，b。然后给一个空数组c，现在有一种操作是每次选择两个数组a，b其中的一个，把第一个元素放到c数组末尾并把这个数删除掉。不限制操作次数，问最后操作完过后的数组c中最长子串是多长(子串的数都要相同)。

思路：
其实我们只需要统计出a，b数组中每段连续相同数字的最大长度，最后把a，b中对于每个数字统计出的答案求和取最大值即可。

代码：

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy secondusing namespace std;typedef pair<int, int> PII;const int N = 5e5 + 10, INF = 1e18;int n, m, k, _, x;
int arr[N], brr[N];
char s[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> arr[i];for(int i = 1; i <= n; i ++) cin >> brr[i];map<int, int> mpa, mpb;int len = 1;for(int i = 2; i <= n; i ++){if(arr[i] == arr[i-1]) len++;else{mpa[arr[i-1]] = max(len, mpa[arr[i-1]]);//最开始取最大时忘了i-1  T_Tlen = 1;}}mpa[arr[n]] = max(len, mpa[arr[n]]);len = 1;for(int i = 2; i <= n; i ++){if(brr[i] == brr[i-1]) len++;else{mpb[brr[i-1]] = max(len, mpb[brr[i-1]]);len = 1;}}mpb[brr[n]] = max(mpb[brr[n]], len);int ans = 0;for(auto [k, v] : mpa) ans = max(ans, v+mpb[k]);for(auto [k, v] : mpb) ans = max(ans, v+mpa[k]);cout << ans << endl;
}signed main()
{IOS;cin >> _;while(_--)solve();return 0;
}

C

题意：有n个点，给你n-1条边。你有三个操作，直到无法操作为止。
step0：你要找到1最开始出现的边的地方，并画出这个点（点1）。
step1：如果对于这条边来说，如果已经有画出的我点，那么把这条边给画出来。否则就跳过这条边。
step2：如果这条边已经画完了，那么转回1号操作。直到所有点被画出结束操作。
问你最终要浏览多少遍这些边把这颗树画完。（从上到下浏览一次算一遍）

思路：

首先我们应该把这颗树建好，对于每个点和每条边出现的时间打上对应的次数。然后我们扫面这棵树，如果对于当前边出现的时间，是小于父亲节点出现的时间那么对于当前点我们就加1，最后我们对每个点取一个最大值就行了。
最开始以为是每一层有一条边出现的时间小于父亲节点的时间，答案+1，最后统计有多少层就行，最后看到一个样例才发现自己错了，贡献了一遍罚时。 T_T

代码：

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy secondusing namespace std;typedef pair<int, int> PII;const int N = 5e5 + 10, INF = 1e18;int n, m, k, _, x;
int ux[N], vx[N];
vector<PII> e[N];
map<PII, int> mp;
map<int, bool> f;int ans = 0;void dfs(int u, int fa, int cnt)
{int tmp = mp[{u, fa}]; //这条边的时间ans = max(cnt, ans);for(auto &[x, y] : e[u]){//y是这个点出现的时间。if(x == fa) continue;if(y < tmp) dfs(x, u, cnt+1);else dfs(x, u, cnt);}
}void solve()
{cin >> n;ans = 0;for(int i = 0; i < n+10; i ++){e[i].clear();}for(int i = 1; i < n; i ++){int u, v;cin >> ux[i] >> vx[i];e[ux[i]].push_back({vx[i], i});e[vx[i]].push_back({ux[i], i});mp[{ux[i], vx[i]}] = i;mp[{vx[i], ux[i]}] = i;}dfs(1, -1, 1);cout << ans << endl;for(int i = 1; i < n; i ++){mp[{ux[i], vx[i]}] = 0;mp[{vx[i], ux[i]}] = 0;}
}signed main()
{IOS;cin >> _;while(_--)solve();return 0;
}

D

题意：给你两个长度为n的数组a，b。现问你 $\le i < j \le n \ \ , \ a_i*a_j = b_i + b_j$ 满足这样条件的(i, j)有多少。

思路：这道题其实最开始就想出是 $n^2$ ，那肯定是不现实的，那么我们最主要的是降低时间复杂度。赛时没注意看a，b的大小。（肯定看了也不一定写出来）。因为 $\le n$ 的，所以 $\le2n$ ，那么对于同一个a[i]，我们其实不用遍历a[j]， $\in [\frac{b[i]}{a[i]}, \frac{n+b[i]}{a[i]}]$ ，然后当a[i], a[j], b[i]都确定过后我们只需要求出(a[j], b[j])的数量就行了。因为我们上述提到了范围这个问题，那么如果我们排完序过后，a[i]从小到大，那么 $\in [1, \sqrt{2*n}]$ 那么我们这样处理就避免因为数据而出现时间复杂度不一样的问题。而我们最终的时间复杂度也就成了 $\sqrt{2*n}*n$ 了。
D题参考链接: link

代码：

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long 
#define endl "\n"
#define xx first
#define yy secondusing namespace std;typedef pair<int, int> PII;const int N = 2e5 + 10;int n, m, k, _;
int arr[N];
PII crr[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> arr[i];for(int i = 1; i <= n; i ++){int b;cin >> b;crr[i] = {arr[i], b};}sort(crr+1, crr+1+n);int ans = 0;for(int sum = 1; sum*sum <= 2*n; sum++){vector<int> cnt(n+1, 0);for(int i = 1; i <= n; i ++){int a = crr[i].xx , b = crr[i].yy;int t = a*sum-b;if(t >= 1 && t <= n) ans += cnt[t];if(sum == a) cnt[b]++;} }cout << ans << endl;
}signed main()
{IOS;cin >> _;while(_--) solve();return 0;
}