题解：P17731 [ICPC 2019 Xuzhou R] Cat
Chen_Three
·
·
题解
题意
区间 [l,r] 选取一个区间 [a,b]，满足 a \oplus (a+1) \oplus \cdots \oplus (b-1) \oplus b \le s 并且最大化 b-a+1。
题解
观察到一个性质，若 x 为偶数，则有 x \oplus (x+1) \oplus (x+2) \oplus (x+3) = 0。
:::info[证明]
容易观察到这样的性质：$x \oplus (x+1) = 1$，原因在于他们只有最低位不同。
这样两个 $1$ 异或得到 $0$。
:::
因此，$[x,x+4k-1]$（$x$ 为偶数）的异或值为 $0$，且是一个连续段。因此，选择这一段一定不劣，此时只需要向左向右暴力扩展即可。
写法上，这里提供一个特判较少的写法：如果 $r-l+1 \le 8$ 直接暴力查询，否则根据 $l$ 奇偶讨论，处理 $l,l+2/l+1,l+3$。这样只有左右端点发生变化，且没有越界风险。
## 复杂度分析
处理完一个极长的连续段后，左右不可能出现一个长度超过 $3$ 的连续段，此时暴力就是 $O(1)$。（虽然说我写的常数有 $9$ 甚至 $512$ 吧，但还是 $O(1)$）。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll rare(ll l, ll r, ll s){
ll ans = -1;
for(ll i = l; i <= r; i++){
for(ll j = i; j <= r; j++){
ll sum = 0;
for(ll k = i; k <= j; k++) sum ^= k;
if(sum <= s) ans = max(ans, j - i + 1);
}
}
return ans;
}
inline ll solve(ll l, ll r, ll tmpl, ll tmpr, ll s){
ll ans = -1, xorl = 0;
for(ll i = tmpl; i >= l; i--){
if(i != tmpl) xorl ^= i;
ll xorr = 0;
for(ll j = tmpr; j <= r; j++){
if(j != tmpr) xorr ^= j;
if((xorl ^ xorr) <= s) ans = max(ans, j - i + 1);
}
}
return ans;
}
int ans;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll _, l, r, s;
cin >> _;
while(_--){
cin >> l >> r >> s;
if(r - l + 1 <= 8){
cout << rare(l, r, s) << "\n";
continue;
}
if(l & 1){
ll tmpl = l + 1, tmpr = tmpl + (r - tmpl + 1) / 4 * 4 - 1, ans = -1;
ans = max(ans, solve(l, r, tmpl, tmpr, s));
tmpl = l + 3, tmpr = tmpl + (r - tmpl + 1) / 4 * 4 - 1;
ans = max(ans, solve(l, r, tmpl, tmpr, s));
cout << ans << "\n";
}else{
ll tmpl = l, tmpr = tmpl + (r - tmpl + 1) / 4 * 4 - 1, ans = -1;
ans = max(ans, solve(l, r, tmpl, tmpr, s));
tmpl = l + 2, tmpr = tmpl + (r - tmpl + 1) / 4 * 4 - 1;
ans = max(ans, solve(l, r, tmpl, tmpr, s));
cout << ans << "\n";
}
}
return 0;
}
```