GermanCPC 2018

题目链接戳这里

B. Battle Royale

多次尝试就会发现，外面的那个区域是无用的，只需考虑红圈的影响。形象的解释是想象有个橡皮筋，连接起始点后的路径就是最短距离。如图，就是画了双杠的三条边了。两条切线段+一段弧。知三点坐标对应计算即可。

#include <bits/stdc++.h>
using namespace std;

double xc, yc, xd, yd;
double xb, yb, rb;
double xr, yr, rr;

double dis(double ax, double ay, double bx, double by) {
    double dx = ax - bx,dy = ay - by;
    return sqrt(dx * dx + dy * dy);
}

void solve() {
    double C = dis(xc, yc, xd, yd);
    double A = dis(xc, yc, xr, yr);
    double B = dis(xd, yd, xr, yr);
    double ans = 0.0;
    double A2 = A * A, B2 = B * B;
    double C2 = C * C, r2 = rr * rr;
    ans += sqrt(A2 - r2);
    ans += sqrt(B2 - r2);
    double cosC = (A2 + B2 - C2)/(2 * A * B);
    double xita = acos(cosC);
    double xita1 = acos(rr / A);
    double xita2 = acos(rr / B);
    xita -= (xita1 + xita2);

    ans += rr * xita;
    printf("%.10lf\n", ans);
}


int main() {
    cin >> xc >> yc >> xd >> yd;
    cin >> xb >> yb >> rb;
    cin >> xr >> yr >> rr;
    solve();
}

C. Coolest Ski Route

求最长路，注意两点：1，用bfs比dfs快，不用每个路径都深搜到底，这样没有必要。2.有重边，取最大值。

#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
const int maxN = 1e3 + 5;
int N, M, K, T;

int G[maxN][maxN];
vector<int> E[maxN];
int d[maxN], top[maxN];

void bfs(int s) {
    d[s] = 0;
    queue<int> Q;
    Q.push(s);

    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        for (int i = 0; i < E[cur].size(); ++i) {
            int x = E[cur][i];
            if (d[x] < d[cur] + G[cur][x]) {
                d[x] = d[cur] + G[cur][x];
                Q.push(x);
            }
        }
    }
}

int main() {
    scanf("%d%d", &N, &M);
    int u, v, w;
    mst(top, 1);
    for (int i = 0; i < M; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        G[u][v] = max(G[u][v], w);
        E[u].pb(v);
        top[v] = 0;
    }
    for (int i = 1; i <= N; ++i)
        if (top[i])
            bfs(i);

    int ans = 0;
    for (int i = 1; i <= N; ++i)
        ans = max(ans, d[i]);
    printf("%d\n", ans);
    return 0;
}

E. Expired License

给你一个浮点数x和y，问有无形成x/y比例的两个素数。这题关键是精度问题！给出的比例因为小数最多5位，所以转成整数，化简，如果这两个数都是素数即有解。double强转int是一个“截断”的过程，用round()来四舍五入才对，小坑也重要..

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int N, M, K, T;

bool isPrime(ll u) {
    for (int i = 2; i * i <= u; ++i)
        if (u % i == 0)
            return 0;
    return u != 1;
}

int main() {
    scanf("%d", &T);
    double a, b;
    while (T--) {
        scanf("%lf%lf", &a, &b);
        int x = round(a * 1e5), y = round(b * 1e5);
        int G = __gcd(x, y);
        x /= G;
        y /= G;
        if (x == y)
            x = y = 2;
        if (isPrime(x) && isPrime(y))
            printf("%d %d\n", x, y);
        else
            puts("impossible");
    }
    return 0;
}

I. It's Time for a Montage

这是巨长巨绕阅读理解题..可以自行去感受一下，无力吐槽

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e3 + 5;
int N, M, K, T;

int A[maxN], B[maxN];

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
    for (int i = 0; i < N; ++i) scanf("%d", &B[i]);

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (A[i] > B[i]) {
            break;
        } else if (A[i] < B[i]) {
            ++ans;
            for (int j = 0; j < N; ++j)
                ++A[j];
            i = -1;
        }
    }
    printf("%d\n", ans);
    return 0;
}