首页 > 其他 > 详细

第六周 10.4-10.10

时间:2015-10-04 11:02:42      阅读:281      评论:0      收藏:0      [点我收藏+]

10.4

CF 582A GCD Table

贪心取最大。熟悉set大法。

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <set>
 7 using namespace std;
 8 multiset<int> S;
 9 multiset<int>::iterator it;
10 vector<int> ans;
11 
12 int gcd(int a,int b)
13 {
14     return a%b?gcd(b,a%b):b;
15 }
16 
17 int main(void)
18 {
19     S.clear();
20     int n; scanf("%d",&n);
21     for(int i=0;i<n*n;i++)
22     {
23         int x;
24         scanf("%d",&x);
25         S.insert(x);
26     }
27     while(!S.empty())
28     {
29         it=S.end(); it--;
30         int cur=*it;
31         S.erase(it);
32         for(int i=0;i<ans.size();i++)
33         {
34             int t=gcd(ans[i],cur);
35             for(int i=0;i<2;i++)
36             {
37                 it=S.find(t);
38                 S.erase(it);
39             }
40         }
41         ans.push_back(cur);
42     }
43     for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
44     puts("");
45     return 0;
46 }
Aguin

 

第六周 10.4-10.10

原文:http://www.cnblogs.com/Aguin/p/4854239.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!