A – Elections

直接做不太好做，很懵逼。可以考虑枚举 CCP 得到的票数，然后再从各大党派中各抢一张票。如果不够抢就直接抢最小的票。这样取 min 即可。

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

using namespace std;

const int MAX_N = 3030;

typedef long long ll;
typedef pair<int, int> pii;

int n, m, pi[MAX_N], ci[MAX_N], cnt[MAX_N], pcnt;
ll gans = 1e18;
pii people[MAX_N];
bool tag[MAX_N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &pi[i], &ci[i]);
        if (pi[i] != 1)
            people[++pcnt] = make_pair(ci[i], pi[i]);
        else
            cnt[1]++;
    }
    sort(people + 1, people + 1 + pcnt);
    for (int stock = 1; stock <= n; stock++)
    {
        int rem = cnt[1];
        ll pans = 0;
        memset(tag, false, sizeof(tag));
        for (int i = 2; i <= m; i++)
            cnt[i] = 0;
        for (int i = 1; i <= pcnt; i++)
            cnt[people[i].second]++;
        for (int i = 1; i <= pcnt; i++)
            if (cnt[people[i].second] >= stock)
                cnt[people[i].second]--, pans += people[i].first, tag[i] = true, rem++;
        if (rem >= stock)
            gans = min(gans, pans);
        else
        {
            for (int i = 1; i <= pcnt && rem < stock; i++)
                if (!tag[i])
                    cnt[people[i].second]--, pans += people[i].first, tag[i] = true, rem++;
            gans = min(gans, pans);
        }
    }
    printf("%lld\n", gans);
    return 0;
}

B – The hat

比较有意思的题目。

首先，有解的一个条件就是 \(n \bmod 4 \equiv 0\)，因为考虑每一个 \(+1, -1\) 的过程是相互抵消的，所以 \(\frac{n}{2} \bmod 2 \equiv 0\)。假设我们现在有 \(a_1, a’_1\)（\(a’_i\)表示 \(i\) 的对面的权值），那么进行一次旋转之后，发现 \(a_1 – a’_1 – (a_2 – a’_2) = 2, -2, 0\)，那么我们可以用这个性质进行倍增或者是二分，来找出平衡的那个位置。

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

using namespace std;

const int MAX_N = 1e5 + 200, INF = 0x3f3f3f3f;

int n, ai[MAX_N];

int query(int x)
{
    if (ai[x] != INF)
        return ai[x];
    printf("? %d\n", x), fflush(stdout), scanf("%d", &ai[x]);
    return ai[x];
}

int opposite(int x) { return (x + (n >> 1) - 1) % n + 1; }

int validiate(int c)
{
    int x = query(c), y = query(opposite(c));
    if (x == y)
        printf("! %d\n", c), fflush(stdout), exit(0);
    return x > y ? 1 : -1;
}

int main()
{
    memset(ai, 0x3f, sizeof(ai));
    scanf("%d", &n);
    if (n % 4 != 0)
        puts("! -1"), fflush(stdout), exit(0);
    int l = 1, r = (n >> 1) + 1, curt = validiate(1), curt_op = -curt;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        int verdict = validiate(mid);
        if (curt * verdict < 0)
            r = mid - 1, curt_op = verdict;
        else if (curt_op * verdict < 0)
            l = mid + 1, curt = verdict;
    }
    printf("! -1\n"), fflush(stdout);
    return 0;
}

C – Sergey’s problem

图论构造题，找出一个独立集使得任意补集点到某个独立集点的最短距离小于等于 2。我们可以直接暴力染色，考虑把 \(1 \to n\) 的点进行暴力染色，然后反过来消色即可。

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

using namespace std;

const int MAX_N = 1e6 + 200;

int n, m, head[MAX_N], current;
vector<int> vec;
bool vis[MAX_N], aff[MAX_N];

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

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

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v);
    for (int u = 1; u <= n; u++)
        if (!vis[u])
        {
            vis[u] = aff[u] = true;
            for (int i = head[u]; i != -1; i = edges[i].nxt)
                vis[edges[i].to] = true;
        }
    for (int u = n; u >= 1; u--)
        if (aff[u])
            for (int i = head[u]; i != -1; i = edges[i].nxt)
                aff[edges[i].to] = false;
    for (int i = 1; i <= n; i++)
        if (aff[i])
            vec.push_back(i);
    printf("%lld\n", 1LL * vec.size());
    for (auto x : vec)
        printf("%d ", x);
    puts("");
    return 0;
}

D – Large Triangle

啊之前没搞懂这个操作，今天彻底搞懂了。

首先向量要按照极角序排序，然后枚举基线段。随着基线段的增加，我们可以维护一个 \(rk[], pos[]\) 来获得与线段距离远近的信息。随着基线段斜率增加，发现只有基线段两端点的远近信息会被修改，直接 \(swap\) 即可。

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

using namespace std;

const int MAX_N = 2020;
const double eps = 1e-10;

typedef long long ll;

int n, m, rk[MAX_N], pos[MAX_N];
ll S;

struct node
{
    ll x, y;
    node(ll x_ = 0, ll y_ = 0) : x(x_), y(y_) {}
    bool operator<(const node &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
    node operator-(const node &rhs) const { return node(x - rhs.x, y - rhs.y); }
    ll operator^(const node &rhs) const { return 1LL * x * rhs.y - y * rhs.x; }
} nodes[MAX_N];

struct segment
{
    int uid, vid;
    node vec;
    bool operator<(const segment &rhs) const { return (vec ^ rhs.vec) > 0; }
} segs[MAX_N * MAX_N];

int main()
{
    scanf("%d%lld", &n, &S), S <<= 1;
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &nodes[i].x, &nodes[i].y);
    sort(nodes + 1, nodes + 1 + n);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            segs[++m] = segment{i, j, nodes[j] - nodes[i]};
    sort(segs + 1, segs + 1 + m);
    for (int i = 1; i <= n; i++)
        rk[i] = pos[i] = i;
    for (int i = 1; i <= m; i++)
    {
        node nd = segs[i].vec;
        int uid = segs[i].uid, vid = segs[i].vid;
        if (rk[uid] > rk[vid])
            swap(uid, vid);
        int l = 1, r = rk[uid] - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            ll curt_S = abs(nd ^ (nodes[pos[mid]] - nodes[pos[rk[uid]]]));
            if (curt_S == S)
            {
                printf("Yes\n%lld %lld\n%lld %lld\n%lld %lld\n", nodes[uid].x, nodes[uid].y, nodes[vid].x, nodes[vid].y, nodes[pos[mid]].x, nodes[pos[mid]].y);
                return 0;
            }
            else if (curt_S > S)
                l = mid + 1;
            else
                r = mid - 1;
        }
        swap(rk[uid], rk[vid]);
        swap(pos[rk[uid]], pos[rk[vid]]);
    }
    puts("No");
    return 0;
}