A.

模拟题。

B.

枚举删除哪个数字。

C.

枚举前两个数字或者 dp。

D.

考虑固定根的情况，然后换根就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void solve(){
	int N;
	cin >> N;
	vector<ll> A(N);
	for(ll& x : A) cin >> x;
	vector<vector<int> > tree(N);
	for(int i = 0; i < N-1; i++){
		int u, v;
		cin >> u >> v;
		u--; v--;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	vector<ll> ans(N);
	vector<ll> ssz(N);
	vector<int> par(N);
	y_combinator(
		[&](auto self, int v, int p) -> void {
			ssz[v] = 1;
			par[v] = p;
			for(int w : tree[v]){
				if(w == p) continue;
				self(w, v);
				ssz[v] += ssz[w];
			}
		}
	)(0, -1);
	ll root_ans = 0;
	for(int v = 1; v < N; v++){
		root_ans += ssz[v] * (A[v] ^ A[par[v]]);
	}
	y_combinator(
		[&](auto self, int v, int p, ll cur_ans) -> void {
			ans[v] = cur_ans;
			for(int w : tree[v]){
				if(w == p) continue;
				ll new_ans = cur_ans + (N - ssz[w] - ssz[w]) * (A[v] ^ A[w]);
				self(w, v, new_ans);
			}
		}
	)(0, -1, root_ans);
	for(int i = 0; i < N; i++){
		cout << ans[i] << " \n"[i == N-1];
	}
}

E.

观察到，我们可以在序列前面添加一个 0，然后序列的样子就是从 0 开始读一圈，然后一次操作等价于 0 和非0 元素的交换。

从这个观察可以得到三次交换两个元素的做法，从而构造出来了单个序列的方案。

E1 可以构造出来两个序列的操作方案。

  • 如果操作个数奇偶性一样，就可以反复横跳 1 和 N。
  • 如果奇偶性不一样，可以考虑对第一个序列使用 N 次 1 或者对第二个序列使用 M 次 1 来调整奇偶性，如果 N M 都是偶数，那么无解。

由此构造出了 $4 \max{n, m}$ 的做法，可以通过 $E1$。

E2，通过观察，可以发现答案一定在 $[i…N,0…i-1]$ 这种目标序列里面取到，$i \in [0,N]$。

然后枚举奇偶性，枚举是哪个目标序列，枚举 $i$，然后判断是否可行/反复横跳，就做完了。感觉还是比较好写的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
using namespace std;
const int INF = 1e9;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<int> sz(2);
  rep(i, 2) { cin >> sz[i]; }
  vector<vector<int>> perms(2);
  rep(i, 2) {
    perms[i].resize(sz[i]);
    for (auto &x : perms[i]) {
      cin >> x;
    }
    perms[i].insert(perms[i].begin(), 0);
  }
  vector<vector<int>> parity_best(2, {-1});
  int best_score = INF;
  rep(par, 2) {
    vector<vector<int>> best(2, {-1});
    rep(x, 2) {
      int N = perms[x].size();
      vector<int> goal(N);
      iota(goal.begin(), goal.end(), 0);

      rep(z, N) {
        vector<int> loc(N);
        vector<int> cur = perms[x];
        // loc_i is the position where value = i
        rep(i, N) { loc[cur[i]] = i; }
        vector<int> ops;
        auto swp = [&](int a, int b) {
          assert(a == loc[0]);
          ops.push_back((b - a + N) % N);
          swap(loc[cur[a]], loc[cur[b]]);
          swap(cur[a], cur[b]);
        };
        while (goal[loc[0]] != 0) {
          int a = loc[0];
          int b = loc[goal[a]];
          swp(a, b);
        }
        int ct = 0;
        while (ct < N) {
          if (cur[ct] == goal[ct]) {
            ct++;
            continue;
          }
          if (ct != loc[0]) {
            swp(loc[0], ct);
          }
          while (goal[loc[0]] != 0) {
            int a = loc[0];
            int b = loc[goal[a]];
            swp(a, b);
          }
        }
        if (ops.size() % 2 == par) {
          if (best[x] == vector<int>{-1} || ops.size() < best[x].size()) {
            best[x] = ops;
          }
        }
        rotate(goal.begin(), goal.begin() + 1, goal.end());
      }
    }
    if (best[0] == vector{-1}) {
      continue;
    }
    if (best[1] == vector{-1}) {
      continue;
    }
    rep(x, 2) {
      while (best[x].size() < best[!x].size()) {
        int N = perms[x].size();
        best[x].push_back(1);
        best[x].push_back(N - 1);
      }
    }
    int score = max(best[0].size(), best[1].size());
    if (score < best_score) {
      best_score = score;
      parity_best = best;
    }
  }

  if (best_score == INF) {
    cout << -1 << "\n";
    return 0;
  }
  cout << parity_best[0].size() << "\n";
  rep(i, parity_best[0].size()) {
    cout << parity_best[0][i] << " " << parity_best[1][i] << "\n";
  }
}