P9573 「TAOI-2」核心共振题解

Svemit / 2023-08-21 / 原文

~~这能评黄？~~

原题链接

题意：

题面就挺简要的。

Solution：

注意到最大的两个数加起来是 \(n + n - 1 = 2n - 1\)，如果 \(p\) 大于这个数时直接乱输出即可。

构造一个排列，让共振的次数最多。显然我们需要尽可能多的让两个数和起来是 \(p\) 的倍数的挨在一起，而两个数加起来是否能整除 \(p\) 只与他们对 \(p\) 取模后的数有关，两个数对 \(p\) 取模后加起来的和是 \(p\) 或者 \(0\) 时加起来就一定是 \(p\) 的倍数，我们不妨将所有数先对 \(p\) 取模。

先把对 \(p\) 取模后和为 \(0\) 的输出，然后把和为 \(p\) 的分一组交错输出。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
void solve() {
	int n, p;
	cin >> n >> p;
	if(p > n * 2 - 1) {
		for(int i = 1;  i <= n; i ++) cout << i << '\n';
	}
	else {
		vector<vector<int> > q(p);
		for(int i = 1; i <= n; i ++) {
			q[i % p].push_back(i);
		}
		for(auto v : q[0]) {
			cout << v << ' ';
		}
		int l = 1, r = p - 1;
		while(l <= r) {
			if(l == r) {
				for(auto v : q[l]) {
					cout << v << ' ';
				}
			}
			else {
				int i = 0, j = 0;
				while(i < q[l].size() && j < q[r].size()) {
					cout << q[l][i] << ' ' << q[r][j] << ' ';
					i ++, j ++;
				}
				while(i < q[l].size()) {
					cout << q[l][i] << ' ';
					i ++;
				}
				while(j < q[r].size()) {
					cout << q[r][j] << ' ';
					j ++;
				}
			}
			l ++, r --;
		}
	}
	cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int t;
	cin >> t;
	while(t --) {
		solve();
	}
    return 0;
}