A.最短路（计算几何）

题解：

先判断两点的最短路是否会跨过圆的范围，如果没有则直接计算两点距离即可，否则最短路就是两点到圆的切线长度加上两个切点间圆弧的长度

#include <bits/stdc++.h>
using namespace std;
double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
    double x1, y1, x2, y2, x3, y3, r, ans = 0;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r;
    double d1 = dis(x1, y1, x2, y2), d2 = dis(x1, y1, x3, y3), d3 = dis(x2, y2, x3, y3);
    double e1 = acos(r / d2), e2 = acos(r / d3);
    double e3 = acos((d2 * d2 + d3 * d3 - d1 * d1) / (2 * d2 * d3));
    if (e1 + e2 > e3)
    {
        printf("%.6f\n", d1);
        return 0;
    }
    ans = sqrt(d2 * d2 - r * r) + sqrt(d3 * d3 - r * r) + (e3 - e1 - e2) * r;
    printf("%.6f\n", ans);
    return 0;
}

B.组队（滑动窗口）

题解：

首先将所有人按照能力值排序，然后维护一个最大能力值与最小能力值的差值小于等于 $k$ 的滑动窗口即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[maxn];
void solve()
{
    ll n, k;
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n);
    int l = 0, ans = 1;
    for (int r = 1; r < n; r++)
    {
        while (a[r] - a[l] > k)
            l++;
        ans = max(ans, r - l + 1);
    }
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.十面埋伏（bfs）

题解：

只需要对士兵外围 bfs 一下，然后对所有 bfs 到的节点，判断他周围四个方向是否有士兵，若有士兵，则说明这个点需要放置陷阱

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char s[1005][1005];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
bool vis[1005][1005];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    queue<pii> q;
    q.push({1, 1});
    while (!q.empty())
    {
        pii t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = t.first + dir[i][0];
            int ty = t.second + dir[i][1];
            if (tx < 1 || tx > n || ty < 1 || ty > m)
                continue;
            if (s[tx][ty] == '#' || vis[tx][ty])
                continue;
            vis[tx][ty] = true;
            q.push({tx, ty});
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i - 1][j] == '#' || s[i + 1][j] == '#' || s[i][j - 1] == '#' || s[i][j + 1] == '#')
            {
                if (s[i][j] != '#' && vis[i][j] == true)
                    s[i][j] = '*';
            }
            putchar(s[i][j]);
        }
        puts("");
    }
    return 0;
}

D.牛妹吃豆子（二位前缀和）

题解：

首先用二维差分算出每个点的豆子数，再用二位前缀和求出每个询问的结果

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[2005][2005];
int main()
{
    int n, m, k, q;
    scanf("%d%d%d%d", &n, &m, &k, &q);
    while (k--)
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        a[x1][y1]++;
        a[x1][y2 + 1]--;
        a[x2 + 1][y1]--;
        a[x2 + 1][y2 + 1]++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
    while (q--)
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%lld\n", a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1]);
    }
    return 0;
}

E.旅旅旅游（最短路）

题解：

先求出以 $1$ 为起点单源最短路和以 $n$ 为起点的单源最短路,然后判断每一条边是否在最短路上，如果不在就用并查集来维护，若所有点都在一个集合内，则可以将所有城市走一遍

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int maxn = 1e5 + 5;
const int MAXN = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<pii> G[maxn];
ll d1[maxn], d2[maxn];
int n, m, u[MAXN], v[MAXN], c[MAXN];
bool vis[maxn];
int fa[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void dij(int s, ll d[], vector<pii> G[])
{
    for (int i = 1; i <= n; i++)
        d[i] = 1e18, vis[i] = 0;
    priority_queue<pli> q;
    q.push({0, s});
    d[s] = 0;
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto it : G[u])
        {
            int v = it.first, w = it.second;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({-d[v], v});
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u[i], &v[i], &c[i]);
        G[u[i]].push_back({v[i], c[i]});
        G[v[i]].push_back({u[i], c[i]});
    }
    dij(1, d1, G), dij(n, d2, G);
    for (int i = 1; i <= m; i++)
    {
        if (d1[u[i]] + d2[v[i]] + c[i] == d1[n] || d1[v[i]] + d2[u[i]] + c[i] == d1[n])
            continue;
        int x = find(u[i]), y = find(v[i]);
        fa[x] = y;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (i == find(i))
            cnt++;
    puts((cnt == 1) ? "YES" : "NO");
    return 0;
}

F.斗兽棋（签到）

题解：

模拟即可

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s, d;
    cin >> d >> s;
    if (s == "elephant" && d == "tiger" || s == "tiger" && d == "cat" || s == "cat" && d == "mouse" || s == "mouse" && d == "elephant")
        puts("tiangou txdy");
    else
        puts("tiangou yiwusuoyou");
    return 0;
}

G.做题（签到）

题解：

贪心，将花费时间排序，每次拿时间最少的即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn];
int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n);
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] > m)
            break;
        m -= a[i];
        ans++;
    }
    printf("%lld\n", ans);
    return 0;
}

H.人人都是好朋友（并查集）

题解：

考虑先将所有的朋友关系利用并查集放在同一个集合中，再判断具有敌人关系的两个人是否在同一个朋友集合中即可。由于数据范围过大，要对数据离散化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int fa[maxn];
int a[maxn], b[maxn], c[maxn], d[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void solve()
{
    int n, cnt = 0;
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", &a[i], &b[i], &c[i]);
        d[++cnt] = a[i];
        d[++cnt] = b[i];
    }
    sort(d + 1, d + cnt + 1);
    int m = unique(d + 1, d + cnt + 1) - (d + 1);
    int flag = 1;
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(d + 1, d + m + 1, a[i]) - d;
        int y = lower_bound(d + 1, d + m + 1, b[i]) - d;
        int u = find(x);
        int v = find(y);
        if (u != v && c[i] == 1)
            fa[u] = v;
        else if (u == v && c[i] == 0)
            flag = 0;
    }
    puts(flag ? "YES" : "NO");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

I.求和（dfs序）

题解：

dfs序裸题，先求出dfs序，用线段树单点修改和区间查询即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll val[maxn], tree[maxn << 2];
int head[maxn], nxt[maxn << 1], to[maxn << 1], cnt;
int tot, in[maxn], out[maxn], id[maxn];
void init()
{
    memset(head, -1, sizeof(head));
    cnt = tot = 0;
}
void addedge(int u, int v)
{
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt++;
}
void dfs(int u, int fa)
{
    in[u] = ++tot;
    id[tot] = u;
    for (int i = head[u]; ~i; i = nxt[i])
    {
        int v = to[i];
        if (v == fa)
            continue;
        dfs(v, u);
    }
    out[u] = tot;
}
void pushup(int rt)
{
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        tree[rt] = val[id[l]];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int rt, int l, int r, int pos, ll v)
{
    if (l == r)
    {
        tree[rt] += v;
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
        update(rt << 1, l, mid, pos, v);
    else
        update(rt << 1 | 1, mid + 1, r, pos, v);
    pushup(rt);
}
ll query(int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return tree[rt];
    int mid = l + r >> 1;
    if (R <= mid)
        return query(rt << 1, l, mid, L, R);
    else if (L > mid)
        return query(rt << 1 | 1, mid + 1, r, L, R);
    else
        return query(rt << 1, l, mid, L, mid) + query(rt << 1 | 1, mid + 1, r, mid + 1, R);
}
int main()
{
    init();
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &val[i]);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(k, 0);
    build(1, n, 1);
    while (m--)
    {
        int op, u;
        ll v;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%lld", &u, &v);
            update(1, 1, n, in[u], v);
        }
        else
        {
            scanf("%d", &u);
            printf("%lld\n", query(1, 1, n, in[u], out[u]));
        }
    }
    return 0;
}

J.建设道路（前缀和）

题解：

$\sum_{i=1}^{n}{\sum_{j=1}^{i-1}{(a_i-a_j)^2}}=\sum_{i=1}^n\sum_{j=1}^{i-1}(a_i^2-2*a_i*a_j+a_j^2)=(n-1)*\sum_{i=1}^{n}{a_i^2}-\sum_{i=1}^{n}{\sum_{j=1}^{i-1}{(2*a_i*a_j)}}=(n-1)*\sum_{i=1}^{n}{a_i^2}-2*\sum_{i=1}^{n}{a_i\sum_{j=1}^{i-1}{a_j}}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[maxn];
int main()
{
    ll n, sum = 0, sum1 = 0, sum2 = 0;
    scanf("%lld", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        sum1 = (sum1 + a[i] * a[i]) % mod;
        sum2 = (sum2 + sum * a[i]) % mod;
        sum = (sum + a[i]) % mod;
    }
    sum1 = (n - 1ll) * sum1 % mod;
    sum2 = 2ll * sum2 % mod;
    printf("%lld\n", (sum1 - sum2 + mod) % mod);
    return 0;
}

牛客小白月赛24