A – The Tower is Going Home

发现只有从最左侧出发的横线才可以造成贡献。计算答案的时候，考虑枚举越过的竖线，然后更新答案。

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

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, ai[MAX_N], bi[MAX_N], cnt, ans;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    sort(ai + 1, ai + 1 + n), ai[n + 1] = ans = 1e9;
    for (int i = 1, xl, xr, y; i <= m; i++)
    {
        scanf("%d%d%d", &xl, &xr, &y);
        if (xl == 1)
            bi[++cnt] = xr;
    }
    sort(bi + 1, bi + 1 + cnt);
    for (int i = 1; i <= n + 1; i++)
        ans = min(ans, int(i + cnt - (lower_bound(bi + 1, bi + 1 + cnt, ai[i]) - bi)));
    printf("%d\n", ans);
    return 0;
}

B – Intersecting Subtrees

智商雪崩，唉。

其实随便找一个 Y 点，然后找最近的 X 点即可。

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

using namespace std;

const int MAX_N = 1010;

int T, n, head[MAX_N], current, k1, k2, p1[MAX_N], p2[MAX_N], dist[MAX_N];
bool tag1[MAX_N], tag2[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

int query(bool typ, int x)
{
    printf("%c %d\n", typ ? 'B' : 'A', x), fflush(stdout);
    scanf("%d", &x);
    return x;
}

int dfs(int u, int fa)
{
    if (tag1[u])
        return u;
    int ret = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dist[edges[i].to] = dist[u] + 1;
            int tmp = dfs(edges[i].to, u);
            if (dist[tmp] < dist[ret])
                ret = tmp;
        }
    return ret;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(head, -1, sizeof(head)), current = 0, memset(dist, 0, sizeof(dist));
        memset(tag1, false, sizeof(tag1)), memset(tag2, false, sizeof(tag2)), dist[0] = 0x3f3f3f3f;
        scanf("%d", &n);
        for (int i = 1, u, v; i < n; i++)
            scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
        scanf("%d", &k1);
        for (int i = 1; i <= k1; i++)
            scanf("%d", &p1[i]), tag1[p1[i]] = true;
        scanf("%d", &k2);
        for (int i = 1; i <= k2; i++)
            scanf("%d", &p2[i]), tag2[p2[i]] = true;
        int center = query(true, p2[1]), pt = dfs(center, 0);
        if (tag2[query(false, pt)])
            printf("C %d\n", pt), fflush(stdout);
        else
            puts("C -1"), fflush(stdout);
    }
    return 0;
}

C – Optimal Polygon Perimeter

妈的这场怎么全是这种题？

发现 \(k \geq 4\) 时，Manhattan 周长其实就是外接矩形的周长。只需要计算三角形和四边形的最大答案即可。

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

using namespace std;

const int MAX_N = 3e5 + 200;

typedef long long ll;

int n;
ll xi[MAX_N], yi[MAX_N], rect[4][2];

ll dist(int x, int y) { return abs(rect[x][0] - rect[y][0]) + abs(rect[x][1] - rect[y][1]); }

ll distRPT(int x, int y) { return abs(rect[x][0] - xi[y]) + abs(rect[x][1] - yi[y]); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &xi[i], &yi[i]);
        if (i == 1)
            for (int j = 0; j < 4; j++)
                rect[j][0] = xi[i], rect[j][1] = yi[i];
        else
        {
            if (xi[i] > rect[0][0])
                rect[0][0] = xi[i], rect[0][1] = yi[i];
            if (yi[i] < rect[1][1])
                rect[1][0] = xi[i], rect[1][1] = yi[i];
            if (xi[i] < rect[2][0])
                rect[2][0] = xi[i], rect[2][1] = yi[i];
            if (yi[i] > rect[3][1])
                rect[3][0] = xi[i], rect[3][1] = yi[i];
        }
    }
    ll ans = 0;
    for (int i = 0; i <= 3; i++)
        for (int j = 0; j <= 3; j++)
            if (i != j)
                for (int k = 1; k <= n; k++)
                    ans = max(ans, dist(i, j) + distRPT(i, k) + distRPT(j, k));
    printf("%lld ", ans), ans = 0;
    for (int i = 0; i <= 3; i++)
        ans += dist(i, (i + 1) % 4);
    for (int i = 4; i <= n; i++)
        printf("%lld ", ans);
    puts("");
    return 0;
}

D – Deduction Queries

带权并查集（之前都不太会）的题。

我们考虑用前缀和的关系来描述这道题。对于更新区间的操作，我们可以把 \(r\) 并在 \(l – 1\) 上，并且赋权。对于回答操作，如果在一个连通块中，那么路径上的 \(\text{xor}\) 和即为答案，否则就无法描述。

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

using namespace std;

const int MAX_N = 2e5 + 200;

int q, lastans;
map<int, int> fa, weight;

int find(int x)
{
    if (fa.count(x) == 0)
        return x;
    int up = find(fa[x]);
    weight[x] ^= weight[fa[x]];
    fa[x] = up;
    return up;
}

int main()
{
    scanf("%d", &q);
    while (q--)
    {
        int opt, l, r, x;
        scanf("%d", &opt);
        if (opt == 1)
        {
            scanf("%d%d%d", &l, &r, &x), l ^= lastans, r ^= lastans, x ^= lastans;
            if (l > r)
                swap(l, r);
            l--;
            int lf = find(l), rf = find(r);
            if (lf != rf)
                fa[rf] = lf, weight[rf] = x ^ weight[l] ^ weight[r];
        }
        else
        {
            scanf("%d%d", &l, &r), l ^= lastans, r ^= lastans;
            if (l > r)
                swap(l, r);
            l--;
            int lf = find(l), rf = find(r);
            if (lf != rf)
                puts("-1"), lastans = 1;
            else
                printf("%d\n", lastans = weight[l] ^ weight[r]);
        }
    }
    return 0;
}