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