又是典型的前四题一下就过，第五题卡死到最后都没有做出来。

赛后看了题解过了第五题，居然是 DP, 赛时一直想着贪心...... 主要是一个性质没有利用好。

A

大水题，一分钟暴切。

B

大水题

C

乍一看好难，一看数据范围，直接搜索。

D

用旋转的公式，先将旋转中心平移到原点，然后旋转完再平移回去。

记住 math 库中的三角函数是弧度制的。

E

一看以为是贪心，按照某种神奇的方式排个序就好了。

想到过 DP，但一看 $10^5$ 的数据范围，觉得 1D / 0D 不太现实，就继续回去贪心。

看了题解，发现确实不是 1D/0D，但确实是 DP。

有一个性质决定了它可以 DP， 这个性质其实挺贪心的，每一种 ID 一定是停在最左或最右， 我想贪心的时候，确实也想到了类似的结论，但却从没有想过要用它来 DP。

既然有了这个结论，那么只停在 左边/右边 这个状态就方便记录了，而且显然有最优子结构性质，也没有后效性，容易转移。

代码

#include <algorithm>
#include <cstdio>
#define int long long
const int N = 200005, INF = 0x3f3f3f3f3f3f3f3fll;
int n, l[N], r[N], cnt, pre, f[N][2];
struct twt {
    int x, c;
} a[N];
signed main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i].x, &a[i].c);
        l[i] = INF, r[i] = -INF;
    }
    for(int i = 1; i <= n; i++) {
        l[a[i].c] = std::min(l[a[i].c], a[i].x);
        r[a[i].c] = std::max(r[a[i].c], a[i].x);
    }
    for(int i = 1; i <= n; i++) {
        if(l[i] == INF) continue;
        cnt++;
        f[cnt][0] = std::min(f[cnt-1][0] + abs(l[pre] - r[i]), f[cnt-1][1] + abs(r[pre]-r[i])) + abs(r[i] - l[i]);
        f[cnt][1] = std::min(f[cnt-1][0] + abs(l[pre] - l[i]), f[cnt-1][1] + abs(r[pre]-l[i])) + abs(r[i] - l[i]);
        pre = i;
    }
	printf("%lld", std::min(f[cnt][0] + abs(l[pre]), f[cnt][1]+abs(r[pre])));
	return 0;
}