题解 CF1408F 【Two Different】

s_r_f · 2020-10-02 20:52:24 · 题解

难写的做法

一开始 n 个数互不相等，我们把这个局面记为 n 个大小为 1 的下标集合。

不难发现，我们可以做以下两种操作：

1、花费 n 次操作的代价，把两个大小为 n 的集合合并为一个大小为 2n 的集合，这个下标集合内所有下标对应的数仍然是全相等的。

2、花费 0 次操作，分裂两个下标集合。

那我们只需要合并到最后只有两个集合即可。

考虑二进制合并，然后剩下 \Theta(\log n) 个集合，其中最大的集合大小大于 n 的一半。

然后利用最大的集合，把其它集合一一合并起来，这样就只剩两个集合了。

实际测试中对于 n = 15000 的情况只需要 100068 次操作 。

code 见我的提交

好写的做法

还有一种做法，先求出 k 满足 2^{k+1} \geq n , 然后直接做两次,先使前 2^k 个数变为相等的，再让后 2^k 个数变为相等的即可，操作数比我当场写的做法多一点，但是很好写。

code ：

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
int ansx[500005],ansy[500005],lans;
inline void print(){
    write(lans),putchar('\n');
    for (int i = 1; i <= lans; ++i) write(ansx[i]),putchar(' '),write(ansy[i]),putchar('\n'); 
    exit(0); 
}
inline void add(int x,int y){ ++lans; ansx[lans] = x; ansy[lans] = y; }
inline void solve(int l,int r){
    if (l == r) return; if (l+1 == r){ add(l,r); return; }
    int mid = l+r>>1,i,j; solve(l,mid),solve(mid+1,r);
    for (i = l,j = mid+1; i <= mid; ++i,++j) add(i,j);
}
int main(){ int n,m; read(n),m = 1; while (m<<1 < n) m <<= 1; solve(1,m),solve(n-m+1,n),print(); return 0; }