ABC 252 - 254 题解（C, D)

ABC 252

本场RP = INT_MIN。

C

我们的Takahashi太不灵活了吧……

对于每个数字，我们都在这个数字停下来时看一看（如888,666等）

这里我们分“轮”的概念（因为Takahashi不能1秒按两个），一轮为10秒。

弄个cnt数组就好办了。

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <set>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 
20 using namespace std;
21 
22 string s[105];
23 int place[105][10];
24 int cnt[10];
25 
26 int main() {
27     int N;
28     cin >> N;
29     for (int i = 0; i < N; i++) {
30         cin >> s[i];
31     } 
32     for (int i = 0; i < N; i++) {
33         for (int j = 0; j < 10; j++) {
34             place[i][s[i][j] - '0'] = j;
35         }
36     }
37     int ans = 0x3f3f3f3f;
38     for (int i = 0; i < 10; i++) {
39         memset(cnt, 0, sizeof(cnt));
40         for (int j = 0; j < N; j++) {
41             cnt[place[j][i]]++;
42         }
43         int this_ans = 0;
44         for (int j = 0; j < 10; j++) {
45             this_ans = max(this_ans, j + (cnt[j] - 1) * 10);
46         }
47         ans = min(ans, this_ans);
48     }
49     cout << ans;
50     return 0;
51 }

广告：Think twice, Code once!

D

首先统计每个数出现了多少次。

假设说有四个数，分别出现a1, a2, a3, a4次……

 a1*a2*a3+a1*a2*a4+a1*a3*a4+a2*a3*a4

= a1*a2*(a3+a4)+a3*a4*(a1+a2)

= (a1)*a2*(a3+a4)+(a1+a2)*a3*(a4)

大胆猜测答案是中间所有数的prefix*now*suffix。

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <set>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 
20 using namespace std;
21 
22 #define maxn 200005
23 
24 long long sum[maxn];
25 
26 int main() {
27     int n;
28     scanf("%d", &n);
29     int tmp;
30     for (int i = 0; i < n; i++) {
31         scanf("%d", &tmp);
32         sum[tmp]++;
33     }
34     for (int i = 1; i < 200003; i++) {
35         sum[i] += sum[i - 1];
36     }
37     long long ans = 0;
38     for (int i = 1; i < 200002; i++) {
39         ans += (sum[i - 1] - 0) * (sum[i] - sum[i - 1]) * (sum[200002] - sum[i]);
40     }
41     printf("%lld", ans);
42     return 0;
43 }

广告：Think twice, Code once!

ABC 253

本场RP = INT_MAX。

对了，最近我把int RP给废除了，换了个long double RP。

C

过于兴奋的我打了个暴力交上去，然后就TLE了。

我又换成了map交上去，就AC了。

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <set>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 
20 using namespace std;
21 
22 multiset<int> s;
23 
24 int main() {
25     int Q;
26     scanf("%d", &Q);
27     while (Q--) {
28         int tp;
29         scanf("%d", &tp);
30         if (tp == 1) {
31             int x;
32             scanf("%d", &x);
33             s.insert(x);
34         } else if (tp == 2) {
35             int x, c;
36             scanf("%d %d", &x, &c);
37               while (c-- && s.find(x) != s.end()) {
38                 s.erase(s.find(x));
39             }
40         } else {
41             printf("%d\n", *(s.rbegin()) - *(s.begin()));
42         }
43     }
44     return 0;
45 }

 广告：Think twice, Code once!

D

容！斥！原！理！数！学！题！

还！要！会！等！差！数！列！

我！要！请！他！去！喝！茶！

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <set>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 
20 using namespace std;
21 
22 int main() {
23     long long n, a, b;
24     scanf("%lld %lld %lld", &n, &a, &b);
25     long long ans = 0;
26     ans += (1 + n) * n / 2;
27     ans -= (a + n / a * a) * (n / a) / 2;
28     ans -= (b + n / b * b) * (n / b) / 2;
29     long long c = a / __gcd(a, b) * b;
30     ans += (c + n / c * c) * (n / c) / 2;
31     printf("%lld", ans);
32     return 0;
33 }

广告：Think twice, Code once!

ABC 254

本场RP = LONG_LONG_MAX。

这次不是CD，是CE。

C

我们可以先把数组重排一下，如：

n = 5, k = 3

1 3 2 4 6 -> 1 4 3 6 2

模k相同的就放一起呗，然后给每段排序。

再重新构造原数组，用上神器剧毒屠龙刀is_sorted就行了。

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <set>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 
20 using namespace std;
21 
22 #define maxn 200005
23 
24 pair<int, int> a[maxn];
25 int b[maxn];
26 
27 int main() {
28     int n, k;
29     scanf("%d %d", &n, &k);
30     for (int i = 0; i < n; i++) {
31         a[i].first = i % k;
32         scanf("%d", &a[i].second);
33     }
34     sort(a, a + n);
35     int idx = 0;
36     b[0] = a[0].second;
37     for (int i = 1; i < n; i++) {
38         if (a[i].first != a[i - 1].first) {
39             idx = a[i].first;
40         } else {
41             idx += k;
42         }
43         b[idx] = a[i].second;
44     }
45     if (is_sorted(b, b + n)) {
46         puts("Yes");
47     } else {
48         puts("No");
49     }
50     return 0;
51 }

广告：Think twice, Code once!

E

裸DBFS就行了。

至于题解说的暴力方法，傻子才会去写那个。

注意BFS时带上层数。

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <set>
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 
20 using namespace std;
21 
22 #define maxn 150005
23 
24 vector<int> gg[maxn];
25 bool vis[maxn];
26 
27 long long bfs(int x, int k) {
28     queueint, int>> bfs_q;
29     bfs_q.push({x, k});
30     vis[x] = 1;
31     int ans = 0;
32     while (bfs_q.size()) {
33         pair<int, int> cur = bfs_q.front();
34         bfs_q.pop();
35         ans += cur.first + 1;
36         if (cur.second != 0) {
37             for (int adj : gg[cur.first]) {
38                 if (!vis[adj]) {
39                     vis[adj] = true;
40                     bfs_q.push({adj, cur.second - 1});
41                 }
42             }
43         }
44     }
45     return ans;
46 }
47 
48 int main() {
49     int n, m;
50     scanf("%d %d", &n, &m);
51     for (int i = 0; i < m; i++) {
52         int a, b;
53         scanf("%d %d", &a, &b);
54         gg[a - 1].push_back(b - 1);
55         gg[b - 1].push_back(a - 1);
56     }
57     int q;
58     scanf("%d", &q);
59     while (q--) {
60         int x, k;
61         scanf("%d %d", &x, &k);
62         memset(vis, 0, sizeof(vis));
63         printf("%lld\n", bfs(x - 1, k));
64     }
65     return 0;
66 }

广告：博主QQ3131380469，Atcoder Rating 862，谁来加我好友呀——

题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签