Codeforces Round 832 (Div. 2) B. BAN BAN

给一个正整数 \(n\) ，定义 \(S{n}\) 为字符串 \(BAN\) 复制 \(n\) 次。比如 \(S(3) = BANBANBAN\) 。可以对 \(S(n)\) 执行任意次以下操作：

• 选择 \(i, j (1 \leq i, j \leq 3n, i \neq j)\) 。\(swap(s_i, s_j)\) 。

希望 \(BAN\) 不作为一个子序列出现在 \(S(n)\) 中，输出最小交换数，和每次的交换位置。

观察一：\(S(n) = BANBAN \cdots BAN\) 中，建立所有 \(B-A-N\) 的连接，则得到一个森林

观察二： \(B\) 可以作为森林中一颗树的根。越靠左的 \(B\) 可以得到的树越大。需要打破这些根，也就是 \(B\) 需要执行交换。

观察三：最优方案是反复让最大树和最小树互相打破。

• 证明：这可以严格保证每次的最大树和最小树永远有位置可以互相交换。而其他情况可能不能。

以上的观察为森林角度。

本题在序列角度的 trick：从一个序列的角度考虑，就是从两边删除，且被删除部分。不会对未删除部分造成影响。

于是每次让第一个 \(BAN\) 的 \(B\) 和最后一个 \(BAN\) 的 \(A\) 或 \(N\) 交换即可。

若 \(n\) 为奇数，最后剩下一个 \(BAN\) ，多执行一次任意交换即可。

前 \(x\) 个 \(BAN\) 的有 \(3x\) 个字符；第 \(x\) 个 \(BAN\) 的第 \(k\) 个字符为 \(3(x-1) + k\) 。

#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<std::pair<int,int>> segs;
	for (int i = 1; i <= n / 2; i++) segs.push_back({(i - 1) * 3 + 1, (n - i) * 3 + 2});
	if (n & 1) { // n/2 * 3 + k
		segs.push_back({n/2*3+1,n/2*3+2});
	}
	int m = segs.size();
	std::cout << m << '\n';
	for (int i = 0; i < m; i++) {
		std::cout << segs[i].first << ' ' << segs[i].second << '\n';
	}
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}