题解 CF1408F 【Two Different】

· · 题解

真的没有人写题解。。。我来写一篇吧。

显然这是一道构造题，我们先来看小范围。

n=3 和 n=4 已经在样例中给了，我先做的是 n=5。

其实，n=5 可以这么做：

abcde->ffcde->ffgge->hfhge->hhhhe

同理，n=6 也可以。

但是 n=7 就不行了，于是我们采用另一种做法：

abcdefg->hhcdefg->hhiiefg->jhjiefg->jjjjefg->jjjkkfg->jjjkkll->jjjmkml->jjjmmmm

所以说，其实这道题做法是这样的：

1) 找到一个最大的 k，使得 2^k \leq n。

2) 处理前一部分 (1,2^k)

3) 处理后一部分 (n-2^k+1,n)

那么如何处理呢？显然可以递归处理：

solve(1,8)->bbbbcccc（递归之后的答案）->dbbbdccc->ddbbddcc->dddbdddc->dddddddd

最后发一下代码：

#include<bits/stdc++.h>
using namespace std;
struct apple
{
    int l,r;
    apple(int l=0,int r=0):l(l),r(r){}
}ans[1000005];
int n,tot=0,lg[1000005];
void gds(int l,int r)
{
    if(l==r)return;
    int mid=l+r>>1;
    gds(l,mid);
    gds(mid+1,r);
    for(int i=l;i<=mid;i++)ans[++tot]=apple(i,i-l+mid+1);
}
int main()
{
    lg[1]=1;
    for(int i=2;i<=1000000;i++)lg[i]=lg[i>>1]<<1;
    int n;
    cin>>n;
    gds(1,lg[n]);
    gds(n-lg[n]+1,n);
    cout<<tot<<endl;
    for(int i=1;i<=tot;i++)printf("%d %d\n",ans[i].l,ans[i].r);
    return 0;
}