蓝桥杯第 2 场小白入门赛

本文介绍: 我们可以发现他具有鲜明的区间修改和变化的操作但是他和我们平常的线段树不同他具有几个物品之间的切换之类的操作，对于这些变化，我们线段树变化的核心在于lazy如何修改我们可以在线段树中用懒标记来维护他们之间的关系，如果是翻倍的话也就是自己和自己的关系，关系如何传递，所以我们用二维数组来充当懒标记来处理，然后再用数组进行pushdown的操作来维护。我们可以先使用线性筛处理出所有的质数，接着对两个质数的中间的数进行左右变化处理最小值即可预处理o(n),然后直接求解即可。对于倍数的累加然后加上剩余的即可。

1.蓝桥小课堂-平方和

2.房顶漏水啦

3.质数王国

4.取余

void solve(){
	
	LL x; cin>>x;
	LL ans= x*(x+1)*(2*x+1)/6;
	cout<<ans<<endl;
}

void solve(){
	
	cin>>n>>m;
	LL mix=1e18,miy=1e18,Max=-1e18,May=-1e18;
	while(m--){
		LL x,y; cin>>x>>y;
		mix=min(x,mix);
		Max=max(Max,x);
		miy=min(miy,y);
		May=max(May,y);
	}
	
	LL ans = max((Max-mix+1),(May-miy+1));
	
	cout<<ans<<endl;
}

int cnt;
int primes[N];

void solve(){
	
	cin>>n;
	
	auto get = [&](){
		bitset<N> st;
		for(int i=2;i<N;i++){
			if(!st[i]) primes[cnt++]=i;
			for(int j=0;primes[j]<=N/i;j++){
				st[i*primes[j]]=true;
				if(i%primes[j]==0) break;
			}
		}
	};
	
	get();
	
	vector<int> dp(N);
	dp[0]=2,dp[1]=1;
	
	for(int i=1;i<cnt;i++){
		for(int x=primes[i-1]+1;x<primes[i];x++){
			dp[x]=min(x-primes[i-1],primes[i]-x);
		}
	}
	LL ans=0;
	while(n--){
		int x; cin>>x;
		ans+=dp[x];
	}
	cout<<ans<<endl;
}

void solve(){
	
	LL A,B,S,T; cin>>A>>B>>S>>T;
	
	auto get = [&](LL u){
		LL res=0;
		if(u<0) return res;
		for(int i=1;i<=B;i++){
			if(i<=u+1) res+=A;
			else res+=A/i*(u+1)+min(A%i,u);
		}
		return res;
	};
	
	cout<<get(T)-get(S-1)<<endl;
}

LL lcm(LL a,LL b){
	return a/__gcd(a,b)*b;
}

void solve(){
	
	vector<LL>  lc(N);
	
	auto get = [&](){
		lc[0]=1;
		for(int i=1;i<N;i++){
			lc[i]=lcm(i,lc[i-1]);
			if(lc[i]>1e16){
				lc[i]=0; break;
			}
		}	
	};
	
	get();
	
	cin>>t;
	while(t--){
		LL n,m;
		cin>>n>>m;
		if(n==1||lc[n-1]==0){
			cout<<0<<endl;
			continue;
		}
		LL ans=m/lc[n-1]-(lc[n] ? m/lc[n] : 0);
		cout<<ans<<endl;
	}	
	
}

int t,n,m;
int op,ql,qr,A,B;

int add[N*4][3][3],a[N*4][3],now[3][3];

void pushup(int u){
	for(int i=0;i<3;i++) a[u][i]=(a[u<<1][i]+a[u<<1|1][i])%mod; 
}

void lazy(int a[3][3],int b[3][3]){
	int c[3][3];
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++){
			c[i][j]=0;
			for(int k=0;k<3;k++){
				c[i][j]=(c[i][j]+(LL)a[i][k]*b[k][j]%mod)%mod;
			}
		}
	// 记录下来关系的传递
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			a[i][j]=c[i][j];
}
void down(int a[3],int b[3][3]){
	// 这个区间直接修改
	int c[3];
	for(int j=0;j<3;j++){
		c[j]=0;
		for(int k=0;k<3;k++){
			c[j]=(c[j]+(LL)a[k]*b[k][j]%mod)%mod;
		}
	}
	for(int i=0;i<3;i++) a[i]=c[i];
}

void build(int u,int l,int r){
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			add[u][i][j]=(i==j);// 表示lazy
	if(l==r){
		int x; cin>>x;
		x--;
		a[u][x]=1;
		return ;
	}	
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}

void modify(int u,int l,int r){
	if(ql<=l && r<=qr){// 找到需要修改的区间
		lazy(add[u],now);// 然后加入懒标记
		down(a[u],now);
		return ;
	}
	lazy(add[u<<1],add[u]);
	lazy(add[u<<1|1],add[u]);
	down(a[u<<1],add[u]);
	down(a[u<<1|1],add[u]);
	
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			add[u][i][j]=(i==j);// 表示这个区间的lazy用完了恢复
			
	int mid=l+r>>1;
	if(ql<=mid) modify(u<<1,l,mid);
	if(qr>mid) modify(u<<1|1,mid+1,r);
	pushup(u);
}

void solve(){
   
    cin>>n>>m;
    build(1,1,n);
    while(m--){
     	cin>>ql>>qr>>op>>A; A--;
     	memset(now,0,sizeof now);// 表示传递的性质   1->1 自己到自己等于没有标记
     	// 表示是否具有标记的传递
     	for(int i=0;i<3;i++) now[i][i]=1;
     	if(op==3){
     		now[A][A]=2;// 自己到自己乘以2
     	}
     	else{
     		cin>>B; B--;
     		if(op==1) now[A][A]=now[B][B]=0,now[A][B]=now[B][A]=1;
     		else now[A][A]=0,now[A][B]=1;
     	}
     	modify(1,1,n);
     	for(int i=0;i<3;i++) cout<<a[1][i]<<' ';
     	cout<<endl;
    }
    return ;
}

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。