首页 > 代码库 > matrix_2015_1 138 - ZOJ Monthly, January 2015
matrix_2015_1 138 - ZOJ Monthly, January 2015
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3844
第一个，n个数，每次操作最大数和最小数都变成他们的差值，最后n个数相同时输出此时的值，暴力跑。
1 #include<cstdio> 2 int main(){ 3 int t,n,a[16]; 4 while(~scanf("%d",&t)){ 5 while(t--){ 6 scanf("%d",&n); 7 for(int i=0;i<n;i++){ 8 scanf("%d",&a[i]); 9 }10 while(true){11 int bid=0,sid=0;12 for(int i=1;i<n;i++){13 if(a[bid]<a[i]) bid=i;14 if(a[sid]>a[i]) sid=i;15 }16 if(a[bid]==a[sid]){17 printf("%d\n",a[sid]);18 break;19 }20 a[bid]=a[sid]=a[bid]-a[sid];21 }22 }23 }24 return 0;25 }
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5440
第二个，n个数，每次操作可以任意选两个数把他们变成他们gcd的值。最后问几步能都变成1，且输出每步选的数的下标。方法：先求出n个数的gcd，如果不为1，输出-1.否则一定能变成全1.变的方法是，先用第一个依次和后面的操作，直至第一个数变成1，然后再用第一个数把剩下的非1的都变掉。
1 #include<cstdio> 2 #include<vector> 3 using namespace std; 4 const int M=1e5+10; 5 typedef pair<int,int> pii; 6 int a[M]; 7 int gcd(int a,int b){ 8 return b?gcd(b,a%b):a; 9 }10 vector<pii> ans;11 int main(){12 int n;13 int cas=1;14 while(~scanf("%d",&n)){15 for(int i=1;i<=n;i++){16 scanf("%d",&a[i]);17 }18 int now=a[1];19 for(int i=2;i<=n;i++){20 now=gcd(now,a[i]);21 }22 printf("Case %d: ",cas++);23 if(now>1){24 puts("-1");25 puts("");26 continue;27 }28 ans.clear();29 for(int i=2;i<=n;i++){30 int now=gcd(a[1],a[i]);31 a[1]=a[i]=now;32 ans.push_back(make_pair(1,i));33 if(now==1) break;34 }35 for(int i=2;i<=n;i++){36 if(a[i]==1) continue;37 ans.push_back(make_pair(1,i));38 }39 int len=ans.size();40 printf("%d\n",len);41 for(int i=0;i<len;i++){42 printf("%d %d\n",ans[i].first,ans[i].second);43 }44 puts("");45 }46 return 0;47 }
end
matrix_2015_1 138 - ZOJ Monthly, January 2015
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。