ACM-ICPC Asia Training League 暑假第一阶段第四场 ABCDH

模拟这个

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 5e6+10;
 5 int t, q, p, m, n;
 6 unsigned int sa, sb, sc;
 7 ll a[N], st[N], top;
 8 ll MAX[N];
 9 unsigned int f() {
10     sa ^= sa<<16;
11     sa ^= sa >> 5;
12     sa ^= sa << 1;
13     unsigned int t = sa;
14     sa = sb;
15     sb = sc;
16     sc ^= t^sa;
17     return sc;
18 }
19 
20 int main() {
21     scanf("%d", &t);
22     for(int ca = 1; ca <= t; ca ++){
23         top = 0;
24         scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &sa, &sb, &sc);
25         for(int i = 1; i <= n; i ++) {
26             if(f()%(p+q) < p) {
27                 int tmp = f()%m+1;
28                 st[++top] = tmp;
29                 MAX[top] = max(st[top], MAX[top-1]); 
30                 a[i] = MAX[top];
31             } else{
32                 if(top == 0) a[i] = 0;
33                 else a[i] = MAX[--top];
34             }
35         }
36         ll ans = 0;
37         for(ll i = 1; i <= n; i ++) {
38             ans ^= i*a[i];
39         }
40         printf("Case #%d: %lld
",ca,ans);
41     }
42     return 0;
43 }

B Rolling The Polygon

Bahiyyah has a convex polygon with $P_0, P_1, cdots, P_{n-1}P0,P1,⋯,Pn−1 in the counterclockwise order.Two vertices with consecutive indexes are adjacent, and besides, P_0P0 and P_{n-1}Pn−1 are adjacent.She also assigns a point QQ inside the polygon which may appear on the border.$

Now, Bahiyyah decides to roll the polygon along a straight line and calculate the length of the trajectory (or track) of point

To help clarify, we suppose $P_n = P_0, P_{n+1} = P_1Pn=P0,Pn+1=P1 and assume the edge between P_0P0 and P_1P1 is lying on the line at first.At that point when the edge between P_{i-1}Pi−1 and P_iPi lies on the line, Bahiyyah rolls the polygon forward rotating the polygon along the vertex P_iPi until the next edge (which is between P_iPi and P_{i+1}Pi+1) meets the line.She will stop the rolling when the edge between P_nPn and P_{n+1}Pn+1 (which is same as the edge between P_0P0 and P_1P1) meets the line again.$

Input Format

The input contains several test cases, and the first line is a positive integer

For each test case, the first line contains an integer $x_{i-1}xi−1 and y_{i-1}yi−1, which are the coordinates of point P_{i-1}Pi−1.The last line contains two integers x_QxQ and y_QyQ, which are the coordinates of point QQ.$

We guarantee that all coordinates are in the range of $-10^3−103 to 10^3103, and point QQ is located inside the polygon or lies on its border.$

Output Format

For each test case, output a line containing Case #x: y, where

Hint

The following figure is the the trajectory of the point

样例输入

样例输出

Case #1: 8.886
Case #2: 7.318
Case #3: 12.102
Case #4: 14.537

给定N边形和一个点，转一圈后点走的轨迹路径是多少。
n个弧，半径为QPi

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 const double PI = acos(-1);
 6 struct Point{
 7     double x, y;
 8 }p[55];
 9 
10 double dis(Point a, Point b) {
11     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
12 }
13 
14 double ang(Point a, Point b, Point c) {
15     double x1 = dis(a,b);
16     double x2 = dis(c,b);
17     double x3 = dis(a,c);
18     return acos((x1*x1+x2*x2-x3*x3)/(2*x1*x2));
19 }
20 int main() {
21     int t, n;
22     cin >>t;
23     for(int ca = 1; ca <= t; ca ++) {
24         cin >> n;
25         for(int i = 0; i <= n; i ++) {
26             cin >> p[i].x >> p[i].y;
27         }
28         double ans = 0;
29         for(int i = 0; i < n; i ++) {
30             ans += dis(p[n],p[i])*(PI-ang(p[(i-1+n)%n], p[i], p[(i+1+n)%n]));
31         }
32         printf("Case #%d: %.3lf
",ca,ans);
33     }
34     return 0;
35 }

C 签到题

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 55;
 5 char s1[N], s2[N], s3[N];
 6 int main() {
 7     int t;
 8     cin >> t;
 9     for(int i = 1; i <= t; i ++) {
10         int n, m;
11         memset(s1, 0, sizeof(s1));
12         memset(s2, 0, sizeof(s2));
13         memset(s3, 0, sizeof(s3));
14         cin >> n >> m;
15         cin >> s1 >> s2 >> s3;
16         int ans = s1[0]-s2[0];
17         for(int j = 0; s3[j]; j ++) {
18             s3[j] += ans;
19             if(s3[j] < 'A') s3[j] += 26;
20             else if(s3[j] > 'Z') s3[j] -= 26;
21         }
22         printf("Case #%d: %s
",i,s3);
23     }
24     return 0;
25 }

D 找规律。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 
 6 int main() {
 7     int t, n, m;
 8     cin >> t;
 9     for(int ca = 1; ca <= t; ca ++) {
10         cin >> n >> m;
11         double ans1 = 0.5, ans2 = 1.0*(m+1)/(2*m);
12         if(n == 1) ans1 = 1.0;
13         if(m == 1) ans2 = 1.0;
14         printf("Case #%d: %.6lf %.6lf
",ca,ans1,ans2);
15     }
16     return 0;
17 }

H 题

按血量与攻击次数的比值从大到小选

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 int t, n, x;
 6 int cnt[1010];
 7 struct Nod{
 8     int num, a;
 9 
10 }e[N];
11 
12 bool cmp(Nod a, Nod b) {
13     if(1.0*a.a/a.num !=  1.0*b.a/b.num)return 1.0*a.a/a.num > 1.0*b.a/b.num;
14     else return a.a > b.a;
15 }
16 
17 int main() {
18     for(int i = 1; i <= 1000; i ++) {
19         cnt[i] = cnt[i-1] + i;
20     }
21     cin >> t;
22     for(int ca = 1; ca <= t; ca ++) {
23         cin >> n;
24         ll ans = 0;
25         for(int i = 1; i <= n; i ++) {
26             scanf("%d%d", &x, &e[i].a);
27             ans += e[i].a;
28             e[i].num = lower_bound(cnt+1,cnt+1000,x) - cnt;
29         }
30         sort(e+1,e+1+n,cmp);
31         ll cnt = 0;
32         for(int i = 1; i <= n; i ++) {
33             // printf("%d %d
",e[i].num,e[i].a);
34             cnt += e[i].num*ans;
35             ans -= e[i].a;
36         }
37         printf("Case #%d: %lld
",ca,cnt);
38 
39     }
40     return 0;
41 }