CF-1077-D. Shortest Statement Ever（没招的时候可以尝试尝试 dp）（高位起到决定性作用） · znzryb
## 题目大意
给定两个非负整数 $x$，$y$。找到两个非负整数$p$和$q$，使得$p\;\&\;q=0$，且$|x-p|+|y-q|$最小化。这里，$\&$表示[按位与操作](https://en.wikipedia.org/wiki/Bitwise_operation#AND)。
You are given two non-negative integers $x$, $y$. Find two non-negative integers $p$ and $q$ such that $p\;\&\;q=0$, and $|x-p|+|y-q|$ is minimized. Here, $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).
**Input**
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The only line of each test case contains two non-negative integers $x$ and $y$ ($0 \le x,y < 2^{30}$).
**Output**
For each test case, output two non-negative integers $p$ and $q$ you found. If there are multiple pairs of $p$ and $q$ 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)<2^{31}$.
```cpp
7
0 0
1 1
3 6
7 11
4 4
123 321
1073741823 1073741822
```
```cpp
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=0$ and $q=0$, as $0\,\&\,0=0$ and $|x-p|+|y-q|=|0-0|+|0-0|=0$ is the minimum over all pairs of $p$ and $q$.
In the third test case, one valid pair would be $p=3$ and $q=8$, as $3\,\&\,8=0$ and $|x-p|+|y-q|=|3-3|+|8-6|=2$ is the minimum over all pairs of $p$ and $q$. Note that $(p,q)=(3,4)$ is also a valid pair.
## 思路讲解
我们需要利用这个高位较优的这个特性，
我们设计了一个 dp，$dp_{i,0}$ 表示该位采用 $0,0$ 的配置，$dp_{i,1}$ 表示该位采用 $1,0$ 的配置，$dp_{i,2}$ 表示该位采用 $0,1$ 的配置。
不难写出这样的转移式子：
```cpp
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。
你使用了对拍，或者其实你不需要使用对拍，你也知道，是因为上面的做法有一些激进，高位上比较好，那自然是比较好的，但是好**分大的好和小的好**。那么上面的做法，大的好，自然是可以得到的，但是小的好，就不是那么简单的可以得到的了。
```cpp
_______________[ 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\gets\text{INF}$，使其不够优秀而被淘汰，强制得到这个我们所谓的**小的好**。
```cpp
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 过程。
```cpp
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](https://codeforces.com/contest/2188/submission/360662700)
::: 源代码
```cpp
/**
* Problem: D. Shortest Statement Ever
* Contest: Codeforces Round 1077 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2188/problem/D
* Created: 2026-01-30 01:18:00
* Author: Gospel_rock
*/
#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <chrono>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
ll X,Y;
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;
}
}
};
void Solve() {
cin >> X >> Y;
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))});
}
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";
#ifdef LOCAL
if (X>100 || Y>100) {
return;
}
ll brute_diff=INF,x_br,y_br;
for (int i=0;i<=1000;++i) {
for (int j=0;j<=1000;++j) {
if ((i&j)==0) {
ll lans=abs(i-X)+abs(j-Y);
if (lans<=brute_diff) {
x_br=i;
y_br=j;
brute_diff=lans;
}
}
}
}
if (brute_diff==Ans.diff) {
return;
}
cout<<"WA\n";
debug(Ans.diff);
debug(brute_diff);
debug(x_br);
debug(y_br);
#endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2188/submission/360662700
_______________[ Stress test, testcase 187 OUTPUT]_______________
63 64
[+] SUCCESS: CORRECT ANSWER
_______________[ Stress test, testcase 188 INPUT ]_______________
1
41 9
_______________[ Stress test, testcase 188 OUTPUT]_______________
41 16
WA
[-] FAILURE: RUNTIME ERROR
Ans.diff:7
brute_diff:3
x_br:41
y_br:6
_______________[ 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
{
ll dp;
vector dp2(40,vector<Diff_p_q>(3));
dp2[0][0]=Diff_p_q(0,0);
dp2[0][1]=Diff_p_q(1,0);
dp2[0][2]=Diff_p_q(0,1);
for (int i=0;i<=35;++i) {
dp2[i]=dp2[i-1];
// dp[i][0] 自己重新开始 继承 继承 继承
dp2[i][0]=min({Diff_p_q(0,0),dp2[i][0],dp2[i-1][1],dp2[i-1][2]});
// 自己重新开始
dp2[i][1]=min({Diff_p_q(1ll<<i,0),Diff_p_q(dp2[i-1][0].p+(1ll<<i),dp2[i-1][0].q),
Diff_p_q(dp2[i-1][1].p+(1ll<<i),dp2[i-1][1].q),
Diff_p_q(dp2[i-1][2].p+(1ll<<i),dp2[i-1][2].q)});
dp2[i][2]=min({Diff_p_q(0,1ll<<i),Diff_p_q(dp2[i-1][0].p,dp2[i-1][0].q+(1ll<<i)),
Diff_p_q(dp2[i-1][1].p,dp2[i-1][1].q+(1ll<<i)),
Diff_p_q(dp2[i-1][2].p,dp2[i-1][2].q+(1ll<<i))});
}
Ans=min({Ans,dp2[35][0],dp2[35][1],dp2[35][2]});
}
*/
```
:::
## 心路历程（WA，TLE，MLE……）