问题解决但题未解决 P10403

Wild_Of_The_World · 2024-12-31 20:57:27 · 个人记录

想到问题了，这样并不能遍历完所有区间，只能走到(1<<i)以及其加1长度的区间

思路是st表预处理的时候判断该区间的gcd是不是2，直接取值。

然后该区间向右扩展一格判断gcd是不是3，取值。

st表预处理时应该会把所有区间长为（1<<i）的区间都遍历一遍，然后区间长加1，这样应该遍历到了所有区间。

只过了Subtask 0 20pts

[测评记录](Subtask 0) 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
int n,st[N][20],lg[N],ans;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n;
    lg[1]=0;
    for(int i=1;i<=n;i++){
        if(i!=1) lg[i]=lg[i>>1]+1;
        cin>>st[i][0];
        if(st[i][0]==3) ans++;
    }
//  cout<<ans<<endl;
    for(int j=1;j<=lg[n];j++)
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
            if(st[i][j]==2){
//              printf("2(%d,%d) %d\n",i,i+(1<<j)-1,1<<j);
                ans+=(1<<j);
            } 
            if(i+(1<<j)<=n&&__gcd(st[i][j],st[i+(1<<j)][0])==3){
//              printf("3(%d,%d) %d\n",i,i+(1<<j),1+1<<j);
                ans+=1+(1<<j);
            }
        }   
    cout<<ans<<endl;
    return 0;
} 
/*
5
2 3 6 3 9
*/