题解：P17731 [ICPC 2019 Xuzhou R] Cat

· · 题解

前言：赛时吃两发罚时，唐完了。

思路：

观察数据范围，显然要找规律。

考虑打表。

我们调用超强的观察力，注意到有：

在区间 [1,4n-1]（n \ge 1）的异或和一定为 0。

故我们可以推出结论：

对于符合 L \equiv 0 \pmod 4 且 R \equiv 3 \pmod 4 的连续的长度为 4 的倍数的区间 [L,R]，其异或和一定为 0。

::::info[证明]

考虑在二进制下最低两位的贡献：

贡献为 00，01，10，11。

显然最低两位异或和为 0。

考虑高位：

由于对于每个区间长度为 4​ 的区间下，数字除最低两位外完全相同，因此高位不对异或和产生贡献。

证毕。

::::

那么做法就出来了，找到极大符合 L \equiv 0 \pmod 4 且 R \equiv 3 \pmod 4 的连续区间 [L,R]，由于 S \ge 0，这段区间一定可以被选中。

然后暴力扩展即可。具体地，向左扩展 0 至 3 位，向右扩展至 0 至 3 位，注意判断是否符合查询范围。

::::success[Code]

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll T,L,R,S;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>T;
    while(T--){
        cin>>L>>R>>S;

        ll l = L, r = R, ans = 0;
        while(l%4 != 0) ++l;
        while(r%4 != 3 && r>=l) --r;

        if(l>r){
            //没有区间，直接暴力
            for(ll i=L;i<=R;++i){
                ll sum = 0;
                for(ll j=i;j<=R;++j){
                    sum ^= j;
                    if(sum <= S) ans = max(ans, j-i+1);
                }
            }
        }else{
            ll sum = 0;
            ans = (r-l+1);
            // cout<<l<<' '<<r<<'\n';
            for(ll i=l;i>=L;--i){
                if(i != l) sum ^= i;
                if(sum <= S) ans = max(ans, r-i+1);
                for(ll j=r;j<=R;++j){
                    if(j != r) sum ^= j;
                    if(sum <= S) ans = max(ans, j-i+1);
                }
                for(ll j=r;j<=R;++j){
                    if(j != r) sum ^= j;
                }
            }
        }

        if(ans == 0) ans = -1;
        cout<<ans<<'\n';

        // ll tmp = 0;
        // for(ll i=L;i<=R;++i){
        //     tmp ^= i;
        // }
        // cout<<"#"<<tmp<<'\n';
    }


    return 0;
}
/*
考虑拆位贡献

从低到高
0:(n+1)/2
1:0~1,2~3,4~5,6~7
(n/2)
……
第k位:(n+1)/2 + n%(1ll<<k)
这些都没用

发现性质：1~(4n-1) 异或和一定为 0
故对于符合 L%4 == 0 && R%4 == 3 连续的长度为 4 的倍数的区间可以直接取得
然后暴力扩展即可

*/

::::