首页 > 代码库 > 杭电女生赛1003
杭电女生赛1003
题意:给一个序列,删除一个数,令这个序列的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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。