526互联

Codeforces Round 865 (Div. 2) B. Grid Reconstruction

发布时间 2023-10-20 17:30:40作者: zsxuan

给一个 \(2 \times n\) 的网格，且 \(n\) 是偶数。你需要将 \(1 \sim 2 \times n\) 填入这个网格。

一条路径是从 \((1, 1)\) 开始，每次只能向右或向下，到 \((2, n)\) 结束时，所经过的位置。按经过点的顺序标号，一两条路径的代价是 \(cost = a_1 - a_2 + a_3 - a_4 + \cdots = \sum_{i=1}^{k} (-1)^{i + 1} a_i\) 。

你需要构造一个网络，使得所有路径的最小代价最大。

几个观察：

  • 一条路径由第一行的一段前缀和第二行的一段后缀构成，\(x \in [1, n]\) ， \(path = pre_x + suf_x\) 。
  • 对于一条路径，奇数位置上的数是正贡献，偶数位置上的数是负贡献。扩展到网格上则有，\(i + j\) 为偶数的数的贡献为正，\(i + j\) 为奇数的数的贡献为负
    • 于是 \(i + j\) 为偶数的位置上填 \(n + 1 \sim 2n\) ，\(i + j\) 为奇数的位置上填 \(1 \sim n\) 。
  • 由于 \(n\) 为偶数 \((1, 1)\) 和 \((2, n)\) 一定有正贡献。
  • 路径的最小代价最大——即每条路径代价尽可能相等。

由于所有路径的贡献需要尽可能相等，不妨观察所有相邻路径的变化情况。

  • \(x = 1 \rightarrow x = 2\) ，\(cost = cost + a_{2, 1} - a_{1, 2}\) 。
  • \(x = 2 \rightarrow x = 3\) ，\(cost = cost - a_{2, 2} + a_{1, 3}\) 。
  • \(x = 3 \rightarrow x = 4\) ，\(cost = cost + a_{2, 3} - a_{1, 4}\) 。
  • \(\cdots\)

于是让每条路径变化的差值为 \(1, -1, 1, -1, \cdots\) 交替即可使所有路径尽可能相等。

于是一种构造方式为

  • \(a_{2, 1}, a_{1, 2}, a_{2, 3}, a_{1, 4}, \cdots a_{2, n-1}, a_{1, n} = 1, 2, 3, 4, \cdots, n-1, n\) 。
  • 一定在路径中的 \((1, 1), (2, n) = 2n, 2n - 1\) 。
  • \(a_{2, 2}, a_{1,3}, \cdots, a_{2, n - 2}, a_{1, n} = n+1, n+2, \cdots, 2n-3,2n-2\) 。
view 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int g[2][100005];
void solve(){
	int n; std::cin >> n;
	g[0][1] = 2 * n; g[1][n] = 2 * n - 1;
	for (int i = 1, p = 1, cur = 1; i <= n; i++, p ^= 1, cur++) {
		g[p][i] = cur;
	}
	for (int i = 2, p = 1, cur = n + 1; i < n; i++, p ^= 1, cur++) {
		g[p][i] = cur;
	}
	for (int i = 1; i <= n; i++) std::cout << g[0][i] << " \n"[i==n];
	for (int i = 1; i <= n; i++) std::cout << g[1][i] << " \n"[i==n];
}               
int main() { 
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}