ZigZagK的博客
[倍增]Codeforces1408F【Two Different】题解
ZigZagK
2020年10月3日 16:01
Codeforces
查看标签

题目概述

CF1408F

解题报告

我们可以把 $2$ 个不同的变成相同的，$4$ 个不同的先变成 $2$ 个不同的，再变成相同的。以此类推，$2^k$ 个不同的可以变成相同的，需要的次数是 $O(2^kk)$ 。

但是 $n$ 不一定是 $2^k$ 的形式，由于题目要求我们变成至多两个不同的，我们可以将 $n$ 拆成两个可能重叠的部分，每部分的个数是 $2^k$ 的形式，做两次上述操作就行了。

示例程序

#include<cstdio>
using namespace std;
const int maxn=150000,maxm=500000;

int n,N,m,A[maxm+5],B[maxm+5],ti,vis[maxn+5];

int main(){
    scanf("%d",&n);N=1;while (N<n) N<<=1;N>>=1;
    for (int j=1;j<N;j<<=1)
        for (int i=1;i<N;i+=j<<1)
            for (int k=0;k<j;k++)
                m++,A[m]=i+k,B[m]=i+k+j;
    for (int j=1;j<N;j<<=1)
        for (int i=1;i<N;i+=j<<1)
            for (int k=0;k<j;k++)
                m++,A[m]=n-N+i+k,B[m]=n-N+i+k+j;
    printf("%d\n",m);for (int i=1;i<=m;i++) printf("%d %d\n",A[i],B[i]);return 0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！