[XSOI Round 1] C.跳跃游戏题解

· · 题解

显然，要获得最大经验值就是枚举所有有经验值的 (x,y)。

首先要解决的是如何快速求出 l \sim r 的 \gcd 值，可以用 st 表来进行实现，单次查询复杂度为 O(\log n) , 没学过的人请转步 P3865, st 表预处理和查询代码如下：

void Init(int n){
    lg[1] = 0;
    for(int i = 2 ; i <= n ; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1 ; i <= n ; i++) st[i][0] = a[i];
    for(int j = 1 ; j <= lg[n] ; j++){
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) st[i][j] = __gcd(st[i + (1 << (j - 1))][j - 1] , st[i][j - 1]);
    }
}
int Find(int l , int r){
    int x = lg[r - l + 1];
    return __gcd(st[l][x] , st[r - (1 << x) + 1][x]);
}

接下来就是考虑如何快速算出所有经验值的总和。

这里复杂度是 O(n \log^2 n) 。

这里给出的做法是枚举 x ，二分查找 y 。

先给出一个显而易见的定理：若 \gcd(a_1,a_2 ,\cdots , a_L)= 3 且 \gcd(a_1,a_2,\cdots , a_R ) = 3 ，则对于 L \le k \le R ，\gcd(a_1,a_2 ,\cdots , a_k)= 3 。

若求出 L \operatorname{and} R ，就可以求出以 x 为左端点的 \operatorname{score_{x,y}} 的总和了。

题解中只写出 \gcd(a_x , a_{x + 1} , \dots , a_y)=3 , \operatorname{len \ mod} 2 = 1 的情况，另一种情况本质上是一样的。

对于这种情况，先对 R 进行二分答案，其中二分的是 R 在第几个 \operatorname{len} 长度为奇数的位置上，则 l = 1 , r = \dfrac{n - x}2 + 1 , 而 \operatorname{check} 函数就是查找当前 x \sim \operatorname{mid} 的 \gcd ，但是,由于 \operatorname{mid} 表示第几个 \operatorname{len} 长度为奇数的位置，而不是真正的位置，需要计算出 \operatorname{truemid}= (\operatorname{mid} - 1) \times 2 + x ，接下来就是如何对 l,r 进行变化。

这样子就能求出 R 了。

其实很多人以为对于 x \le k \le R , 其 \gcd 的值都为 3 ，那就大错特错了，其实其 \gcd 的值是 3 的倍数，而不是 3 ，举个例子：

3
6 6 3

其中, 对于 x=1 时 , R=3 ，但 k=2 时，其 \gcd 值为 6 ，不符合要求。

所以说还是要求 L ，不过这也很简单，其实跟求 R 是一样的，就是把范围缩小到了 x \sim R 而已，这里就不过多阐述。

最后求出 L 和 R 后，就要计算答案了，这里可用求和公式计算。

其中首项为 L - x + 1 ，尾项为 R-x + 1 ，项数为 \dfrac{R-L} 2 +1，则局部答案为 \dfrac{(L+R-2 \times x + 2) \times (\dfrac{R-L} 2 +1)} 2。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int st[600010][30] , a[600010] , lg[600010];
void Init(int n){
    lg[1] = 0;
    for(int i = 2 ; i <= n ; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1 ; i <= n ; i++) st[i][0] = a[i];
    for(int j = 1 ; j <= lg[n] ; j++){
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) st[i][j] = __gcd(st[i + (1 << (j - 1))][j - 1] , st[i][j - 1]);
    }
}
int Find(int l , int r){
    int x = lg[r - l + 1];
    return __gcd(st[l][x] , st[r - (1 << x) + 1][x]);
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Init(n);
    long long res = 0;
    for(int i = 1 ; i <= n ; i++){
        int l = 1 , r = (n - i) / 2 + 1;
        int best = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            int true_mid = (mid - 1) * 2 + i;
            if(Find(i , true_mid) % 3 != 0) r = mid - 1;
            else if(Find(i , true_mid) % 3 == 0){
                best = max(best , true_mid);
                l = mid + 1;
            }
            else{
                l = mid + 1;
            }
        }
        int best2 = 1e9;
        if(best != -1){
            int l = 1 , r = (best - i) / 2 + 1;
            while(l <= r){
                int mid = (l + r) / 2;
                int true_mid = (mid - 1) * 2 + i;
                if(Find(i , true_mid) == 3){
                    best2 = min(best2 , true_mid);
                    r = mid - 1;
                }
                else l = mid + 1;
            }

        }
        if(!(best == -1 || best2 == 1e9)) res += (long long)(best + best2 - 2 * i + 2) * (long long)((best - best2) / 2 + 1) / 2ll;
        l = 1 , r = (n - i + 1) / 2;
        best = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            int true_mid = mid * 2 + i - 1;
            if(Find(i , true_mid) % 2 != 0) r = mid - 1;
            else if(Find(i , true_mid) % 2 == 0){
                best = max(best , true_mid);
                l = mid + 1;
            }
            else{
                l = mid + 1;
            }
        }
        best2 = 1e9;
        if(best != -1){
            int l = 1 , r = (best - i + 1) / 2;
            while(l <= r){
                int mid = (l + r) / 2;
                int true_mid = mid * 2 + i - 1;
                if(Find(i , true_mid) == 2){
                    best2 = min(best2 , true_mid);
                    r = mid - 1;
                }
                else l = mid + 1;
            }       
        }
        if(best == -1 || best2 == 1e9) continue;    
        res += (long long)(best + best2 - 2 * i + 2) * (long long)((best - best2) / 2 + 1) / 2ll;
    }
    printf("%lld" , res);
    return 0;
}

如有错误，请予以指正。

（可能作者脑抽，没想到简单解法，有简单解法可以私信）