[ICPC2019上海D] Spanning Tree Removal

[ICPC2019上海D] Spanning Tree Removal - 构造

Description

给定一个 n 个节点的完全图，每次删掉一棵生成树，问最多能够删除几次。输出删除的方案。

Solution

我们发现一种模式，比如在 n=8 的情况构造 4-5-3-6-2-7-1-8 这样，然后循环移位 n/2 次

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    int ans = n / 2;
    cout << ans << endl;
    for (int i = ans; i >= 1; i--)
    {
        int pos = i;
        vector<int> vec;
        for (int j = 1; j <= n; j++)
        {
            vec.push_back(((pos - 1) % n + n) % n + 1);
            if (j & 1)
                pos += j;
            else
                pos -= j;
        }
        for (int j = 1; j < n; j++)
            cout << vec[j - 1] << " " << vec[j] << endl;
    }
}

signed main()
{
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}