Codeforces Round #379 (Div. 2) 总结分享

前言

　　初入acm的新手，打算在cf混。这几天没有比赛，就做了个最新的Virtual participation。虽然说div2比较简单，但还是被虐得体无完肤。。。Orz。两个小时，共6道题。最后只AC了AB两道，花了20分钟，剩下的100分钟也不知道哪去了（逃

A、B两道水题没什么说的。那我们从C题开始吧

C. Anton and Making Potions

题意

　　制作n瓶药水，初始时每制作一瓶花费x秒，有两类法术，第一类（包含m个法术）使制作每瓶药的时间由x变为a[i] (a[i] < x) 并消耗b[i]点法力值，第二种（k个法术）能瞬间制造c[i]瓶并消耗d[i]点法力值，初始法力值为s，最多在两种类型中分别选一个法术来加快进度。求制作这n瓶药水最少花费的时间。

思路

　　暴力法肯定爆时间O(m*k)，所以没敢用，就去纠结各种“巧妙”的办法，然后。。。然后时间就过去了T.T 结束之后看Tutorial，第一类就暴力，第二类在第一类的基础上二分查找，这样O(m*log₂k)就不会爆了。之前从未想过二分法查找近似数（如：找到比给定值小的最大元素），这里第二类本身是有序（非递减）的，正好用二分法。

代码

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int max_n = 1000000;
 6 
 7 int n, m, k;
 8 int x, s;
 9 int a[max_n], b[max_n], c[max_n], d[max_n];
10 
11 inline int max_complete(int mana_left)
12 {
13     int l = 0, r = k;
14     while (l < r)
15     {
16         int m = (l + r + 1) / 2;
17         if (d[m] <= mana_left) l = m; else r = m-1;
18     }
19     return c[l];
20 }
21 
22 int main()
23 {
24     cin >> n >> m >> k;
25     cin >> x >> s;
26     a[0] = x;
27     b[0] = 0;
28     c[0] = 0;
29     d[0] = 0;
30     for (int i = 1; i <= m; i++) cin >> a[i];
31     for (int i = 1; i <= m; i++) cin >> b[i];
32     for (int i = 1; i <= k; i++) cin >> c[i];
33     for (int i = 1; i <= k; i++) cin >> d[i];
34     long long ans = 1LL * n * x;
35     for (int i = 0; i <= m; i++)
36     {
37         int mana_left= s - b[i];
38         if (mana_left< 0) continue;
39         ans = min(ans, 1LL * (n - max_complete(mana_left)) * a[i]);
40     }
41     cout << ans << endl;
42     return 0;
43 }

Unfold Code

分析

　　虽然最大只有2e5，内存足够的情况下，max_n大一点更好，避免编程是改来改去的；

　　abcd[0]存放特殊元素，好处是使后续操作统一化（不必写额外语句去判断特殊情况）；

　　数字的LL后缀代表这是一个long long型变量，1LL*int 使int变为long long（C语言基础，不同数据范围的运算，得到范围较大的类型）；

小结

　　二分法一定要好好写啊，考虑清楚再写，避免消耗过多时间。（这个二分法，搞了半小时....Orz）；

D. Anton and Chess

题意

　　一个无限大的棋盘，一个白王和n个黑色棋子（车、象、皇三种），判断白王是否被将军了。车走十字，象走对角线，皇既可走十字，又可走对角线。

思路

　　在王的八个方向中，判断每个方向离王最近的黑棋能否将军即可。知道王的坐标，八个方向可以用函数表示出来，分别为y=y0，x=x0，y=x+y0-x0，y=-x+y0+x0。黑棋坐标代进去就知道是不是在八个方向上，找到最近的八个判断就行了。

代码

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int max_n = 1000000;
 6 
 7 typedef struct {
 8     char type;
 9     int x;
10     int y;
11 }piece;
12 
13 int n, X, Y;
14 piece a[max_n], near[9];
15 int main()
16 {
17     cin >> n;
18     cin >> X >> Y; // white king
19     for(int i=0; i<n; i++) {
20         cin >> a[i].type >> a[i].x >> a[i].y;
21     }
22     for(int i=0; i<n; i++) {
23         if(a[i].x == X) {
24             if(a[i].y > Y) {
25                 if(near[3].type==0 || a[i].y-Y < near[3].y-Y) {
26                     near[3] = a[i];
27                 }
28             } else {
29                 if(near[7].type==0 || a[i].y-Y > near[7].y-Y) {
30                     near[7] = a[i];
31                 }
32             }
33         } else if(a[i].y == Y) {
34             if(a[i].x > X) {
35                 if(near[1].type==0 || a[i].x-X < near[1].x-X) {
36                     near[1] = a[i];
37                 }
38             } else {
39                 if(near[5].type==0 || a[i].x-X > near[5].x-X) {
40                     near[5] = a[i];
41                 }
42             }
43         } else if(a[i].y == a[i].x + Y - X) {
44             if(a[i].x > X) {
45                 if(near[2].type==0 || a[i].x-X < near[2].x-X) {
46                     near[2] = a[i];
47                 }
48             } else {
49                 if(near[6].type==0 || a[i].x-X > near[6].x-X) {
50                     near[6] = a[i];
51                 }
52             }
53         } else if(a[i].y == -1 * a[i].x + Y + X){
54             if(a[i].x > X) {
55                 if(near[8].type==0 || a[i].x-X < near[8].x-X) {
56                     near[8] = a[i];
57                 }
58             } else {
59                 if(near[4].type==0 || a[i].x-X > near[4].x-X) {
60                     near[4] = a[i];
61                 }
62             }
63         }
64     }
65     for(int i=1; i<=8; i+=2) {
66         if(near[i].type==0) continue;
67         if(near[i].type == 'Q' || near[i].type == 'R') {
68             cout << "YES";
69             return 0;
70         }
71     }
72     for(int i=2; i<=8; i+=2) {
73         if(near[i].type==0) continue;
74         if(near[i].type == 'Q' || near[i].type == 'B') {
75             cout << "YES";
76             return 0;
77         }
78     }
79     cout << "NO";
80     return 0;
81 }

Unfold Code

分析

　　白王坐标（X,Y），黑棋用结构体定义，遍历所有黑棋，用near[9]来储存最近的八个棋子，最后遍历这八个棋子，然后AC！

小结

　　总体来说不难，比C题更容易想到，也没有用复杂的算法和数据结构。

E. Anton and Tree

题意

　　一个无环无向图(acyclic undirected gragh)，有白和黑两种颜色的顶点，一次选择一个顶点，使与其连通的相同颜色的顶点一起变为另一种颜色。欲使所有顶点变成同一种颜色，求最少执行几次操作？

思路

　　既然同一块连通的颜色一起改变，那就可以把这样的一块压缩成一个点；可以用一个线性表来储存原图顶点与压缩图顶点的对应编号，①.每次选一个点dfs，确定出一个压缩点，也就是说：所有点访问一遍就能确定每个原图顶点与压缩图顶点的对应编号（此时还没形成压缩图的边）；②.然后再遍历一次原图，通过比较邻接点的颜色与自身是否相同，来确定哪些压缩点之间是存在边的。通过这两个操作就能构建一个压缩顶点图，然后再找到这个无环无向图的最长路径/2就是结果（压缩后的图是黑白相间的，随便画一条出来看看就知道了）；关键是如何找到这条最长路径，其实很简单，先随便找一个点v，找到离点v距离最远的点s，则s必定是最长路径两端点的其中之一，这里可用反证法证明（设最长路另一端点为t，假设存在一个不是最长路端点s'的点到v的距离大于s，则最长路将会是s'---t，而不是s---t，矛盾）；再由s找到距离最远的点t，这个距离就是最长路径长度，使用这种方法只需要遍历两次图

代码

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n, cn, diameter=1, s;
 6 vector < vector<int> > g;
 7 vector < vector<int> > cg;
 8 vector <int> color;
 9 vector <bool> viewed;
10 vector <int> comp;
11 
12 void comp_dfs(int v, int col) {
13     comp[v] = cn;
14     viewed[v] = true;
15     int len = g[v].size();
16     for(int i=0; i<len; i++) {
17         if(viewed[g[v][i]] || color[g[v][i]]!=col) continue;
18         comp_dfs(g[v][i], col);
19     }
20 }
21 
22 void dfs(int v, int d) {
23     viewed[v] = true;
24     int len = cg[v].size();
25     for(int i=0; i<len; i++) {
26         if(viewed[cg[v][i]]) continue;
27         dfs(cg[v][i],d+1);
28     }
29     if(d>diameter) {
30         diameter = d;
31         s = v;
32     }
33 }
34 
35 int main()
36 {
37     std::ios::sync_with_stdio(false);
38     cin >> n;
39     g.resize(n);
40     color.resize(n);
41     for(int i=0; i<n; i++) {
42         cin >> color[i];
43     }
44     viewed.resize(n);
45     viewed.assign(n,false);
46     for(int i=0; i<n-1; i++) {
47         int v1, v2;
48         cin >> v1 >> v2;
49         v1--;
50         v2--;
51         g[v1].push_back(v2);
52         g[v2].push_back(v1);
53     }
54     comp.resize(n);
55     cg.resize(n);
56     // compress
57     for(int i=0; i<n; i++) {
58         if(!viewed[i]) {
59             comp_dfs(i,color[i]);
60             cn++;
61         }
62     }
63     // link
64     for(int i=0; i<n; i++) {
65         int len = g[i].size();
66         for(int j=0; j<len; j++) {
67             if(color[i] != color[g[i][j]]) {
68                 cg[comp[i]].push_back(comp[g[i][j]]);
69             }
70         }
71     }
72     viewed.resize(cn);
73     viewed.assign(cn,false);
74     dfs(0,1);
75     viewed.assign(cn,false);
76     dfs(s,1);
77     cout << (diameter)/2;
78     return 0;
79 }

Unfold Code

分析

　　明显，用vector向量代替链表来构建邻接表更简单（这就是c++比c方便的地方：STL）;

　　comp_dsf只是将最初传入的顶点与其连通的同色点压缩成一个点（赋予相同的压缩后编号），并没有建立压缩后的边；

　　压缩完所有块后，再遍历原图，颜色不同的相邻点之间必定存在边；

小结

Codeforces Round #379 (Div. 二) 总结分享

前言

C. Anton and Making Potions

题意

思路

代码

分析

小结

D. Anton and Chess

题意

思路

代码

分析

小结

E. Anton and Tree

题意

思路

代码

分析

小结

相关推荐