首页 > 代码库 > 杭电女生赛1003

杭电女生赛1003

2024-09-20 04:29:43   220人阅读

题意：给一个序列，删除一个数，令这个序列的gcd最大

思路：求出原始序列的gcd=g，然后从左边跑一遍gcd，如果gcd==c 标记 r，那么a[r] 肯定和前面某个数的gcd为 c ， 再从r开始完前跑一遍求gcd，直到gcd==c，标记l，那么a[l]一定与后面（l到r区间）某个数的gcd为 c，所以可得 gcd(a[l],a[r])==c ，分别删除a[l] a[r] 求gcd 输出较大的

PS：给的是任意序列，但是题目第一句话告诉我什么是互质序列是什么鬼，wa了一天以为给的是互质序列，要不是我狗哥提醒我这是中国人出题，不是cf，前面讲的互质序列可能没软用，我可能一辈子也想不到。。。。mdzz

PPS：代码改得乱七八糟随便看看就好了。。。当然大佬都是前缀后缀搞出来的不用考虑互质不互质的问题

AC代码：

#include "iostream"
#include "string.h"
#include "string"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e5+100;
int n,t,a[N],b[N];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1; i<=n; ++i){
            scanf("%d",a+i);
            b[i]=a[i];
        }
        int c=a[1];
        for(int i=2; i<=n; ++i){
            c=__gcd(c,a[i]);
        }
        int g=a[1],l=1,r=n;
        for(int i=2; i<=n; ++i){
            if(g==c){
                r=i-1;
                break;
            }
            g=__gcd(g,a[i]);
        }
        g=a[r];
        for(int i=r-1; i>=1; --i){
            if(g==c){
                l=i+1;
                break;
            }
            g=__gcd(g,a[i]);
        }
        //cout<<l<<" "<<r<<endl;
        if(l==1) a[l]=a[l+1];
        else a[l]=a[l-1];
        if(r==1) b[r]=b[r+1];
        else b[r]=b[r-1];
        int ans1=a[1],ans2=b[1];
        for(int i=2; i<=n; ++i){
            ans1=__gcd(ans1,a[i]);
            ans2=__gcd(ans2,b[i]);
        }
        cout<<max(ans1,ans2)<<endl;
    }
    return 0;
}

 

杭电女生赛1003


联系
我们