题解：P7207 [COCI 2019/2020 #3] Sob

· · 题解

P7207

题目描述

两个集合 A=\{0,1,2,\cdots,N-1\} 和 B=\{M,\cdots,M+N-1\}，从中选出 N 对互不重复的 x,y 使得 x\&y=x。

做法概括

令 i=N，j_{l}=M，找到 j_{l} 之后第一个 y_{j_{n}} \& x_i=x_i。

令 n=j_{n}-j_{l} ，将 x_{i_l-n} 至 x_{i_l} 与 y_{j_l} 至 y_{j_n} 顺序对应，重复此操作。

做法正确性分析

为什么可以保证进行操作后的集合仍有解？

在操作后，假设拿掉了 A 集合后 k 个元素和 B 集合前 k 个元素。

由于题目说明了当 A=\{0,1,2,\cdots,N-1\} 和 B=\{M,\cdots,M+N-1\} 时，必然有解，故剩下的集合也必然有解。

为什么在操作时可以进行顺序匹配？

在寻找 y_j 时，中间跳过的 y_j \& x \neq x，说明这些 y 与 x 在二进制上至少有一位匹配不上。

设 y_j 第 u 位是第一位匹配不上的。所以当 y_{j_n} 与 x 匹配上时，后 u 位完全相同。

所以 A 中前 k 个也能与 B 中前 k 个对应上。

又因为不会发生二进制退位的情况，即 k+1 \leq x \bmod 2^u。

若 n+1=x \bmod 2^u+1，则 y_j \bmod 2^u=2^u-1，不可能出现第 u 位无法匹配的情况。

因此这 n 位可以一一匹配。

为什么在 B 中总能找到 y 使得 y\&N=N？

设 x 在二进制下共 n 位。

易发现：(2^n-1)\&x=x，x\&x=x。

令 y 二进制的后 n 位的十进制数字 z=y\bmod 2^n，有 y\&x=z\&x。

若 z < x，这区间[z,z+x] 包含 x。

若 z \geq x，这区间[z,z+x] 包含 2^n-1。

故在 y 中必能找到 z\&x=x。

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
stack<pair<int,int>>stk;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int i=n-1,j=m,lastj=j;
    while(j<=m+n-1){
        if((j&i)!=i) j++;
        else{
            for(int v=j;v>=lastj;v--) stk.push({i--,v});
            lastj=j+1;
            j++;
        }
    }
    while(!stk.empty()) cout<<stk.top().first<<" "<<stk.top().second<<"\n",stk.pop();
    return 0;
}

upd:

2025/11/4: 修改了笔误。