题目链接：https://codeforces.com/contest/598
A - Tricky Sum
挺有意思的一条送分题。
B - Queries on a String
题意：给一个长<=10000的字符串，然后<=300次询问，每次询问要求把[l,r]子串循环右移k<=1000000次。求最终的结果。
题解：感觉这题有个FHQTreap的解法。不过仔细想想看长度这么短，询问也这么少，直接把k模子串长度然后暴力就可以了。
char s[10005];
char tmp1[10005];
char tmp2[10005];
void test_case() {
scanf("%s", s + 1);
int n = strlen(s + 1), m;
scanf("%d", &m);
while(m--) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
k %= (r - l + 1);
int t1top = 0, t2top = 0;
for(int i = l; i <= r - k; ++i)
tmp1[++t1top] = s[i];
for(int i = r - k + 1; i <= r; ++i)
tmp2[++t2top] = s[i];
tmp1[t1top + 1] = ' ';
tmp2[t2top + 1] = ' ';
for(int i = l, k = 1; k <= t2top; ++i, ++k)
s[i] = tmp2[k];
for(int i = l + t2top, k = 1; k <= t1top; ++i, ++k)
s[i] = tmp1[k];
}
puts(s + 1);
}
C - Nearest vectors
题意：给一堆起点为0的向量，求哪两个向量的夹角最小。注意此题精度超高。
题解：计算出atan2(y,x)的值，也就是极角值，然后极角排序。注意夹角为极角差和极角差的补角中的最小值。
const long double PI = acos(-1.0);
struct Point {
long double k;
int x, y;
int id;
Point() {}
Point(long double k, int x, int y, int id):
k(k), x(x), y(y), id(id) {}
bool operator<(const Point &p) {
return k < p.k;
}
} p[100005];
long double angle(long double k1, long double k2) {
long double tk = k2 - k1;
tk = min(tk, 2.0 * PI - tk);
return tk;
}
void test_case() {
int n;
scanf("%d", &n);
int top1 = 0, top2 = 0;
int up = 0, down = 0;
for(int i = 1; i <= n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
p[i] = Point(atan2(y, x), x, y, i);
}
sort(p + 1, p + 1 + n);
long double mindis = angle(p[1].k, p[n].k);
int ans1 = p[1].id, ans2 = p[n].id;
for(int i = 1; i < n; ++i) {
if(angle(p[i].k, p[i + 1].k) < mindis) {
mindis = angle(p[i].k, p[i + 1].k);
ans1 = p[i].id;
ans2 = p[i + 1].id;
}
printf("%.20f
", (double)angle(p[i].k, p[i + 1].k));
}
printf("%d %d
", ans1, ans2);
}
收获：
1、atan2(y,x)可以正确处理各种y和x为0的情况，算出一个[-PI,PI]的极角。
2、夹角为极角的差的绝对值，和极角的差的绝对值的补角之间的最小值。而不是要加减某些周角。是补角，不是加减周角。
3、精度题可以用long double试试，double的有效数字在这一题中大概只有7位十进制。
4、可以用余弦定理算出cos值，易知cos值的平方为有理数，可惜在交叉相乘的时候却会溢出64位整数。是否应该封装一个128位整数类，他没有大数这么麻烦，却是实在的128位整数。
D - Igor In the Museum
一个挺明显的挖油井问题，要数某个白格连通块中与白格接壤的黑格的不同面的数量。假如去掉同一个黑格的不同面，只需要在cntwall前判断一下有没有被当前白色连通块vis过，然后涂上这个连通块特有的颜色。
int di[4] = {0, 0, -1, 1};
int dj[4] = {-1, 1, 0, 0};
char g[1005][1005];
int vis[1005][1005];
int cnt[1005][1005];
queue<pii> Q1, Q2;
void bfs(int si, int sj, int color) {
vis[si][sj] = color;
Q1.push({si, sj});
Q2.push({si, sj});
int cntwall = 0;
while(!Q1.empty()) {
int ui = Q1.front().first, uj = Q1.front().second;
Q1.pop();
for(int k = 0; k < 4; ++k) {
int vi = ui + di[k];
int vj = uj + dj[k];
if(g[vi][vj] == '*')
++cntwall;
if(g[vi][vj] == '.' && vis[vi][vj] == 0) {
vis[vi][vj] = color;
Q1.push({vi, vj});
Q2.push({vi, vj});
}
}
}
while(!Q2.empty()) {
int ui = Q2.front().first, uj = Q2.front().second;
Q2.pop();
cnt[ui][uj] = cntwall;
}
}
void test_case() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; ++i)
scanf("%s", g[i] + 1);
int cntcolor = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(g[i][j] == '.' && vis[i][j] == 0)
bfs(i, j, ++cntcolor);
}
}
while(q--) {
int qi, qj;
scanf("%d%d", &qi, &qj);
printf("%d
", cnt[qi][qj]);
}
}
*E - Chocolate Bar
题意：一块n*m的格子巧克力（其中n<=30且m<=30），要恰好吃k(<=min(n*m,50))块巧克力，已知每次可以沿一条直的格子边界掰断巧克力，代价是长度的平方。求最小代价。
题解：一开始以为是枚举k的因数，发现过不了第3个样例，然后猜测要多一些零头，注意这些零头未必只有1格宽。观察到掰断之后的小巧克力的代价，与掰断前的巧克力无关，是个相似结构的子问题，设计一个dp算法，然后卡一堆常数解决。
ll dp[31][31][51];
void test_case() {
memset(dp, LINF, sizeof(dp));
for(int a = 0; a <= 30; ++a) {
for(int b = 0; b <= 30; ++b) {
dp[a][b][0] = 0;
if(a * b <= 50)
dp[a][b][a * b] = 0;
}
}
for(int a = 1; a <= 30; ++a) {
for(int b = 1; b <= a; ++b) {
int ck = min(a * b - 1, 50);
for(int k = 0; k <= ck; ++k) {
ll tmp = dp[a][b][k];
for(int a1 = 1; a1 < a; ++a1) {
int cs = min(k, a1 * b);
for(int s = 0, t = b * b; s <= cs && tmp > t; ++s) {
tmp = min(tmp, dp[a1][b][s] + dp[a - a1][b][k - s] + t);
tmp = min(tmp, dp[a1][b][k - s] + dp[a - a1][b][s] + t);
}
}
for(int b1 = 1; b1 < b; ++b1) {
int cs = min(k, b1 * a);
for(int s = 0, t = a * a; s <= cs && tmp > t; ++s) {
tmp = min(tmp, dp[a][b1][s] + dp[a][b - b1][k - s] + t);
tmp = min(tmp, dp[a][b1][k - s] + dp[a][b - b1][s] + t);
}
}
dp[a][b][k] = min(dp[a][b][k], tmp);
dp[b][a][k] = min(dp[b][a][k], tmp);
//printf("dp[%d][%d][%d]=%lld
", a, b, k, dp[a][b][k]);
}
}
}
int t;
scanf("%d", &t);
while(t--) {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
printf("%lld
", dp[n][m][k]);
}
}
*F - Cut Length
题意：给一个n<=1000个点的不自交的多边形（不一定是凸包），按顺时针或者逆时针方向给出。再询问一些直线，问这条直线与多边形重叠部分的长度，在边界上也算重叠，精度要求（相对C题来说）不高。
题解：感觉很好想的，先把整个多边形按点存下来，然后对于每一条直线，求出其与x轴的交点，然后让直线和多边形一起绕交点旋转，直到直线与x轴重合。假如直线斜率为0，则直接平移直线与多边形直到直线与x轴重合。再遍历多边形的所有边，求出其与x轴的交点。排序之后分奇偶性统计就好了。问题的恶心的地方在于多边形中与x轴重合的边。仔细想想这种情况（上一条边和下一条边）无论是从内部、从外部、还是从边界本身出发、结束，都是直接把边的两端也加进来即可。剩下的，计算几何只能相信你的eps了。
需要用到的函数：求直线的旋转角，继续用atan2即可，求直线交点，解一个简单的一次方程，然后用Point类中的Rotate函数旋转多边形，在旋转的时候因为函数默认是绕原点旋转。所以要进行一些加加减减。求线段与x轴的交点，先特判两端是否在x轴上或者一端在x轴上，都不是则询问两端点是否异侧，然后解一个一次方程。或者直接调用计算几何的函数。