题解：P17731 [ICPC 2019 Xuzhou R] Cat

polishtex · 2026-10-22 15:44:58 · 题解

题解：P17731 [ICPC 2019 Xuzhou R] Cat

题意

有编号为 1,2,\dots,10^{18} 的猫排成一行，购买编号连续的一段 x,x+1,\dots,y 需要花费：

其中 \oplus 表示按位异或。

有 T 个询问，每个询问 L,R,S，要求只能在 [L,R] 内购买连续编号的猫，且总花费不超过 S。问最多能买多少只猫；如果啥也买不了，输出 -1。

考场思路

求一段区间的异或和自然想到前缀异或。设：

那么区间 [x,y] 的异或和为：

经过手模前几项，不难发现前缀异或的一个规律：

于是如果存在两个前缀下标 p=x-1 和 q=y，满足：

于是，

正解思路

由此我们能发现：

对于任意长度不小于 7 的区间，一定存在一个长度至少为 len-6 的子区间，其异或和为 0。

因为在前缀下标序列中，模 4 余 1 或 3 的位置每 4 个就会出现两个。任意连续 3 个整数中，至少有一个数模 4 余 1 或 3。因此在一个长区间中，最多从两端各去掉 3 个元素（即最多总共 6 个元素），就能找到一对满足刚才条件、使得对应子区间异或和为 0 的下标对，因此无论 S 多小，答案都不会小于 len-6

也就是说，如果原区间长度为 len=R-L+1，那么答案一定在 [len-6, len] 中。

因此对于 len \ge 7 的情况，我们只需要枚举所有可能的长度，然后对于每种长度，检查所有可能的子区间即可。

对于某个长度，我们可将其视为去掉 i 个元素，其中 i \in [0,6] ，即当前选中区间长度为 len-i。我们枚举区间开头 j，那当前情况下的对应区间为：

其花费为：

若花费不超过 S，则当前长度可行。

对于 len<7 的情况，我们直接枚举所有可能的答案长度，再枚举所有起点即可。

代码

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
#define fi first
#define se second
#define pct(x) __builtin_popcount(x)
#define ump unordered_map<int,int>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=2e5+5,K=55,INF=0x3f3f3f3f,mod=998244353;

ll f(ll n){
    if(n%4==0)return n;
    if(n%4==1)return 1;
    if(n%4==2)return n+1;
    if(n%4==3)return 0;
}

ll l,r,s,len,ans;

void solve(){
    cin>>l>>r>>s;
    len=r-l+1,ans=-1;
    if(len<7){
        for(int i=len,fl;i>=1;i--){
            fl=0;
            for(ll j=l;j+i-1<=r;j++){
                if((f(j+i-1)^f(j-1))<=s){
                    fl=1;
                    break;
                }
            }
            if(fl){
                ans=i;
                break;
            }
        }
    }
    else{
        for(int i=0,fl;i<=6;i++){
            fl=0;
            for(int j=0;j<=i;j++){
                if((f(r+j-i)^f(l+j-1))<=s){
                    fl=1;
                    break;
                }
            }
            if(fl){
                ans=len-i;
                break;
            }
        }
    }

    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

复杂度分析

单次询问最多检查 7 种长度，每种长度最多检查 7 个区间，因此单次询问复杂度为 O(7^2)=O(1)，总时间复杂度为 O(T)。 空间复杂度 O(1)。