Codeforces Round #487 (Div. 2)
分类:
IT文章
•
2022-07-29 11:37:19
A. A Blend of Springtime
暴力
1 #include <bits/stdc++.h>
2 using namespace std;
3 char s[111];
4
5 int main() {
6 scanf("%s", s + 1);
7 int l = strlen(s + 1), ok = 0;
8 for(int i = 1; i <= l; ++i) {
9 if(s[i] == 'A' && s[i-1] == 'B' && s[i+1] == 'C') ok = 1;
10 if(s[i] == 'A' && s[i-1] == 'C' && s[i+1] == 'B') ok = 1;
11 if(s[i] == 'B' && s[i-1] == 'A' && s[i+1] == 'C') ok = 1;
12 if(s[i] == 'B' && s[i-1] == 'C' && s[i+1] == 'A') ok = 1;
13 if(s[i] == 'C' && s[i-1] == 'A' && s[i+1] == 'B') ok = 1;
14 if(s[i] == 'C' && s[i-1] == 'B' && s[i+1] == 'A') ok = 1;
15 }
16 puts(ok ? "Yes" : "No");
17 return 0;
18 }
Aguin
B. A Tide of Riverscape
暴力(这不本来就On吗- -)
1 #include <bits/stdc++.h>
2 using namespace std;
3 char s[2222];
4
5 int main() {
6 int n, p, ok = 0;
7 scanf("%d %d %s", &n, &p, s + 1);
8 for(int i = p + 1; i <= n; ++i) {
9 if(s[i] == '.') {
10 if(s[i-p] == '.') s[i-p] = '0', s[i] = '1', ok = 1;
11 else s[i] = '1' + '0' - s[i-p], ok = 1;
12 }
13 else {
14 if(s[i-p] == '.') s[i-p] = '1' + '0' - s[i], ok = 1;
15 else if(s[i-p] != s[i]) ok = 1;
16 }
17 }
18 if(!ok) puts("No");
19 else {
20 for(int i = 1; i <= n; ++i)
21 if(s[i] == '.') s[i] = '0';
22 puts(s + 1);
23 }
24 return 0;
25 }
Aguin
C. A Mist of Florescence
大概的想法都是把一个颜色嵌到另一个颜色里面
1 #include <bits/stdc++.h>
2 using namespace std;
3 int G[55][55];
4
5 int main() {
6 int a, b, c, d;
7 scanf("%d %d %d %d", &a, &b, &c, &d);
8 a--, b--;
9 for(int i = 1; i <= 50; ++i) {
10 for(int j = 1; j <= 25; ++j) {
11 if(i & 1) G[i][j] = 1;
12 else if(j & 1) G[i][j] = 1;
13 }
14 for(int j = 26; j <= 50; ++j){
15 if(i & 1) G[i][j] = 2;
16 else if(!(j & 1)) G[i][j] = 2;
17 }
18 }
19 for(int i = 1; i <= 50; ++i)
20 for(int j = 1; j <= 25; ++j)
21 if(b && !G[i][j]) b--, G[i][j] = 2;
22 for(int i = 1; i <= 50; ++i)
23 for(int j = 26; j <= 50; ++j)
24 if(a && !G[i][j]) a--, G[i][j] = 1;
25 for(int i = 1; i <= 50; ++i)
26 for(int j = 1; j <= 50; ++j)
27 if(c && !G[i][j]) c--, G[i][j] = 3;
28 for(int i = 1; i <= 50; ++i)
29 for(int j = 1; j <= 50; ++j)
30 if(d && !G[i][j]) d--, G[i][j] = 4;
31 for(int i = 1; i <= 50; ++i)
32 for(int j = 1; j <= 25; ++j)
33 if(!G[i][j]) G[i][j] = 1;
34 for(int i = 1; i <= 50; ++i)
35 for(int j = 26; j <= 50; ++j)
36 if(!G[i][j]) G[i][j] = 2;
37 puts("50 50");
38 for(int i = 1; i <= 50; ++i){
39 for(int j = 1; j <= 50; ++j) {
40 putchar('A' - 1 + G[i][j]);
41 }
42 puts("");
43 }
44 return 0;
45 }
Aguin
D. A Shade of Moonlight
转化成月亮动比较显然,然后利用x-t图写出满足要求的不等式,枚举一个方向,另一个方向解不等式二分
我特判了一个w=1的情况
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 vector<LL> L, R;
5
6 int main() {
7 LL n, l, w;
8 cin >> n >> l >> w;
9 for(int i = 1; i <= n; ++i) {
10 LL x, v;
11 cin >> x >> v;
12 if(v == -1) L.push_back(x);
13 else R.push_back(x);
14 }
15 sort(R.begin(), R.end());
16 LL ans = 0;
17 for(int i = 0; i < L.size(); ++i) {
18 if(w == 1 && L[i] + l <= 0) continue;
19 int lb = lower_bound(R.begin(), R.end(), 1.0 * (w - 1) * (L[i] + l) / (w + 1)) - R.begin();
20 if(w != 1) lb = min(lb, lower_bound(R.begin(), R.end(), 1.0 * (w + 1) * (L[i] + l) / (w - 1)) - R.begin());
21 ans += lb;
22 }
23 cout << ans << endl;
24 return 0;
25 }
Aguin
1 #include <bits/stdc++.h>
2 using namespace std;
3 const double pi = acos(-1);
4 const double eps = 1e-8;
5 const int maxn = 205;
6 int x[maxn], y[maxn];
7
8 struct Matrix {
9 double a[maxn][maxn];
10 void init() {
11 memset(a, 0, sizeof(a));
12 for (int i = 0; i < maxn; ++i) {
13 a[i][i] = 1;
14 }
15 }
16 } P[14];
17
18 Matrix mul(Matrix a, Matrix b) {
19 Matrix ans;
20 memset(ans.a, 0, sizeof(ans.a));
21 for (int i = 0; i < maxn; ++i) {
22 for (int k = 0; k < maxn; ++k) {
23 if (a.a[i][k] != 0)
24 for (int j = 0; j < maxn; ++j) {
25 ans.a[i][j] += a.a[i][k] * b.a[k][j];
26 }
27 }
28 }
29 return ans;
30 }
31
32 typedef pair<double, int> pdi;
33 vector<pdi> v;
34
35 double d[maxn], e[maxn];
36 int main() {
37 int n, q;
38 scanf("%d", &n);
39 for (int i = 1; i <= n; ++i) scanf("%d %d", x + i, y + i);
40 for (int i = 1; i <= n; ++i) {
41 v.clear();
42 for (int j = 1; j <= n; ++j) {
43 if (j == i) continue;
44 double theta = atan2(x[j] - x[i], y[j] - y[i]);
45 while (theta < 0) theta += pi;
46 while (theta >= pi) theta -= pi;
47 v.push_back(pdi(theta, j));
48 }
49 sort(v.begin(), v.end());
50 int line = 0;
51 for (int j = 0, k; j < n - 1;) {
52 for (k = j; k < n - 1 && fabs(v[k].first - v[j].first) < eps; ++k);
53 j = k, line++;
54 }
55 for (int j = 0, k; j < n - 1;) {
56 for (k = j; k < n - 1 && fabs(v[k].first - v[j].first) < eps; ++k);
57 for (int p = j; p < k; ++p) P[0].a[v[p].second][i] += 1.0 / line / (k - j + 1);
58 P[0].a[i][i] += 1.0 / line / (k - j + 1);
59 j = k;
60 }
61 }
62 for(int i = 1; i < 14; ++i) P[i] = mul(P[i-1], P[i-1]);
63 scanf("%d", &q);
64 while (q--) {
65 int t, m;
66 scanf("%d %d", &t, &m);
67 m--;
68 memset(d, 0, sizeof(d));
69 d[t] = 1;
70 for(int i = 0; i < 14; ++i) {
71 if(m & (1 << i)) {
72 memset(e, 0, sizeof(e));
73 for(int j = 1; j <= n; ++j)
74 for(int k = 1; k <= n; ++k)
75 e[j] += P[i].a[k][j] * d[k];
76 memcpy(d, e, sizeof(d));
77 }
78 }
79 double ans = 0;
80 for (int i = 1; i <= n; ++i) {
81 v.clear();
82 for (int j = 1; j <= n; ++j) {
83 if (j == i) continue;
84 double theta = atan2(x[j] - x[i], y[j] - y[i]);
85 while (theta < 0) theta += pi;
86 while (theta >= pi) theta -= pi;
87 v.push_back(pdi(theta, j));
88 }
89 sort(v.begin(), v.end());
90 for (int j = 0, k; j < n - 1;) {
91 double tmp = 0;
92 for (k = j; k < n - 1 && fabs(v[k].first - v[j].first) < eps; ++k);
93 for (int p = j; p < k; ++p) tmp += d[v[p].second] / (k - j + 1);
94 tmp += d[i] / (k - j + 1);
95 ans = max(ans, tmp);
96 j = k;
97 }
98 }
99 printf("%.10f
", ans);
100 }
101 return 0;
102 }