问题解决但题未解决 P10403

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

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

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

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

只过了Subtask 0 20pts

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

CPP

#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
*/

问题解决但题未解决 P10403

文章操作

相关推荐

评论

问题解决但题未解决 P10403