# Codeforces Round 875 (Div. 2) 题解 A ~ D

## A. Twin Permutations

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
cout << n - x + 1 << " ";
}
cout << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## B. Array merging

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

int a[N], b[N];

void solve() {
int n;
cin >> n;
vector<int> c1(n * 2 + 1), c2(n * 2 + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] != a[i - 1]) {
c1[a[i - 1]] = max(c1[a[i - 1]], cnt1);
cnt1 = 1;
} else {
cnt1++;
}
if (b[i] != b[i - 1]) {
c2[b[i - 1]] = max(c2[b[i - 1]], cnt2);
cnt2 = 1;
} else {
cnt2++;
}
}
c1[a[n]] = max(c1[a[n]], cnt1);
c2[b[n]] = max(c2[b[n]], cnt2);
LL res = 0;
for (int i = 1; i <= (n << 1); ++i) {
res = max(res, (LL)c1[i] + c2[i]);
}
cout << res << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## C. Copil Copac Draws Trees

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

int h[N], e[N], ne[N], idx, fore[N];
LL cnt[N];
bool vis[N];

void add(int a, int b, int id) {
e[idx] = b;
ne[idx] = h[a];
fore[idx] = id;
h[a] = idx++;
}

void dfs(int u, int id) {
vis[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
if (!vis[e[i]]) {
cnt[e[i]] = cnt[u] + (fore[i] < id);
dfs(e[i], fore[i]);
}
}
}

void solve() {
int n;
cin >> n;
idx = 0;
memset(h, -1, sizeof h);
memset(vis, 0, sizeof vis);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
}
dfs(1, 0x3f3f3f3f);
cout << *max_element(cnt + 1, cnt + n + 1) << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````

## D. The BOSS Can Count Pairs

### AC Code

``````#include <iostream>
#include <algorithm>
#include <cstring>
#define endl "
"
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

int cnt[N];
pair<int, int> p[N];

void solve() {
int n;
cin >> n;
LL res = 0;

for (int i = 1; i <= n; ++i) {
cin >> p[i].first;
}
for (int i = 1; i <= n; ++i) {
cin >> p[i].second;
}
sort(p + 1, p + n + 1);
for (int i = 1; i * i <= (n << 1); ++i) {
memset(cnt, 0, sizeof cnt);
for (int j = 1; j <= n; ++j) {
int cal = p[j].first * i - p[j].second;
if (cal >= 1 && cal <= n) {
res += cnt[cal];
}
if (p[j].first == i) {
cnt[p[j].second]++;
}
}
}
cout << res << endl;
}

signed main() {
ios;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
``````