Educational Codeforces Round 2
https://codeforces.com/contest/600
3/6： ABD
A. Extract Numbers
小模拟。把一个字符分成两部分输出，遇到 ';' 或 ',' 视为单词分隔符，非负整数的单词在第一行输出，单词与单词之间要输出一个','。要注意空单词也要输出逗号。
分析：对于判断第一类单词其实也很容易，如果出现了非数字字符，就一定不属于第一类；如果是一个有前导0的数字也不属于第一类。至于空单词的处理：塞一个 $ 符号进去，输出的时候特判就好。
把细节考虑清楚之后就很容易了，一遍过还是很开心的ovo
#include <bits/stdc++.h>
using namespace std;
bool check (string s) {
//出现非数字字符
for (int i = 0; i < s.size (); i++) {
if (!isdigit (s[i])) return false;
}
if (s[0] == '0' && s.size () != 1) return false;
return true;
}
void print (vector <string> v) {
int n = v.size ();
cout << "\"";
if (v[0] != "$") cout << v[0];
for (int i = 1; i < n; i++) {
cout << ",";
if (v[i] != "$") cout << v[i];
}
cout << "\"" << endl;
}
int main () {
string s;
cin >> s;
vector <string> v1, v2;
string t;
s += ';';
for (int i = 0; i < s.size (); i++) {
if (s[i] == ';' || s[i] == ',') {
if (t.empty ()) v2.push_back ("$");
else {
//cout << t << endl;
if (check (t)) v1.push_back (t);
else v2.push_back (t);
t = "";
}
}
else t += s[i];
}
if (v1.empty ()) cout << "-\n";
else print (v1);
if (v2.empty ()) cout << "-\n";
else print (v2);
}
//没有前导0的非负数
B. Queries about less or equal elements
题意：输出a数组中不大于当前输入数字的个数
分析：对a排序后二分即可
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, a[N];
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort (a + 1, a + n + 1);
for (int j = 1; j <= m; j++) {
int x; cin >> x;
int pos = upper_bound (a + 1, a + n + 1, x) - a;
cout << pos - 1 << ' ';
}
//cout << (int)(log (2e5) * (2e5));
}
C. Make Palindrome
目前还不知道为什么WA
#include <bits/stdc++.h>
using namespace std;
int main () {
string s;
cin >> s;
int n = s.size ();
sort (s.begin (), s.end ());
map<char, int> mp;
for (auto i : s) mp[i] ++;
if (n & 1) {
if (n == 1) {
cout << s;
return 0;
}
char find;
for (int i = n - 1; i >= 0; i--) {
if (mp[s[i]] & 1) {
find = s[i];
break;
}
}
for (int i = 0, j = n - 1; i < j; ) { //最大奇可以保留，其余的改
int cnt = mp[s[i]];
if (cnt & 1) {
if (s[i] != find) {
s[j] = s[i];
j --;
}
}
i += cnt;
}
}
else { //偶: 所有次数都要偶
for (int i = 0, j = n - 1; i < j; ) {
int cnt = mp[s[i]];
//cout << cnt << ' ';
if (cnt & 1) {
s[j] = s[i];
j --;
}
i += cnt;
}
}
//cout << endl << s << endl;
sort (s.begin (), s.end ());
string t;
for (int i = 0; i < n - 1; i += 2) cout << s[i], t += s[i];
if (n & 1) cout << s[n-1];
reverse (t.begin (), t.end ());
cout << t;
}
//最小操作做次数下的最小字典序
D. Area of Two Circles' Intersection
简单计算几何。求两个圆的面积并。
分析如图：
相交：
\(S\) = \(S_{扇ACD}-S_{△ACD}+S_{扇BCD}-S_{△BCD}\)
然后通过余弦公式计算两夹角 \(∠CAD,∠CBD\)
利用扇形面积公式和三角形面积公式就可以求得了，这两个公式就不做过多赘述具体可以看代码。
包含：面积并为较小的圆的面积
注意细节：
输入的坐标和半径在参与运算时会爆 \(int\)，所以要开 \(long\,\,double\)
\(double\) 精度不够，要开 \(long \,\,double\)。
#include <bits/stdc++.h>
#define PI acos(-1)
#define double long double
using namespace std;
struct circle {
double x, y, r;
};
double dis(circle a, circle b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main() {
cout << fixed << setprecision (7);
circle a, b;
cin >> a.x >> a.y >> a.r;
cin >> b.x >> b.y >> b.r;
double len = dis(a, b);
if (len + min(a.r, b.r) <= max(a.r, b.r)) {
if (a.r < b.r) cout << PI * a.r * a.r << endl;
else cout << PI * b.r * b.r << endl;
}
else if (len >= a.r + b.r) cout << "0.0000000";
else {
double d1 = 2 * acos((a.r * a.r + len * len - b.r * b.r) / (2 * a.r * len));
double d2 = 2 * acos((b.r * b.r + len * len - a.r * a.r) / (2 * b.r * len));
double area1 = d1 * a.r * a.r / 2 - a.r * a.r * sin(d1) / 2;
double area2 = d2 * b.r * b.r / 2 - b.r * b.r * sin(d2) / 2;
cout << area1 + area2 << endl;
}
}
//扇形面积 α * r * r / 2
//小心爆int
//用long double