【MST+GCD】CF714div2 D. GCD and MST

朱雀 2024-03-22 13:13 59阅读 0赞

**第一次写2000分的题，把大致思路想出来了**

**但是差点细节**

**比如vis数组****没加****，区间贡献算错了**

**对于这些，思路对的但是差点细节的题，应该多模拟样例，不然写出来会很抽象**

[Problem - D - Codeforces][]

题意：

![4471028f50ab4e01a507aba4ccc7149e.png][]

思路：

记录了一下一开始想的思路：

![fb906ce2d99147869032fb179fe43bf4.jpeg][]

写到最后一行的时候差不多思路就出来了

![99e79287534e4127801af933f2e44ea3.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mod=998244353;
    
    struct ty{
    	int val,id;
    }num[mxn];
    
    bool cmp(ty x,ty y){
    	if(x.val==y.val) return x.id<y.id;
    	return x.val<y.val;
    }
    
    int N,P;
    int a[mxn],vis[mxn];
    
    void solve(){
    	cin>>N>>P;
    	for(int i=1;i<=N;i++) vis[i]=0;
    	for(int i=1;i<=N;i++){
    		cin>>a[i];
    		num[i]={a[i],i};
    	}
    	sort(num+1,num+1+N,cmp);
    	int ans=0,cnt=N-1;
    	for(int i=1;i<=N;i++){
    		if(num[i].val>=P) break;
    		if(vis[num[i].id]==1) continue;
    		int pos=num[i].id;
    		int l=pos,r=pos;
    		while(l>=1&&a[l]%a[pos]==0){
    			l--;
    			if(vis[l+1]) break;
    		}
    		l++;
    		while(r<=N&&a[r]%a[pos]==0){
    			r++;
    			if(vis[r-1]) break;
    		}
    		r--;
    		for(int i=l;i<=r-1;i++) vis[i]=vis[i+1]=1;
    		ans+=(r-l)*a[pos];
    		cnt-=(r-l);
    	}
    	cout<<ans+cnt*P<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1513/problem/D
[4471028f50ab4e01a507aba4ccc7149e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/03520d67d38f403b8507bf5e1dbd83b0.png
[fb906ce2d99147869032fb179fe43bf4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c15f907003354ccc8d0ab742805dcb98.png
[99e79287534e4127801af933f2e44ea3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c46daef3967548a3a4dc96441b17e12d.png