CF1408F Two Different

    科技2024-12-24  3

    题面传送门 一道好题。 首先有一个操作:如果有 n n n a a a, n n n b b b,那么可以通过 n n n次变成 2 n 2n 2n c c c 那么考虑倍增,每次选取两块拿来合并。 然后对于前一部分和后一部分分别倍增就好了。 代码实现:

    #include<cstdio> using namespace std; int n,m,k,z,a[100039],s,head,x[1000039],y[1000039]; int main(){ // freopen("1.in","r",stdin); register int i,j; scanf("%d",&n); for(i=0;i<=30;i++) if(n<=(1<<i)) {k=i;break;} k--; for(i=1;i<=k;i++){ for(j=1;j<=(1<<k);j++) if(!((j-1)&(1<<i-1))) x[++head]=j,y[head]=j+(1<<i-1); } for(i=1;i<=k;i++){ for(j=1;j<=(1<<k);j++) if(!((j-1)&(1<<i-1))) x[++head]=n-j+1,y[head]=n-j+1-(1<<i-1); } printf("%d\n",head); for(i=1;i<=head;i++) printf("%d %d\n",x[i],y[i]); }
    Processed: 0.076, SQL: 8