首页 > 代码库 > # 7-19题解
# 7-19题解
A - An Easy Physics Problem
没有计算几何关于圆的模板，都是在场写的，赛场上wa了很多法，
因为考虑的不是很周全．刚开始就因为只注意了圆心到两点的距离需要超过半径，
但忽略了一个点直接到另一个点．关于一个点射向另一个点要注意方向，我选取了额外一个点，
制造了一个角．判断角是否相等来判断一个点射向另外一个点．
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 using namespace std; 5 const double eps = 1e-8; 6 struct Point { 7 double x, y; 8 Point(){}; 9 Point(double a, double b) { 10 x = a, y = b; 11 } 12 }; 13 14 struct Segment { 15 Point a, b; 16 Segment(){}; 17 Segment(Point x, Point y){ 18 a = x, b = y; 19 } 20 }; 21 22 double dis(Point a, Point b){ 23 return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); 24 } 25 //叉积判断点在线段两端．跟eps或者-eps比较会有不同的结果，注意． 26 double Multi(Point p0, Point p1, Point p2) { 27 return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); 28 } 29 //点积 30 double dMulti(Point p0, Point p1, Point p2) { 31 return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y); 32 } 33 //算角度，利用点积算的acos角度，也就是说方向是需要额外判断的 34 double ang(Point p0, Point p1, Point p2) { 35 //printf("%lf",dMulti(p0, p1, p2)/dis(p0, p1)/dis(p0, p2)); 36 return acos(dMulti(p0, p1, p2) / dis(p0, p1) / dis(p0, p2)); 37 } 38 //点在矩形里面． 39 bool inRect(Point a, Point x, Point y) { 40 if (max(x.x, y.x) >= a.x && a.x >= min(x.x, y.x) 41 && max(x.y, y.y) >= a.y && a.y >= min(x.y, y.y) 42 ) return true; 43 return false; 44 } 45 //处理近似０和eps的关系的 46 int dblcmp(double m) { 47 if (fabs(m) <eps) return 0; 48 return m > 0 ? 1 : -1; 49 } 50 double vx,vy; 51 52 double distoSegment(Point a, Segment b) { 53 double ans = Multi(b.a, b.b, a); 54 return abs(ans / dis(b.a, b.b)); 55 } 56 57 Point GetPoint(Point o, int r, Point a) { 58 if (abs(vy - a.y) > eps) { 59 double da = (1+vy * vy / vx / vx); 60 double db = -(2 * o.x - 2 * vy / vx * (a.y - o.y) + (vy * vy / vx / vx * 2 * a.x)); 61 double dc = (o.x * o.x - 2 * vy / vx * a.x * (a.y - o.y) 62 + (a.y - o.y) * (a.y - o.y) - r * r + vy * vy / vx / vx * a.x * a.x); 63 double delat = sqrt(db * db - 4 * da * dc); 64 //printf("%lf %lf %lf %lf",da,db,dc,delat); 65 double x = (-db + delat) / 2 / da; 66 double y = vy / vx * (x - a.x) + a.y; 67 Point huchi = Point(x, y); 68 double tx = (-db - delat) / 2 / da; 69 double ty = vy / vx * (tx - a.x) + a.y; 70 //printf("%lf %lf %lf %lf\n",x,y,tx,ty); 71 Point chihu = Point(tx, ty); 72 if (dis(huchi, a) < dis(chihu, a)) { 73 return huchi; 74 } else { 75 return chihu; 76 } 77 } else { 78 double x = o.x + sqrt(r * r - (a.y - o.y) * (a.y - o.y)); 79 double y = a.y; 80 Point huchi = Point(x,y); 81 double tx = -o.x + sqrt(r * r - (a.y - o.y) * (a.y - o.y)); 82 double ty = a.y; 83 Point chihu = Point(y, x); 84 if (dis(huchi, a) < dis(chihu, a)) { 85 return huchi; 86 } else { 87 return chihu; 88 } 89 } 90 } 91 92 int main() { 93 int T, t = 0; scanf("%d", &T); 94 while (t++ < T) { 95 double o_x, o_y; 96 scanf("%lf%lf", &o_x, &o_y); 97 Point O = Point(o_x, o_y); 98 double r; scanf("%lf", &r); 99 double a_x, a_y, b_x, b_y; 100 scanf("%lf%lf%lf%lf", &a_x, &a_y, &vx, &vy); 101 scanf("%lf%lf", &b_x, &b_y); 102 Point A = Point(a_x, a_y); 103 Point B = Point(b_x, b_y); 104 bool final_a = 0; 105 if (r <= distoSegment(O, Segment(A,B))) { 106 //cout <<"huchi"<<endl; 107 if (abs(vy * (A.x - B.x) - vx * (A.y - B.y)) < eps) { 108 Point tt = Point(1001, A.y); 109 if (abs(ang(A, tt, B) - ang(Point(B.x - vx, B.y - vy), Point(1001, B.y - vy), B)) < eps) { 110 final_a = 1; 111 } 112 } else { 113 Point temp = Point(A.x - vx, A.y - vy); 114 if (r > distoSegment(O, Segment(A, temp))) { 115 Point jiaodian = GetPoint(O, r, A); 116 //printf("%lf:%lf",jiaodian.x,jiaodian.y); 117 double ang1 = ang(jiaodian, O, A); 118 double ang2 = ang(jiaodian, B, O); 119 //printf("%lf %lf\n",ang1,ang2); 120 if (abs(ang1 - ang2) < eps) final_a = 1; 121 } 122 } 123 } else if (distoSegment(O, Segment(A,B)) < eps) { 124 Point tt = Point(1001, 0); 125 if (abs(ang(O, A, tt) - ang(O, Point(O.x - vx, O.y - vy), tt)) < eps) { 126 final_a = 1; 127 } 128 } else { 129 //cout << endl<<endl; 130 if (abs(vy * (A.x - B.x) - vx * (A.y - B.y)) < eps) { 131 Point jiaodian = GetPoint(O, r, A); 132 133 if (dis(jiaodian, A) > dis(B,A)) { 134 135 Point tt = Point(1001, A.y); 136 if (abs(ang(A, tt, B) - ang(Point(B.x - vx, B.y - vy), Point(1001, B.y - vy), B)) < eps) { 137 final_a = 1; 138 } 139 } 140 } 141 } 142 if (final_a) printf("Case #%d: Yes\n",t); 143 else printf("Case #%d: No\n",t); 144 } 145 return 0; 146 }
B - Binary Tree
发现最左边的那条链,把除最后一个点都置为负
比如 -1 -2 -4 8 此时和为1
依次把 -1 取正，-2取证，可以得到 3、5、7、9...所有的奇数
把8取右子节点，可以得到2、4、6...所有偶数
根据n的二进制为判断是否要取正，注意奇偶就行
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 typedef long long LL; 5 6 LL n, a[65]; 7 int b[65], k; 8 9 LL qpow(LL a, int n) { 10 LL res = 1; 11 while (n) { 12 if (n & 1) res *= a; 13 a *= a; 14 n >>= 1; 15 } 16 return res; 17 } 18 19 int main() { 20 int T; scanf("%d", &T); 21 for (int cas = 1; cas <= T; ++cas) { 22 scanf("%lld%d", &n, &k); 23 memset(b, -1, sizeof(b)); 24 for (int i = 1; i <= k; ++i) a[i] = qpow(2, i - 1); 25 if (!(n & 1)) a[k]++, n -= 2; 26 b[k] = 1; 27 int now = 1; 28 while (n >>= 1) { 29 if (n & 1) b[now] = 1; 30 now++; 31 } 32 printf("Case #%d:\n", cas); 33 for (int i = 1; i <= k; ++i) 34 printf("%lld %c\n", a[i], b[i] == 1 ? ‘+‘ : ‘-‘); 35 } 36 return 0; 37 }
F - Friendship of Frog
签到题．手动打表
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 map<char,int> shit; 5 char fuck[1005]; 6 int main() { 7 int n; scanf("%d",&n); 8 for(int ks = 1; ks <= n; ks++) { 9 shit.clear(); 10 scanf("%s",fuck); 11 int len = int(strlen(fuck)); 12 int ans = 1e9; 13 for (int i = 0; i < len; i++) { 14 if(shit.count(fuck[i])) 15 ans = min(i - shit[fuck[i]], ans); 16 shit[fuck[i]] = i; 17 } 18 if (ans == 1e9) ans = -1; 19 printf("Case #%d: %d\n",ks,ans); 20 } 21 }
K - Kingdom of Black and White
贪心的跑，先考虑一个长度的，这样可以连通两个块．在跑一边关于长度差的，就是a > b长度的2 *(abs(a-b)+1)．跑一遍取最大值
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <cstring> 6 #include <cmath> 7 using namespace std; 8 const int N = 1e5 + 5; 9 typedef long long LL; 10 11 char s[N]; 12 vector <int> vec; 13 14 int main() { 15 int t; scanf("%d", &t); 16 for (int cas = 1; cas <= t; ++cas) { 17 vec.clear(); 18 scanf("%s", s); 19 int n = strlen(s); 20 int cnt = 1; 21 for (int i = 1; i < n; ++i) 22 if (s[i] != s[i - 1]) vec.push_back(cnt), cnt = 1; 23 else cnt++; 24 vec.push_back(cnt); 25 26 // for (int i = 0; i < (int) vec.size(); ++i) 27 // printf("vec[%d]=%d ", i + 1, vec[i]); 28 // cout << endl; 29 30 31 LL sum = 0; 32 for (int i = 0; i < (int) vec.size(); ++i) sum += 1LL * vec[i] * vec[i]; 33 LL ans = sum, tmp; 34 35 // printf("sum = %lld\n", sum); 36 37 int ed = (int) vec.size() - 1; 38 LL maxn2 = 0; 39 for (int i = 0; i < (int) vec.size(); ++i) 40 if (vec[i] == 1) { 41 if (i != 0 && i != ed) { 42 LL a = 1LL * vec[i - 1]; 43 LL b = 1LL * vec[i + 1]; 44 tmp = (a + 1 + b); 45 tmp = tmp * tmp - (1LL * a * a + b * b + 1); 46 // printf("a = %lld, b = %lld, tmp = %lld\n", a, b, tmp); 47 maxn2 = max(maxn2, tmp); 48 } 49 } 50 LL maxn = 0; 51 for (int i = 1; i < (int) vec.size(); ++i) { 52 maxn = max(maxn, 1LL * 2 * abs(vec[i] - vec[i - 1]) + 2); 53 //printf("maxn = %lld, ", maxn); 54 } 55 ans = max(ans + maxn, ans + maxn2); 56 printf("Case #%d: %lld\n", cas, ans); 57 } 58 return 0; 59 }
L - LCM Walk
关于跳．(x,y)跳到(x,y+lcm(x,y))或者(x+lcm(x,y),y),首先做处理，让gcd(x,y)＝１,然后(x<y)时考虑(x,y)一定是从(x,p)跳到的，
互质所以有(xp+p)=y,就判断一下y%(x+1),这里我把跳０步忽略了，放在最后＋１了．
1 #include <cstdio> 2 #include <iostream> 3 #define ll long long 4 using namespace std; 5 6 ll dfs(int x, int y) { 7 if (x > y) swap(x, y); 8 if (x<=1 && y <= 1) return 0; 9 if (y % (x + 1) != 0) return 0; 10 return 1 + dfs(x, (y / (x + 1))); 11 } 12 13 int gcd(int a, int b) { 14 return b ? gcd(b, a % b) : a; 15 } 16 17 int main() { 18 int t = 0, T; scanf("%d",&T); 19 while (t++ < T) { 20 int x,y; 21 ll ans; 22 scanf("%d%d",&x,&y); 23 int d = gcd(x, y); 24 x /= d; y /= d; 25 if (x > y) swap(x, y); 26 if (y % (x + 1) != 0) ans = 0; 27 else ans = dfs(x, y); 28 printf("Case #%d: %lld\n", t, ans + 1); 29 } 30 }
# 7-19题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。