题目链接：https://codeforces.com/contest/600
一个很无聊的模拟，难度居然是1600，看来当时的竞赛和现在完全不一样。
排个序二分一下，很无聊的一个题。注意应该使用upper_bound。
一开始以为是随便贪心一下的无聊题，结果WA15了。
题意：给一个串s，可以对它进行重排，然后修改其中的一些字母。修改最少的次数使得他变成回文串，假如修改次数最少的有多种方案，求结果字典序最小的一种。
题解：假如串是奇数长度，那么可以容纳一个奇数字母，当然选择剩下的容纳最小的字母。然后想怎么构造两边，假如最小的字母还有剩，那么肯定放一个在左边，然后假如还有剩，再放一个在右边，continue。否则一定要进行一次修改，为了使得字典序最小，就应该找出现次数是奇数的最大的字母，把他变成最小的字母，然后放进去，continue。
当然写的时候就不需要这么蠢了。用cnt的方法写，注意要跳过奇数次的字母。
char s[200005];
int cnt[128];
void test_case() {
scanf("%s", s + 1);
int n = strlen(s + 1);
for(int i = 1; i <= n; ++i)
++cnt[s[i]];
int l = 'a', r = 'z';
while(l < r) {
if(cnt[l] % 2 == 0) {
++l;
continue;
}
if(cnt[r] % 2 == 0) {
--r;
continue;
}
++cnt[l];
--cnt[r];
++l;
--r;
}
int c = 'a';
for(int i = 1; i <= n / 2; ++i) {
while(cnt[c] < 2)
++c;
s[i] = c;
s[n - i + 1] = c;
cnt[c] -= 2;
}
c = 'a';
if(n % 2 == 1) {
while(cnt[c] == 0)
++c;
s[(n + 1) / 2] = c;
}
puts(s + 1);
}题意：给两个圆，求面积交。
从现在这个年代看好像这种题很模板，可能当时的人水平和现在不一样吧。不过自己从来没有认真推过这个结论，不妨现在看一看。
题解：特判掉两圆内含、两圆外离（含相切）的情况，剩下的就是相交，相交部分为两个不见得一定是一样的弓形，要计算这个弓形的面积，应该是使用扇形的面积减去三角形的面积，换言之只需要知道交点和圆心连线的圆心角的大小。画了一下发现原来这种圆心角也有可能是优角，这是之前没有观察到的。
怎么找交点的坐标呢？仔细想想甚至还真不需要！好像之前在学校的题目里面做过，这里已经知道了两圆的半径，也很容易根据圆心算出圆心距，那么两个圆心和交点形成的三角形就是唯一的（SSS全等），可以用余弦定理解出圆心角的一半的cos值，然后计算反cos得到圆心角的一半。注意到这种算法并不关心圆心角是否是优角，甚至这个算法包含了外离和内含的情况（不能构成三角形）。这种算法的误差来源：计算cos值时不可避免求了模的根号，使用内置函数求反cos值，以及后面的一系列浮点运算产生的近似，关键是没有二分求解交点这样的误差非常大的环节。也省去了对于不同情况下找交点的讨论。
注：三角形的面积，这里没有点的坐标，用正弦定理的推论算出来。
void test_case() {
ll x1, y1, r1;
ll x2, y2, r2;
scanf("%lld%lld%lld", &x1, &y1, &r1);
scanf("%lld%lld%lld", &x2, &y2, &r2);
long double dis = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
if(r1 + r2 <= dis) {
printf("%.12f\n", (double)(0.0));
return;
}
if(r1 + dis <= r2) {
printf("%.12f\n", (double)(PI * r1 * r1));
return;
}
if(r2 + dis <= r1) {
printf("%.12f\n", (double)(PI * r2 * r2));
return;
}
long double cosa1 = (dis * dis + r1 * r1 - r2 * r2) / (2.0 * r1 * dis);
long double a1 = acos(cosa1);
long double A1 = 2.0 * a1;
long double S1 = 0.5 * r1 * r1 * A1 - 0.5 * sin(A1) * r1 * r1;
long double cosa2 = (dis * dis + r2 * r2 - r1 * r1) / (2.0 * r2 * dis);
long double a2 = acos(cosa2);
long double A2 = 2.0 * a2;
long double S2 = 0.5 * r2 * r2 * A2 - 0.5 * sin(A2) * r2 * r2;
long double S = S1 + S2;
printf("%.12f\n", (double)(S));
}收获：才发现公式全忘了，余弦定理是 \(a^2=b^2+c^2-2bc \cos A\) ，正弦定理的推论是 \(S=\frac{1}{2}ab \sin C\) ，圆心角所对的弧长是 \(l=\alpha r\) ，圆心角所对的扇形的面积是 \(S=\frac{1}{2}\alpha r^2\)
思考：那么既然能够算出圆心角的大小，就可以通过构造一个圆心连线的向量，然后顺时针或者逆时针Rotate过去，再加上圆心的坐标，就可以得到交点的坐标。
Educational Codeforces Round 2
原文：https://www.cnblogs.com/KisekiPurin2019/p/12460135.html