Znzryb's Blog
0%

CF-1077-D. Shortest Statement Ever（没招的时候可以尝试尝试 dp）（高位起到决定性作用）

Posted on Edited on

题目大意

给定两个非负整数 xx，yy。找到两个非负整数pp和qq，使得p  &  q=0p\;\&\;q=0，且∣x−p∣+∣y−q∣|x-p|+|y-q|最小化。这里，&\&表示按位与操作。

You are given two non-negative integers xx, yy. Find two non-negative integers pp and qq such that p  &  q=0p\;\&\;q=0, and ∣x−p∣+∣y−q∣|x-p|+|y-q| is minimized. Here, &\& denotes the bitwise AND operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The only line of each test case contains two non-negative integers xx and yy (0≤x,y<2300 \le x,y < 2^{30}).

Output

For each test case, output two non-negative integers pp and qq you found. If there are multiple pairs of pp and qq satisfying the conditions, you may output any of them.

It can be proven that under the constraints of the problem, any valid solution satisfies max⁡(p,q)<231\max(p,q)<2^{31}.

1
2
3
4
5
6
7
8
7
0 0
1 1
3 6
7 11
4 4
123 321
1073741823 1073741822
1
2
3
4
5
6
7
0 0
2 1
3 8
6 9
4 3
128 321
1073741824 1073741822

Note

In the first test case, one valid pair would be p=0p=0 and q=0q=0, as 0 & 0=00\,\&\,0=0 and ∣x−p∣+∣y−q∣=∣0−0∣+∣0−0∣=0|x-p|+|y-q|=|0-0|+|0-0|=0 is the minimum over all pairs of pp and qq.

In the third test case, one valid pair would be p=3p=3 and q=8q=8, as 3 & 8=03\,\&\,8=0 and ∣x−p∣+∣y−q∣=∣3−3∣+∣8−6∣=2|x-p|+|y-q|=|3-3|+|8-6|=2 is the minimum over all pairs of pp and qq. Note that (p,q)=(3,4)(p,q)=(3,4) is also a valid pair.

思路讲解

我们需要利用这个高位较优的这个特性，

我们设计了一个 dp，dpi,0dp_{i,0} 表示该位采用 0,00,0 的配置，dpi,1dp_{i,1} 表示该位采用 1,01,0 的配置，dpi,2dp_{i,2} 表示该位采用 0,10,1 的配置。

不难写出这样的转移式子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector dp(40,vector<Diff_p_q>(3));
dp[36][0]=Diff_p_q(0,0);
dp[36][1]=Diff_p_q(1ll<<36,0);
dp[36][2]=Diff_p_q(0,1ll<<36);
for (int i=35;i>=0;--i) {
    dp[i]=dp[i+1];
    // dp[i][0]   自己重新开始     继承      继承       继承
    dp[i][0]=min({Diff_p_q(0,0),dp[i][0],dp[i+1][1],dp[i+1][2]});
    //             自己重新开始
    dp[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp[i+1][0].p+(1ll<<i),dp[i+1][0].q),
        Diff_p_q(dp[i+1][1].p+(1ll<<i),dp[i+1][1].q),
        Diff_p_q(dp[i+1][2].p+(1ll<<i),dp[i+1][2].q)});
    dp[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp[i+1][0].p,dp[i+1][0].q+(1ll<<i)),
        Diff_p_q(dp[i+1][1].p,dp[i+1][1].q+(1ll<<i)),
        Diff_p_q(dp[i+1][2].p,dp[i+1][2].q+(1ll<<i))});
}

然后你忐忑地提交了，结果 WA on 2。

你使用了对拍，或者其实你不需要使用对拍，你也知道，是因为上面的做法有一些激进，高位上比较好，那自然是比较好的，但是好分大的好和小的好。那么上面的做法，大的好，自然是可以得到的，但是小的好，就不是那么简单的可以得到的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_______________[ Testcase #1 INPUT ]_______________
1
78 88

_______________[ Testcase #1 OUTPUT]_______________
78 128
WA


[-] FAILURE: RUNTIME ERROR
Ans.diff:40
brute_diff:39
x_br:39
y_br:88

那么对拍也给了我们这个反馈，确实是这样的。

但是我们怎么样得到小的好呢？其实也简单，我们使用同样方法，整一个 dp，但是我们 dp 里存的的那个结构体的构造函数，我们传入一个指示参数，使得只要一出现大于的情况，就给他附上 diff←INFdiff\gets\text{INF}，使其不够优秀而被淘汰，强制得到这个我们所谓的小的好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Diff_p_q {
    ll diff,p,q;
    bool operator<(const Diff_p_q &o) const {
        return diff<o.diff;
    }
    Diff_p_q()=default;
    explicit Diff_p_q(ll p,ll q,bool no_big=false) {
        if (!no_big) {
            diff=abs(p-X)+abs(q-Y);
            this->p=p;
            this->q=q;
        }else {
            if (p > X || q > Y) {
                diff=INF;
            }else {
                diff=abs(p-X)+abs(q-Y);
            }
            this->p=p;
            this->q=q;
        }

    }
};

一样的 dp 过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Diff_p_q Ans=min({dp[0][0],dp[0][1],dp[0][2]});
{
    vector dp2(40,vector<Diff_p_q>(3));
    dp2[36][0]=Diff_p_q(0,0,true);
    dp2[36][1]=Diff_p_q(1ll<<36,0,true);
    dp2[36][2]=Diff_p_q(0,1ll<<36,true);
    for (int i=35;i>=0;--i) {
        dp2[i]=dp2[i+1];
        // dp[i][0]   自己重新开始     继承      继承       继承
        dp2[i][0]=min({Diff_p_q(0,0,true),dp2[i][0],dp2[i+1][1],dp2[i+1][2]});
        //             自己重新开始
        dp2[i][1]=min({Diff_p_q(1ll<<i,0,true),Diff_p_q(dp2[i+1][0].p+(1ll<<i),dp2[i+1][0].q,true),
            Diff_p_q(dp2[i+1][1].p+(1ll<<i),dp2[i+1][1].q,true),
            Diff_p_q(dp2[i+1][2].p+(1ll<<i),dp2[i+1][2].q,true)});
        dp2[i][2]=min({Diff_p_q(0,1ll<<i,true),Diff_p_q(dp2[i+1][0].p,dp2[i+1][0].q+(1ll<<i),true),
            Diff_p_q(dp2[i+1][1].p,dp2[i+1][1].q+(1ll<<i),true),
            Diff_p_q(dp2[i+1][2].p,dp2[i+1][2].q+(1ll<<i),true)});
    }
    Ans=min({Ans,dp2[0][0],dp2[0][1],dp2[0][2]});
}
cout<<Ans.p<<" "<<Ans.q<<"\n";

okay，上面我们已经把我们的思路讲的比较清楚了。

我感觉这个代码对是因为，在确定好高位以后，绝对值距离最小的数一定贴在区间边界：要么贴上边界（低位全 0），要么贴下边界（低位全 1）；中间形态永远不可能比边界更近。

不过我们的第一种 dp 由于没有引入这个 loose 和 tight，实际上计算出来的，并不是严格的 ≥≥，会有 << 的情况出现，所以我心里也不太踏实。欢迎 hack 我的代码。

AC代码

AC
https://codeforces.com/contest/2188/submission/360662700

心路历程（WA，TLE，MLE……）