5/5
果然上一篇博文是个flag啊！我果然拖更了！昨天的CF完了还没有更新上一次的CF题解，所以昨天差点GG（不过第三题这个分数也离GG不远了，好在rating没掉(/▽╲)）。为了攒回人品，于是我马上更新啦……
题A A Good Contest
题意：给你人名，让你找rating是红名的，并且在比赛中有涨的~~
题解：这也太水了吧！这一点坑点都没啊，div2也不带这么水的~~
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 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 <bits/stdc++.h> 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 <bits/stdc++.h> 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<pii> 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 <bits/stdc++.h> 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 <bits/stdc++.h> 3 using namespace std; 4 5 const double eps = 1e-9, PI = acos(-1.0); 6 7 vector<pair<double,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 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5596088.html
