CF1408F Two Different 题解

题意：

你被给定一个整数 \(n\)。

你应该找到满足以下条件的一组配对列表 \((x_1, y_1)\)，\((x_2, y_2)\)，...，\((x_q, y_q)\) （\(1 \leq x_i, y_i \leq n\)）。

让我们考虑某个函数 \(f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) （我们定义 \(\mathbb{N}\) 为正整数集）。换句话说，\(f\) 是一个为一对正整数返回正整数的函数。

让我们创建一个数组 \(a_1, a_2, \ldots, a_n\)，其中 \(a_i = i\) 初始值。

你将执行 \(q\) 次操作，第 \(i\) 次操作中你将：

赋值 \(t = f(a_{x_i}, a_{y_i})\) （\(t\) 是一个临时变量，仅用于接下来的两个赋值）;

赋值 \(a_{x_i} = t\);

赋值 \(a_{y_i} = t\)。

换句话说，你需要同时将 \(a_{x_i}\) 和 \(a_{y_i}\) 更改为 \(f(a_{x_i}, a_{y_i})\)。请注意，在此过程中，对于一对固定的 \(p\) 和 \(q\)，\(f(p, q)\) 始终相同。

最后，在数组 \(a\) 中最多应存在两个不同的数字。

对于任何函数 \(f\)，上述条件应成立。

找到任何可能的配对列表。配对数不应超过 \(5 \times 10^5\)。

输入格式：

单行包含一个整数 \(n\)（\(1 \leq n \leq 15,000\)）。

输出格式：

在第一行打印 \(q\) （\(0 \leq q \leq 5 \times 10^5\)）— 配对数。

在接下来的 \(q\) 行中，每行打印两个整数。第 \(i\) 行打印 \(x_i\), \(y_i\)（\(1 \leq x_i, y_i \leq n\)）。

应满足陈述中描述的条件。

如果存在多个答案，则可以打印任何一个。

本题就是一个结论题。对于偶数 \(n\) 我们可以做以下操作

1 2 3 4 5 6
a 2 3 a 5 6
a b 3 a b 6
a c c a c c

对于奇数 \(n\) 稍微特殊一些。我们找到最大的 \(k\) 满足 \(2^k \le n\) ，例如 \(n=7\) 时

1 2 3 4 5 6 7
a a 3 4 5 6 7
a a b b 5 6 7

然后我们需要把前面 \(2^k\) 个数全部变成一样的

c a c b 5 6 7
c c c c 5 6 7
c c c d d 6 7
c c c d d e e
c c c f d f e
c c c f f f f

然后对于偶数情况显然是可以递归的，那么这题就解决了

时间复杂度 \(\mathcal{O}(n \log n)\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int n, tot, lg[N]; pii ans[N];
void solve(int l, int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1; solve(l, mid); solve(mid + 1, r);
    for(int i = l; i <= mid; i++) ans[++tot] = make_pair(i, i - l + mid + 1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; lg[1] = 0;
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    solve(1, (1 << lg[n]));
    if((1 << lg[n]) < n) solve(n - (1 << lg[n]) + 1, n);
    cout << tot << '\n';
    for(int i = 1; i <= tot; i++)   
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    return 0;
}