目录
问题概述
给出整数a、b、r，要求输出|(a^x) - (b^x)|的绝对值，其中0<=x<=r（取值都是[0, 1e18]）
思路想法
首先是一个位置关系，由于求的是绝对值，所以我们可以假定a > b；第二，我们要做的是异或操作，因此可以将a和b的二进制数写出来，结合异或的特点，可以发现，当a和b的相应位数上相同时，无论该位取0/1，不影响最小值，当然，我们肯定取0最好，比较x是有范围的；当a和b的相应位数上的值不同时，我们考虑取x位数取1的效果，可以发现，当a的位数为1时，会导致a-(1<<idx)，b+(1<<idx)，idx为相应的位数，即差值会减小，相反的，当该位数为0时，差值会变大。但是由于我们做的绝对值，不知道什么时候停止，2和-1这种类型的不好做出来，当时就卡住了
假如a和b的大小关系恒定，即a恒大于b的话，这个题就好写了，是否可以恒定呢，我们只需要保证首位不相同的位数上的值不变就可以保证a恒大于b，假如a = 1a1a2
...an，b = 1b1b2...bn，改变第一位我们可以得到a = 0a1a2...an，b = 0b1b...bn，但是我们发现，我们可以通过改变第一位之后的值将a和b变成相应的模样，因此我们得出结论改变第一位得到的最小值一定可以通过不改变第一位，而是修改其他位得到最小值，那么这样的话，a和b的大小关系就恒定了，只需要求出最小的正整数解即可，那就是从高位向低位不断逼近就行了
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
ll a, b, r;
int arr[67], brr[67];
void solve() {
cin >> a >> b >> r;
if(b > a) swap(a, b);
ll p1 = a, p2 = b;
int idx = 0;
memset(arr, 0, sizeof arr);
memset(brr, 0, sizeof brr);
while(true) {
if(!p1 && !p2) break;
if(p1 & 1) arr[idx] = 1;
if(p2 & 1) brr[idx] = 1;
++idx;
p1 >>= 1, p2 >>= 1;
}
bool first = true;
ll change = 0;
for(int i=64; i>=0; i--) {
if(arr[i] != brr[i]) {
if(!first) {
if(!brr[i]) {
ll tmp = (1ll << i);
if(change+tmp <= r) change += tmp;
}
}
else first = false;
}
}
cout << abs((a-change) - (b+change)) << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
问题反思
刚开始还想着用01背包来做的，就是将r作为拥有的体积，将各位作为消耗体积，改变值作为价值，求最大价值，但是这玩意在没有想通a恒大于b之前也是没有什么意义的，因为最小值不一定在最大值处取得，可能负数嘛，取绝对值就越来越大了，总的来说就是想明白a的b的大小关系恒定就好做了，也就是做题遇到困难要想做假设，然后验证该假设是否可以成立，就会好做很多