【题解】[COCI2019-2020#3] Sob

7KByte · 2021-06-20 16:56:04 · 题解

首先题目已经给出了结论，就是对于任意 N,M 均有解。

所以如果 A 中后 x 个数和 B 中前 x 个数两两配对，就可以转化为 N-x,M+x 的子问题。

所以对于 A 中最后一个数 n-1 ，在 B 中至少存在一个数 x 使得 x\ \&\ (n-1) = n-1 。我们只记录 B 中最小的 x 。

关键结论：\forall k\in[0,x-m]\ ,\ (x-k)\ \&\ (n-1-k)=(n-1-k) 。

说人话，就是将 A 后面这一段和 B 前面这一段按顺序两两配对一定是合法解。

感性理解以下，因为在 [m,x) 区间内的数和 n-1 配对都不合法，而 x 是第一个合法的，所以 x 和 n-1 最后几位相同，而这包括了区间 [m,x] 。

理性分析以下，我们令 n-1 中为 1 ，而 m 中为 0 的最高位为第 i 位，那么枚举 x 的过程就是将最低的 i 位一直加到后 i 位和 n-1 完全相同。那么再减回去也一定完全相同。

#include<cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=n-1,j=m;~i;){
        int k=j;
        while((k&i)!=i)k++;
        rep(r,0,k-j)printf("%d %d\n",i--,k-r);
        j=k+1;
    }return 0;
}