Product of Closures

· · 题解

有点好玩。但是做了 1.5h，我是区。

要求的是字典序最小，那越高的位就要越小。由定义知 C(x) 的开头一定是 1，我们想让第二个 1 出现的位置越晚越好，那最理想的策略就是让 x 取 [l,r] 内最大的二的幂次（当然有可能取不到，后面会讲）。

假设 x 取到了这个幂次（记为 2^k），我们还要再取一个 y，使 C(x)\,\&\,C(y) 的字典序最小。经过一些手玩，我们发现取 y=2^{k-1} 总是最优的（当然还是有可能取不到，后面也会讲）。这个不太好严格证明，让我们结合一个例子来感性理解。

例如 l=1，r=10，根据上述策略，我们会取 x=8，y=4，此时 C(x)=100010001000\dots，C(y)=100100100100\dots，C(x)\,\&\,C(y) 计算如下：

\begin{array}{r} \begin{array}{r} C(16)\\ C(8)\\ \end{array} \mathop{\&} \begin{array}{r} 1000100010001000\dots\\ 1001001001001001\dots\\ \end{array} \\ \hline \begin{array}{r} 1000000000001000\dots \end{array} \end{array}

我们发现，对于 x 中从左至右的每个 1，y 中与它对齐的那一位每次都会偏移。当且仅当 y 取 2^{k-1} 时，每次只偏移一位，那么 1 与 1 对齐的时刻就越晚，字典序也就越小。

这样我们就解决了 [l,r] 中至少可以取到两个二的次幂的情况。现在考虑取不到的情况，分为两种。

第一种，只有一个二的次幂可以取（记为 2^k）。此时 x=2^k 是肯定要取上的，考虑 y 怎么取。依旧感性理解，已知 [l,x) 内所有数二进制下的位数相等，那么 y 取得越小，1 的位置就越靠后，字典序就越小。故我们取 y=l（若 l=2^k 则取 y=l+1）。

第二种，没有任何二的次幂可以取。此时 [l,r] 内所有数二进制下的位数都相等，问题等价于选出 x,y 使 x\,\&\,y 的字典序最小。那么 x=l 肯定要取，我们还可以取一个 y 来消去 x 末尾的尽可能多的 1，同时要保证 y>x。那么我们找到 r 二进制下与 l 不同的最高位，将这一位右边的所有位全部清零，得到 y。

做完了。很多结论我没有严格证明，建议自己多手玩几个例子来理解。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
void output(int a, int b, int n){
    int lena = __lg(a) + 1, lenb = __lg(b) + 1;
    for (int i = 0; i < n; i++){
        int da = (a >> (lena - i % lena - 1) & 1);
        int db = (b >> (lenb - i % lenb - 1) & 1);
        cout << (da & db);
    }
    cout << "\n";
    return;
}
void solve(){
    int l, r, n;
    cin >> l >> r >> n;
    int k;
    for (k = 0; (1 << (k + 1)) <= r; k++);
    int a = (1 << k), b = (1 << (k - 1));
    if (a >= l && b >= l){
        output(a, b, n);
    }
    else if (a >= l){
        b = (a == l ? l + 1 : l);
        output(a, b, n);
    }
    else{
        a = l;
        int p = __lg(l ^ r);
        b = (r >> p) << p;
        output(a, b, n);
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::