CF 1474E What Is It?

• 构造出一个 \(1...n\le 10^5\) 的排列，每次可以选择位置 \((i,j)\)，满足 \(a_j = i\)，交换 \(a_i,a_j\)，代价为 \((i - j)^2\)，求出最大代价。

考虑倒着模拟这个过程，有一个序列 \(a_i = i\)，每次可以选择位置 \((i, j)\)，满足 \(a_i = i\)，交换 \(a_i,a_j\)，求出最大代价。

每次操作会使 \(a_i = i\) 的个数减少 \(1\)，除去第一次操作减少 \(2\)。那么最大可以操作 \(n - 1\) 次。

显然第一次操作 \((1,n)\)，然后每个 \(2...n-1\) 都会作为 \(a_i = i\) 进行操作，那么选择最远的点 \(1\) 或者 \(n\) 操作即可。

注意答案要倒着输出。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
using namespace std;

typedef long long LL;
typedef pair <int, int> P;
const int inf = 0x3f3f3f3f, N = 3e5 + 10;
template <typename T>
void rd_(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if (ch == ‘-‘) f = -1;
	for (; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) x = x*10 + ch - ‘0‘;
	x *= f;
}

int T, n, p[N];
vector <P> g;
LL ans;

int main() {
	rd_(T);
	while (T--) {
		rd_(n), g.clear(), ans = 0;
		rep (i, 1, n) p[i] = i;
		swap(p[1], p[n]), ans += 1ll*(n - 1)*(n - 1);
		g.push_back(P(1, n));
		rep (i, 2, n/2) {
			swap(p[i], p[n]), g.push_back(P(i, n)), ans += 1ll*(n - i)*(n - i);
			swap(p[n - i + 1], p[1]), g.push_back(P(n - i + 1, 1)), ans += 1ll*(n - i)*(n - i);
		}
		if (n&1) 
			swap(p[n/2 + 1], p[n]), g.push_back(P(n/2 + 1, n)), ans += 1ll*(n/2)*(n/2);
		printf("%lld\n", ans);
		rep (i, 1, n) printf("%d ", p[i]);
		puts("");
		printf("%d\n", n - 1);
		per (i, n - 2, 0)
			printf("%d %d\n", g[i].fi, g[i].se);
	}
}

CF 1474E What Is It?

原文：https://www.cnblogs.com/ympc2005/p/14310534.html