题解：P17731 [ICPC 2019 Xuzhou R] Cat

Water_Lemon · 2026-10-22 18:34:17 · 题解

题目

0x01 思路

观察到 L,R \le 10^{18}，不能枚举，考虑构造一组较大解。

我们先将 \oplus_{i=x}^{y}{i} 转化为 \oplus_{i=1}^{y}{i} \oplus \oplus_{i=1}^{x-1}{i}。而对于前缀异或则有：

所以我们可以在 [L,R] 中找到第一个四的倍数，使得 \oplus_{i=x}^{y}{i}=0，再去暴力枚举更大长度即可。

因为我们构造出了较大解，所以剩余枚举的数量 \le 9，总复杂度 O(T)。

0x02 代码

:::info[赛时代码]

#include<bits/stdc++.h>
using namespace std;
#define debug cout<<"---Successfully---\n"
#define PII pair<int ,int >
#define int long long
#define endl '\n'
#define ssj 0
const int N=100010;
/*---------- Paste Clipboard ----------*/
#if defined(WLSSJ)&&defined(_WIN32)
#include<io.h>
struct _Clip{
    FILE*f=_popen("powershell -NoP -c Get-Clipboard 2>nul","r");
    _Clip(){if(f)_dup2(_fileno(f),0);}
    ~_Clip(){if(f)_pclose(f);}
}_clip;
#endif
int T;
int L,R,S;
int sumxor(int x){
    if(x%4==1) return 1;
    if(x%4==2) return x+1;
    if(x%4==3) return 0;
    return x;
}
void sol(){
    cin>>L>>R>>S;
    int limL=L-(L%4)+4,limR=R-(R%4),ans=-1;
    for(int len=limR-limL;len<=R-L+1;len++){
        for(int l=L;l+len-1<=R;l++){
            if((sumxor(l-1)^sumxor(l+len-1))<=S){
                ans=len;break;
            }
        }
    }
    if(ans>0) cout<<ans<<endl;
    else cout<<-1<<endl;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>T;
    while(T--) sol();
    return ssj;
}

:::