题目链接：https://codeforces.com/gym/102411
D. Dream Team
题意：n个点，让你连边成为一棵树，边权为顶点的GCD（u，v）。求所有边权和的最大值。
思路：将每个数进行因数分解，从大的因子开始求最大生成树。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 50; 4 vector<int> G[maxn]; 5 int far[maxn]; 6 int n; 7 int find(int x) 8 { 9 if(far[x] == x) return x; 10 else return far[x] = find(far[x]); 11 } 12 void unite(int x, int y) 13 { 14 x = find(x); 15 y = find(y); 16 if(x == y) return ; 17 far[x] = y; 18 } 19 bool check(int x, int y) 20 { 21 return find(x) == find(y); 22 } 23 void init() 24 { 25 for(int i = 0;i < maxn;i++) 26 { 27 far[i] = i; 28 G[i].clear(); 29 } 30 } 31 long long kruskal() 32 { 33 long long ans = 0; 34 for(int i = 1e5;i >= 1;i--) 35 { 36 if(G[i].size() < 2) continue; 37 else{ 38 int u = G[i][0]; 39 for(int j = 1;j < G[i].size();j++) 40 { 41 int v = G[i][j]; 42 if(!check(v, u)){ 43 ans += i; 44 unite(v, u); 45 } 46 } 47 } 48 } 49 return ans; 50 } 51 void gao(int x, int k) 52 { 53 int nn = sqrt(x); 54 for(int i = 1;i <= nn;i++) 55 { 56 if(x % i == 0){ 57 if(i * i == x){ 58 G[i].push_back(k); 59 } 60 else { 61 G[i].push_back(k); 62 G[x/i].push_back(k); 63 } 64 } 65 } 66 } 67 int main() 68 { 69 freopen("dream.in","r",stdin); 70 int t; 71 scanf("%d",&t); 72 for(int cas = 1; cas <= t;cas++) 73 { 74 init(); 75 scanf("%d",&n); 76 int x; 77 for(int i = 0;i < n;i++){ 78 scanf("%d",&x); 79 gao(x,i); 80 } 81 long long ans = kruskal(); 82 printf("Case %d: ",cas); 83 printf("%lld\n",ans); 84 } 85 return 0; 86 } 87 88
F. Forgot the Flag!
题意：给你一个凸多边形，给你俩个点在多边形内，问你从a点到多边形一条边上再到b点的最小距离以及和边界的交点。
思路：对于多边形每条边求点b的对称点，答案就是a到对称点的距离，然后求直线交。注意特判俩点重合并且在线上的时候。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e5 + 50; 5 const double eps = 1e-10; 6 double INF = 1e18; 7 int sgn(double x) 8 { 9 if(fabs(x) < eps) return 0; 10 else return x < 0 ? -1 : 1; 11 } 12 struct Point{ 13 double x, y; 14 Point(){} 15 Point(double _x,double _y) 16 { 17 x = _x,y = _y; 18 } 19 void input() 20 { 21 scanf("%lf %lf",&x, &y); 22 } 23 bool operator ==(const Point &b)const{ 24 return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; 25 } 26 bool operator <(const Point &b)const{ 27 return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; 28 } 29 Point operator -(const Point &b)const{ 30 return Point(x - b.x, y - b.y); 31 } 32 double operator ^(const Point &b)const{ 33 return x*b.y-y*b.x; 34 } 35 double operator *(const Point &b)const{ 36 return x*b.x + y*b.y; 37 } 38 double len2(){ 39 return x*x + y*y; 40 } 41 double distance(Point p){ 42 return hypot(x-p.x,y-p.y); 43 } 44 Point operator + (const Point &b)const{ 45 return Point(x+b.x,y+b.y); 46 } 47 Point operator * (const double &k)const{ 48 return Point(x*k,y*k); 49 } 50 Point operator / (const double &k)const{ 51 return Point(x/k,y/k); 52 } 53 54 }; 55 Point p[maxn]; 56 struct line{ 57 Point s, e; 58 line(){} 59 line(Point _s, Point _e) 60 { 61 s = _s,e= _e; 62 } 63 Point lineprog(Point p) 64 { 65 return s +(((e - s) * ((e - s)*(p - s)))/((e - s).len2())); 66 } 67 Point symmetrypoint(Point p) 68 { 69 Point q = lineprog(p); 70 return Point(2*q.x - p.x, 2*q.y - p.y); 71 } 72 Point crosspoint(line v) 73 { 74 double a1 = (v.e - v.s) ^ (s - v.s); 75 double a2 = (v.e - v.s) ^ (e - v.s); 76 return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)); 77 } 78 int relation(Point p){ 79 int c=sgn((p-s)^(e-s)); 80 if(c<0) return 1; 81 else if(c>0) return 2; 82 else return 3; 83 } 84 }; 85 int main() 86 { 87 int t; 88 freopen("flags.in","r",stdin); 89 scanf("%d",&t); 90 for(int cnt = 1;cnt <= t;cnt++) 91 { 92 int n; 93 scanf("%d",&n); 94 for(int i = 0;i < n;i++) p[i].input(); 95 int q; 96 Point st, ed; 97 line l ; 98 Point a; 99 scanf("%d",&q); 100 printf("Case %d:\n",cnt); 101 while(q--) 102 { 103 st.input(); 104 ed.input(); 105 double ans = INF; 106 double d; 107 Point anspoint; 108 for(int i = 0;i < n;i++){ 109 l = line(p[i],p[(i+1)%n]); 110 a = l.symmetrypoint(ed); 111 d = st.distance(a); 112 if(l.relation(ed) == 3 && st == ed) 113 { 114 ans = 0; 115 anspoint = st; 116 break; 117 } 118 if(sgn(d - ans) < 0){ 119 ans = d; 120 line r = line(st, a); 121 anspoint = l.crosspoint(r); 122 } 123 } 124 printf("%.7f %.7f %.7f\n",ans,anspoint.x,anspoint.y); 125 } 126 } 127 return 0; 128 }
.G. Glorious Stadium
思路：推公式。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const double pi = acos(-1.0); 4 int main() 5 { 6 int t; 7 freopen("glorious.in","r",stdin); 8 scanf("%d",&t); 9 for(int cas = 1;cas <= t;cas++) 10 { 11 int n; 12 double r, k; 13 scanf("%d %lf %lf",&n, &r, &k); 14 printf("Case %d: ",cas); 15 double af = pi / k; 16 double c = 1/(cos(af)*cos(af)); 17 double m = (1.0-pow(c,n))/(1.0-c); 18 double ans = (tan(af)*k - pi)*r*r*m; 19 printf("%.5f\n",ans); 20 } 21 return 0; 22 }
J. Jacked Tickets
题意：将n个东西分成m份，每一种数量 i 对应 p[i] 的损失，问损失和最小多少。
思路：题目说p[i]满足凹函数的性质，那么可以贪心知道，对于每一份要尽可能的平均。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e5 + 50; 5 ll a[maxn]; 6 int main() 7 { 8 freopen("jacking.in","r",stdin); 9 int t; 10 scanf("%d",&t); 11 for(int cnt = 1;cnt <= t;cnt++) 12 { 13 int n; 14 scanf("%d", &n); 15 for(int i = 1;i <= n;i++) 16 { 17 scanf("%lld",&a[i]); 18 } 19 int q; 20 scanf("%d", &q); 21 ll x, y; 22 printf("Case %d:\n", cnt); 23 while(q--) 24 { 25 scanf("%lld %lld",&x, &y); 26 if(x < y){ 27 printf("impossible\n"); 28 } 29 else 30 { 31 ll num = x / y; 32 ll remain = x % y; 33 ll ans = a[num]*y - a[num]*remain; 34 ans += a[num + 1]*remain; 35 printf("%lld\n",ans); 36 } 37 38 } 39 } 40 return 0; 41 }
K. Katryoshka
题意：给定a,b,c,由（2*a,b），（2*a,b,c）,(a,b,c) 三种组成方法去构造一个模型，问最多构建几个模型。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 std::ios::sync_with_stdio(false); 6 freopen("katryoshka.in","r",stdin); 7 int t; 8 cin >> t; 9 for(int cnt = 1;cnt <= t; cnt++) 10 { 11 int a, b, c; 12 cin >> a >> b >> c; 13 int k = min(a, b); 14 k = min(k, c); 15 int ans = k; 16 a -= k;b -= k;c -= k; 17 ans += min(a / 2, c); 18 cout << "Case " << cnt << ": " << ans << endl; 19 } 20 return 0; 21 } 22 23
L. Lazy ERCD
签到题。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int main(){ 5 freopen("lazy.in","r",stdin); 6 int T; 7 cin >>T; 8 for(int co = 1; co <= T; co++){ 9 int x; 10 cin >>x; 11 cout <<"Case "<<co<<": "<<x-1<<endl; 12 } 13 }