做起来很舒适的一套题。

A – route

假设一个局面：所有可用的点都已经在一侧，那么我们向那一侧走的时候，根据下一次的走向来决定走近似直线还是 Z 字形（也就是取极角序最大或最小）。

// route.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5055;

typedef long long ll;

int n;
char str[MAX_N];

struct point
{
    int x, y;
    point(const int x_ = 0, const int y_ = 0) : x(x_), y(y_) {}
    point operator+(const point &rhs) { return point(x + rhs.x, y + rhs.y); }
    point operator-(const point &rhs) { return point(x - rhs.x, y - rhs.y); }
    ll operator^(const point &rhs) const { return 1LL * x * rhs.y - 1LL * y * rhs.x; }
} pts[MAX_N];

int ans[MAX_N];
bool vis[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].x, &pts[i].y);
    scanf("%s", str + 1);
    point remote = point(1e9, 1e9);
    int remoteId;
    for (int i = 1; i <= n; i++)
        if (pts[i].x < remote.x || (pts[i].x == remote.x && pts[i].y < remote.y))
            remote = pts[i], remoteId = i;
    ans[1] = remoteId, vis[remoteId] = true;
    for (int i = 2; i <= n; i++)
    {
        int pt = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
            {
                if (pt == -1)
                    pt = j;
                else if ((str[i - 1] == 'L' && ((pts[j] - pts[remoteId]) ^ (pts[pt] - pts[remoteId])) > 0) ||
                         (str[i - 1] == 'R' && ((pts[j] - pts[remoteId]) ^ (pts[pt] - pts[remoteId])) < 0))
                    pt = j;
            }
        ans[i] = pt, vis[pt] = true, remoteId = pt;
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}

B – infection

大概思考一下作为初始元素的贡献，发现是一段区间，然后就是区间覆盖问题。用个数据结构之类的维护一下 DP 即可。

// infection.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200, mod = 1e9 + 7;

typedef pair<int, int> pii;

int n, dp[MAX_N], nodes[MAX_N], lower_side, preMax[MAX_N], sufMin[MAX_N];
pii pts[MAX_N], segs[MAX_N];
vector<int> vx, vv;

int lowbit(int x) { return x & (-x); }

void update(int x, int d)
{
    for (; x <= lower_side; x += lowbit(x))
        nodes[x] = (0LL + nodes[x] + mod + d) % mod;
}

int query(int x, int ret = 0)
{
    for (; x; x -= lowbit(x))
        ret = (0LL + ret + nodes[x]) % mod;
    return ret;
}

int ripe(vector<int> &mp, int x) { return lower_bound(mp.begin(), mp.end(), x) - mp.begin() + 1; }

void solve()
{
    for (int i = 1; i <= n; i++)
        vx.push_back(pts[i].first), vv.push_back(pts[i].second);
    sort(vx.begin(), vx.end()), sort(vv.begin(), vv.end());
    for (int i = 1; i <= n; i++)
        pts[i].first = ripe(vx, pts[i].first), pts[i].second = ripe(vv, pts[i].second);
    lower_side = vv.size();
    sort(pts + 1, pts + 1 + n);
    for (int i = 1; i <= n; i++)
        preMax[i] = max(preMax[i - 1], pts[i].second);
    sufMin[n + 1] = 0x3f3f3f3f;
    for (int i = n; i >= 1; i--)
        sufMin[i] = min(sufMin[i + 1], pts[i].second);
    for (int i = 1; i <= n; i++)
    {
        int up = preMax[i], lower = sufMin[i];
        segs[i] = make_pair(lower, up);
    }
    sort(segs + 1, segs + 1 + n, [](const pii &A, const pii &B) { return A.second < B.second || (A.second == B.second && A.first < B.first); });
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int tmp = (0LL + query(segs[i].second) - query(segs[i].first - 1) + mod + dp[segs[i].first - 1]) % mod;
        update(segs[i].second, tmp);
        dp[segs[i].second] = (0LL + dp[segs[i].second] + tmp) % mod;
    }
    printf("%d\n", dp[lower_side]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].first, &pts[i].second);
    solve();
    return 0;
}

C – gcd

打表发现跟 Fibonacci 数列有关。可以用几个基底来算次数之类的。

// gcd.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, mod = 1e9 + 7;

typedef long long ll;
typedef pair<ll, ll> pll;

int n, q;
ll f[MAX_N];
vector<pll> g[MAX_N];

ll calc(pll u, ll x, ll y)
{
    ll ret = 0;
    if (x >= u.second && y >= u.first + u.second)
        ret = (0LL + ret + (y - u.first) / u.second) % mod;
    if (y >= u.second && x >= u.first + u.second)
        ret = (0LL + ret + (x - u.first) / u.second) % mod;
    return ret;
}

int main()
{
    f[0] = f[n = 1] = 1;
    while (f[n] <= 4e18)
        n++, f[n] = f[n - 1] + f[n - 2];
    for (int i = 1; i <= 2; i++)
        g[0].push_back(make_pair(0, i));
    for (int i = 0; i < n - 2; i++)
        for (auto u : g[i])
        {
            ll x = u.first, y = u.second;
            x += y;
            while (x <= f[i + 3] + f[i])
            {
                if (x > y)
                    g[i + 1].push_back(make_pair(y, x));
                x += y;
            }
        }
    scanf("%d", &q);
    while (q--)
    {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        if (x < y)
            swap(x, y);
        ll ans = 1, sum = 0;
        for (; f[ans + 2] <= x && f[ans + 1] <= y; ans++)
            ;
        if (ans == 1)
            sum = 1LL * x * y % mod;
        else
            for (auto &u : g[ans - 1])
                sum = (0LL + sum + calc(u, x, y)) % mod;
        printf("%lld %lld\n", ans, sum);
    }
    return 0;
}