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

· · 个人记录

这能评黄？

原题链接

题意：

题面就挺简要的。

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;
}