Codeforces Round #357 (Div. 2)
5/5
果然上一篇博文是个flag啊!我果然拖更了!昨天的CF完了还没有更新上一次的CF题解,所以昨天差点GG(不过第三题这个分数也离GG不远了,好在rating没掉(/▽╲))。为了攒回人品,于是我马上更新啦……
题A A Good Contest
题意:给你人名,让你找rating是红名的,并且在比赛中有涨的~~
题解:这也太水了吧!这一点坑点都没啊,div2也不带这么水的~~
1 /*zhen hao*/
2 #include
3 using namespace std;
4
5 #define lson l, m, rt*2
6 #define rson m + 1, r, rt*2+1
7 #define xx first
8 #define yy second
9
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13
14 int main() {
15 // freopen("case.in", "r", stdin);
16 string id;
17 int before, after, n, ok = 0;
18 cin >> n;
19 for (int i = 0; i < n; i++) {
20 cin >> id >> before >> after;
21 if (before >= 2400 && after - before > 0) ok = 1;
22 }
23 puts(ok ? "YES" : "NO");
24 return 0;
25 }
代码君
题B Economy Game
题意:给你一个数,问你存不存在a、b、c使得a * 1234567 + b * 123456 + c * 1234 = n?
题解:显然枚举a和b得到c。
1 /*zhen hao*/
2 #include
3 using namespace std;
4
5 #define lson l, m, rt*2
6 #define rson m + 1, r, rt*2+1
7 #define xx first
8 #define yy second
9
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13
14 int main() {
15 // freopen("case.in", "r", stdin);
16 ll x = 1234567, y = 123456, z = 1234;
17 ll n;
18 cin >> n;
19 bool ok = false;
20 for (int i = 0; i * x <= n; i++) {
21 for (int j = 0; ; j++) {
22 if (x * i + y * j > n) break;
23 if ((n - x * i - y * j) % z == 0) ok = 1;
24 }
25 }
26 if (ok) puts("YES"); else puts("NO");
27 return 0;
28 }
代码君
题C Heap Operations
题意:给你一些堆操作,但这是不完全的,可能有漏的,你需要补漏,也就是加上最少的操作使得整个操作序列合法。
题解:我们用一个优先队列来维护,
a、insert就直接push进去;
b、getMin的话,分两种情况:1、队列为空,那么插入一个数即可,2、不空即看最开头的元素,如果小于x的话就pop出来(记得加操作),循环知道队列为空或者最开头的元素大于等于x,如果大于或者为空的话就要先insert一个x;
c、removeMin的话,要注意的是队列为空的时候没得remove,这时候就要随便加一个元素进去;
(最后注意一下优先队列的优先级,蒟蒻因为优先队列优先级忘了耽误了下一题的时间)
1 /*zhen hao*/
2 #include
3 using namespace std;
4
5 #define lson l, m, rt*2
6 #define rson m + 1, r, rt*2+1
7 #define xx first
8 #define yy second
9
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13
14 const int maxn = 2e5 + 100, maxm = 2e6 + 100;
15 int e, head[maxn];
16 char s[40];
17
18 struct Edge {
19 int v, op, nx;
20 } edges[maxm];
21
22 void init() {
23 e = 0;
24 memset(head, -1, sizeof head);
25 }
26
27 void add_edge(int u, int v, int op) {
28 edges[e].v = v;
29 edges[e].op = op;
30 edges[e].nx = head[u];
31 head[u] = e++;
32 }
33
34 int get_op() {
35 if (s[0] == 'i') return 0;
36 else if (s[0] == 'g') return 1;
37 else return 2;
38 }
39
40 vector p;
41
42 int main() {
43 // freopen("case.in", "r", stdin);
44 int n, v;
45 cin >> n;
46 init();
47 priority_queue<int, vector<int>, greater<int> > pq;
48 for (int i = 0; i < n; i++) {
49 scanf("%s", s);
50 int op = get_op();
51 if (op == 0 || op == 1) scanf("%d", &v);
52 // cout << op << ' ' << v << endl;
53 if (op == 0) pq.push(v);
54 else if (op == 2) {
55 if (pq.empty()) add_edge(i, 0, 0);
56 else pq.pop();
57 }
58 else {
59 if (pq.empty()) {
60 add_edge(i, v, 0);
61 pq.push(v);
62 } else {
63 while (!pq.empty() && pq.top() < v) {
64 add_edge(i, 0, 2);
65 pq.pop();
66 }
67 if (pq.empty() || pq.top() > v) {
68 add_edge(i, v, 0);
69 pq.push(v);
70 }
71 }
72 }
73 add_edge(i, v, op);
74 }
75 printf("%d\n", e);
76 for (int u = 0; u < n; u++) {
77 p.clear();
78 for (int j = head[u]; ~j; j = edges[j].nx) {
79 p.push_back(make_pair(edges[j].op, edges[j].v));
80 }
81 for (int j = p.size() - 1; j >= 0; j--) {
82 int x = p[j].xx, y = p[j].yy;
83 if (x == 0) printf("%s %d\n", "insert", y);
84 else if (x == 1) printf("%s %d\n", "getMin", y);
85 else printf("%s\n", "removeMin");
86 }
87 }
88 return 0;
89 }
代码君
题D Gifts by the List
题意:有n个人送礼,m对祖先关系,然后a必须送礼物给它的祖先(自己可以是自己的祖先),给出每个人想要送礼的人的编号,然后问你有没有一个安排,使得满足所有人的送礼,每个人会在安排中找第一个祖先来送礼物。
题解:首先要明确的是哪个安排一定是所有列出名单的人的集合,因为如果少一个人就会不满足哪个人的送礼物要求。现在分析一个,假设a想送给b,然后c是在a和b之间的,他想送个d,这个时候d只能是b才能满足,更具体点就是想送给b的人最底下的假设是a,那么a和b之间的所有人都必须送的是b,否则不可以。然后我们就可以得出一个解法:对于dfs序的x如果是想送礼物的名单,那么他的子树的所有没有送礼物的送礼物对象一定是x,所以这就变成了一个模拟题:先得出dfs序,对于一个点x(在送礼物名单中),把所有没有安排的人的并且是x的儿子的要送的人设为x,然后看是否和题目给出的人相吻合即可。
1 /*zhen hao*/
2 #include
3 using namespace std;
4
5 #define lson l, m, rt*2
6 #define rson m + 1, r, rt*2+1
7 #define xx first
8 #define yy second
9
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13
14 const int maxn = 1e5 + 10;
15 vector<int> son[maxn], topo, ans;
16 int a[maxn], b[maxn], is[maxn], vis[maxn];
17
18 void dfs(int u) {
19 vis[u] = 1;
20 for (int i = 0; i < (int)son[u].size(); i++) {
21 int v = son[u][i];
22 if (!vis[v]) dfs(v);
23 }
24 topo.push_back(u);
25 }
26
27 void dfs(int u, int p) {
28 if (b[u]) return;
29 b[u] = p;
30 for (int i = 0; i < (int)son[u].size(); i++) {
31 int v = son[u][i];
32 dfs(v, p);
33 }
34 }
35
36 int main() {
37 // freopen("case.in", "r", stdin);
38 int n, m;
39 cin >> n >> m;
40 for (int i = 0; i < m; i++) {
41 int u, v;
42 scanf("%d%d", &u, &v);
43 son[u].push_back(v);
44 }
45 for (int i = 1; i <= n; i++) {
46 scanf("%d", a + i);
47 is[a[i]] = 1;
48 }
49 memset(vis, 0, sizeof vis);
50 for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);
51 // for (int i = 0; i < (int)topo.size(); i++) cout << topo[i] << endl;
52 for (int i = 0; i < (int)topo.size(); i++) {
53 int u = topo[i];
54 if (is[u]) { dfs(u, u); ans.push_back(u); }
55 }
56 for (int i = 1; i <= n; i++) if (a[i] != b[i]) {
57 puts("-1"); return 0;
58 }
59 cout << ans.size() << endl;
60 for (int i = 0; i < (int)ans.size(); i++)
61 cout << ans[i] << endl;
62 return 0;
63 }
代码君
题E Runaway to a Shadow
题意:给你一个起始点(x0,y0),然后在时间T内以v的速度逃跑,随机往每个角度跑,当跑到给定圆的边界或园内则安全,问你这个逃跑成功的概率。
题解:这道题我觉得比上一题还要水,思路很容易。
1、如果在某个圆内,就输出1
2、对于每个圆求出角度的范围[angL,angR];(要用到余弦定理)
3、然后把每个区间塞到vector里面去,取区间的并集在除以2 * pi则为答案。
怎么取区间的并集?
把每个区间放到vector,并注明左边界是1,右边界是-1,然后排序之后取出来加起来即可!!这道题应该主要是怎么区间取并吧,学到新姿势了orz!
1 /*zhen hao*/ 2 #include代码君3 using namespace std; 4 5 const double eps = 1e-9, PI = acos(-1.0); 6 7 vector ,int> > p; 8 9 double dist(double x1, double y1, double x2, double y2) { 10 return 1.0 * (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); 11 } 12 13 int main() { 14 // freopen("case.in", "r", stdin); 15 int x0, y0, v, t, n; 16 cin >> x0 >> y0 >> v >> t >> n; 17 double r0 = 1.0 * v * t; 18 for (int i = 0; i < n; i++) { 19 int x, y, r; 20 scanf("%d%d%d", &x, &y, &r); 21 22 double d = dist(x, y, x0, y0), sd = sqrt(d); 23 if (d < 1.0 * r * r + eps) { 24 puts("1.000000000"); return 0; 25 } 26 27 if (r + r0 < sd - eps) continue; 28 29 double dr = sqrt(d - 1.0 * r * r); 30 double ang, angL, angR, angM = atan2(y - y0, x - x0); 31 32 if (angM < 0) angM += 2 * PI; 33 34 if (dr < r0 + eps) { 35 ang = asin(r / sd); 36 } 37 else { 38 ang = acos((d + r0 * r0 - 1.0 * r * r) / (2.0 * sd * r0)); 39 } 40 41 angL = angM - ang; 42 angR = angM + ang; 43 44 if (angL < 0) { 45 p.push_back(make_pair(angL + 2 * PI, 1)); 46 p.push_back(make_pair(2 * PI, -1)); 47 p.push_back(make_pair(0.0, 1)); 48 p.push_back(make_pair(angR, -1)); 49 } 50 else if (angR > 2 * PI) { 51 p.push_back(make_pair(angL, 1)); 52 p.push_back(make_pair(2 * PI, -1)); 53 p.push_back(make_pair(0.0, 1)); 54 p.push_back(make_pair(angR - 2 * PI, -1)); 55 } 56 else { 57 p.push_back(make_pair(angL, 1)); 58 p.push_back(make_pair(angR, -1)); 59 } 60 } 61 sort(p.begin(), p.end()); 62 int sum = 0; 63 double pre = 0, ans = 0; 64 for (int i = 0; i < (int)p.size(); i++) { 65 if (sum > 0) ans += p[i].first - pre; 66 sum += p[i].second; 67 pre = p[i].first; 68 } 69 printf("%.10lf\n", ans / (2.0 * PI)); 70 }double