本文主要是介绍【解题报告】Codeforces Round #357 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
A. A Good Contest（Codeforces 681A）
思路
遍历输入数据，检查是否存在符合条件的人即可。
代码
#include <bits/stdc++.h>
using namespace std;bool ok = false;
int n, b, a;
string s;int main() {cin >> n;while(n--) {cin >> s >> b >> a;if(b >= 2400 && b < a) {ok = true;}}puts(ok ? "YES" : "NO");return 0;
}B. Economy Game（Codeforces 681B）
思路
最朴素的想法是用三重循环枚举 a,b,c ，但是其实用两重循环枚举 a,b ，再检查是否存在满足条件的c即可。
代码
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll a[] = {1234567, 123456, 1234};
bool ok = false;
ll n, tmp, rem;int main() {cin >> n;for(ll i = 0; ; i++) {tmp = i * a[0];if(tmp > n) {break;}for(ll j = 0; tmp + j * a[1] <= n; j++) {rem = n - tmp - j * a[1];if(rem % a[2] == 0) {ok = true;i = 1000;break;}}}puts(ok ? "YES" : "NO");return 0;
}C. Heap Operations（Codeforces 681C）
思路
因为本题的操作是一系列关于堆的操作，而且数据规模也合适，所以我们可以直接用一个堆来模拟这些操作（可用 STL 的 priority _ queue 或 multiset ），然后动态判断当前操作是否合法。当前操作合法时只需要维护堆，且将当前操作加入题目要求我们求的答案序列中即可(可以用数组或 vector 保存)。当前操作不合法时有以下两种情况：
- 当进行删除最小值操作时操作不合法：说明此时队列为空，需要往答案序列中加入插入任意数的操作。
- 当进行查询最小值操作时操作不合法：说明要么队列为空，要么最小值与我们维护的堆得最小值不同。前者比较好处理，后者若堆的最小值比查询的值大的话就往队里插入任意数，否则删除最小值直到堆的最小值比查询的值大或变成空堆。
代码
#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 10;
int n, a[maxn];
string input[maxn];
vector <int> b;
vector <string> output;
priority_queue < int, vector<int>, greater<int> > pq;int main() {ios::sync_with_stdio(false);cin >> n;for(int i = 1; i <= n; i++) {cin >> input[i];if(input[i][0] != 'r') {cin >> a[i];}}for(int i = 1; i <= n; i++) {// 若当前操作是插入操作if(input[i][0] == 'i') {output.push_back(input[i]);b.push_back(a[i]);pq.push(a[i]);}// 若当前操作是删除操作else if(input[i][0] == 'r') {// 若堆空则需先让将插入操作加入到答案中if(pq.empty()) {output.push_back("insert");b.push_back(0);}// 否则对堆执行删除操作else {pq.pop();}// 将删除操作加入到答案中output.push_back(input[i]);b.push_back(0);}// 若当前操作是查询操作else {// 若堆空则先维护答案和堆if(pq.empty()) {output.push_back("insert");b.push_back(a[i]);pq.push(a[i]);}// 否则若堆顶元素与查询元素不相等else if(pq.top() != a[i]) {// 若堆非空且堆顶元素太小则删除堆顶while(!pq.empty() && pq.top() < a[i]) {output.push_back("removeMin");b.push_back(0);pq.pop();}// 若上一个循环让堆变空if(pq.empty()) {output.push_back("insert");b.push_back(a[i]);pq.push(a[i]);}// 若堆顶元素太大则直接插入待查询元素else if(pq.top() > a[i]) {output.push_back("insert");b.push_back(a[i]);pq.push(a[i]);}}// 将查询操作加入答案中output.push_back(input[i]);b.push_back(a[i]);}}cout << output.size() << endl;for(int i = 0; i < output.size(); i++) {cout << output[i];if(output[i][0] == 'r') {cout << endl;}else {cout << ' ' << b[i] << endl;}}return 0;
}D. Gifts by the List（Codeforces 681D）
思路
首先可以确定的是，最终的名单上的人的名字，就是 a 数组中出现的名字
代码
#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 5;
bool notRoot[maxn];
int n, m, u, v, a[maxn];
vector <int> ans, G[maxn];bool dfs(int u, int p) {for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];if(v == p) {continue;}// 动态检查答案序列是否合法if(a[v] != v && a[v] != a[u]) {return false;}if(dfs(v, u) == false) {return false;}}// 输出完所有的儿子再输出自己if(a[u] == u) {ans.push_back(u);}return true;
}int main() {scanf("%d%d", &n, &m);while(m--) {scanf("%d%d", &u, &v);G[u].push_back(v);notRoot[v] = true;}for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);}for(int i = 1; i <= n; i++) {if(notRoot[i] == true) {continue;}// 以每个树根为起点进行拓扑排序if(dfs(i, -1) == false) {puts("-1");return 0;}}printf("%d\n", ans.size());for(int i = 0; i < ans.size(); i++) {printf("%d\n", ans[i]);}return 0;
}E. Runaway to a Shadow（Codeforces 681E）
思路
螳螂可以在规定时间内进入圆C的充分条件是螳螂以螳螂起点O为圆心，螳螂在规定时间T内能够发生的位移R = v * t为半径的圆O与圆C有大于或等于(题目中的Reach暗示了可以等于)零的公共面积。如果有公共面积的话，求出“能让螳螂达到圆C”的角度（某个方向与x轴正方向的夹角）区间，不妨称之为“安全区间”。对所有的圆C都这样做，最后求这些区间的并ans，而ans / (2 * pi)就是题目所求概率。现在的问题是怎么求出角度区间呢？我们先用勾股定理求出点O到圆C的切线长度tn，然后比较tn和R的大小，若tn比较小的话说明螳螂能够到达，所以两条切线分别于x轴求夹角的结果[al, ar]就是安全区间。若R比tn大的话，说明螳螂在规定时间内无法到达切点，但是螳螂最远能够到达圆上的点是l和r，那么就用余弦定理直接求出直线OC与Ol的夹角（OC与Or的夹角与其相等），就能够通过求OC与x周的夹角求出安全区间了。值得注意的是，连续区间的区间合并与离散区间的区间合并在实现上有些不同。另外，这里还有一些跟精度有关的细节。比如用atan2函数求向量与x轴的夹角的精度比atan高。还有当将两个距离比较大小的时候，用平方距离比较大小会比较好，因为少了两次开方运算，也就少了两次精度损失。
代码
#include <bits/stdc++.h>
using namespace std;const double eps = 1e-8;
const double pi = acos(-1.0);inline int cmp(double x) {return x < -eps ? -1 : (x > eps);
}inline double sqr(double x) {return x * x;
}inline double mySqrt(double n) {return sqrt(max(0.0, n));
}// 二维点类
struct Point {double x, y;Point() {}Point(double x, double y): x(x), y(y) {}void input() {scanf("%lf%lf", &x, &y);}friend Point operator - (const Point& a, const Point& b) {return Point(a.x - b.x, a.y - b.y);}double norm() {return sqrt(sqr(x) + sqr(y));}double angle() {return atan2(y, x);}
};// 点对类型
typedef pair <Point, Point> pp;// 求平方距离
double sqrDist(const Point& a, const Point& b) {Point c = a - b;return sqr(c.x) + sqr(c.y);
}// 用余弦定理求余弦
double Cos(double a, double b, double c) {return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);
}// 判断点与圆的位置关系
int isPointInCircle(Point p, Point c, double r) {double d = sqrDist(p, c);return cmp(sqr(r) - d);
}// 求点到圆的切线的长度
double tangentLength(Point p, Point c, double r) {double d = (p - c).norm();return mySqrt(sqr(d) - sqr(r));
}typedef pair <double, int> p;
int v, t, n, cnt;
double R, r, d, tn, a, am, al, ar, last, ans;
vector <p> vec;
Point O, C, D;// 将区间插入区间集合中
void insert(double l, double r) {vec.push_back(p(l, 1));vec.push_back(p(r, -1));
}int main() {O.input();scanf("%d%d%d", &v, &t, &n);R = 1.0 * v * t;while(n--) {C.input();scanf("%lf", &r);if(isPointInCircle(O, C, r) >= 0) {printf("%.5f\n", 1.0);return 0;}D = C - O;d = D.norm();// 若两圆不相交跳过if(cmp(d - R - r) > 0) {continue;}tn = tangentLength(O, C, r);// 判断螳螂是否能到达切点if(cmp(tn - R) <= 0) {a = asin(r / d);}else {a = acos(Cos(R, d, r));}am = D.angle();al = fmod(am - a + 2 * pi, 2 * pi);ar = fmod(am + a + 2 * pi, 2 * pi);if(cmp(al - ar) > 0) {insert(al, 2 * pi);insert(0, ar);}else {insert(al, ar); }}// 合并区间sort(vec.begin(), vec.end());for(int i = 0; i < vec.size(); i++) {if (cnt > 0) {ans += vec[i].first - last;}cnt += vec[i].second;last = vec[i].first;}printf("%.5f\n", ans / pi / 2);return 0;
}这篇关于【解题报告】Codeforces Round #357 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
