在纪中，不铺好蚊帐就等着第二天比赛 GG。

kal0rona

A – 鸡腿の梦境

计算几何套路题，所以不会。

其实考试的时候看得出来是判断点是否在多边形内，但是真的不会写然后就爆零了。主要原理在于跨立试验和判奇权环。

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

using namespace std;

const int MAX_N = 330;

int n, head[MAX_N], current;
double ri[MAX_N];
bool vis[MAX_N][2];

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

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

struct point
{
    double x, y;
} pts[MAX_N];

double pow2(double x) { return x * x; }

double getDist(point &a, point &b) { return sqrt(pow2(a.x - b.x) + pow2(a.y - b.y)); }

bool judge(point &a, point &b, point &c, point &d)
{
    double u, v, w, z;
    u = (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
    v = (d.x - a.x) * (b.y - a.y) - (b.x - a.x) * (d.y - a.y);
    w = (a.x - c.x) * (d.y - c.y) - (d.x - c.x) * (a.y - c.y);
    z = (b.x - c.x) * (d.y - c.y) - (d.x - c.x) * (b.y - c.y);
    return (u * v <= 0.00001 && w * z <= 0.00001);
}

void dfs(int u, int fa, int opt)
{
    if (vis[u][opt])
        return;
    vis[u][opt] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u, opt ^ edges[i].weight);
}

int main()
{
    point remote_point = {9024.0, 6002.0};
    while (scanf("%d", &n) != EOF)
    {
        memset(head, -1, sizeof(head)), current = 0;
        for (int i = 1; i <= n + 1; i++)
            scanf("%lf%lf%lf", &pts[i].x, &pts[i].y, &ri[i]);
        for (int i = 1; i <= n; i++)
            ri[i] += ri[n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (getDist(pts[i], pts[j]) < ri[i] + ri[j])
                    if (judge(pts[i], pts[j], pts[n + 1], remote_point))
                        addpath(i, j, 1), addpath(j, i, 1);
                    else
                        addpath(i, j, 0), addpath(j, i, 0);
        bool flag = true;
        for (int i = 1; i <= n; i++)
        {
            memset(vis, false, sizeof(vis));
            dfs(i, 0, 0);
            for (int j = 1; j <= n; j++)
                if (vis[j][0] && vis[j][1])
                {
                    flag = false;
                    break;
                }
            if (flag == false)
                break;
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

B – 鸡腿の花园

我恨卡哈希。把哈希函数设置的奇怪一点就特么过了，害。

// B.cpp
#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int MAX_N = 2e5 + 200, bitnum = 133, mod1 = 1e9 + 7, mod2 = 1e9 + 9, bitlft = 23333, bitrig = 998443;

struct hash_val
{
    int val1, val2;

    hash_val operator+(const int &ch)
    {
        hash_val ret = *this;
        ret.val1 = (1LL * ret.val1 + mod1 + ch) % mod1;
        ret.val2 = (1LL * ret.val2 + mod2 + ch) % mod2;
        return ret;
    }

    hash_val operator+(const hash_val &ch)
    {
        hash_val ret = *this;
        ret.val1 = (1LL * ret.val1 + mod1 + ch.val1) % mod1;
        ret.val2 = (1LL * ret.val2 + mod2 + ch.val2) % mod2;
        return ret;
    }

    hash_val operator-(const hash_val &rhs)
    {
        hash_val ret = *this;
        ret.val1 = (0LL + ret.val1 + mod1 - rhs.val1) % mod1;
        ret.val2 = (0LL + ret.val2 + mod2 - rhs.val2) % mod2;
        return ret;
    }

    hash_val operator*(const int &rhs)
    {
        hash_val ret = *this;
        ret.val1 = 1LL * ret.val1 * rhs % mod1;
        ret.val2 = 1LL * ret.val2 * rhs % mod2;
        return ret;
    }

    hash_val operator*(const hash_val &rhs)
    {
        hash_val ret = *this;
        ret.val1 = 1LL * ret.val1 * rhs.val1 % mod1;
        ret.val2 = 1LL * ret.val2 * rhs.val2 % mod2;
        return ret;
    }

    bool operator==(const hash_val &target) const { return val1 == target.val1 && val2 == target.val2; }

    bool operator<(const hash_val &target) const { return val1 < target.val1 || (val1 == target.val1 && val2 < target.val2); }
};

int n, m, ch[MAX_N][2], siz[MAX_N], fa[MAX_N];
hash_val nodes[MAX_N], bpow[MAX_N];
map<hash_val, int> mp;
long long ans = 0;

void dfs(int u, int opt)
{
    siz[u] = 1;
    if (ch[u][0] != -1)
        dfs(ch[u][0], opt), siz[u] += siz[ch[u][0]];
    else
        ch[u][0] = 0;
    if (ch[u][1] != -1)
        dfs(ch[u][1], opt), siz[u] += siz[ch[u][1]];
    else
        ch[u][1] = 0;

    hash_val curt = hash_val{0, 0};
    curt = nodes[ch[u][0]] * nodes[ch[u][0]] * bitlft + nodes[ch[u][1]] * bitrig + (siz[u] ^ siz[ch[u][1]]);
    nodes[u] = curt;
    if (opt == 0)
        mp[nodes[u]]++;
    else
        ans += mp[nodes[u]];
}

void setFather(int x, int fat) { x > 0 ? fa[x] = fat : 0; }

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &ch[i][0], &ch[i][1]), setFather(ch[i][0], i), setFather(ch[i][1], i);
    bpow[0] = hash_val{1, 1};
    for (int i = 1; i <= max(n, m); i++)
        bpow[i] = bpow[i - 1] * bitnum;
    for (int i = n + 1; i <= n + m; i++)
    {
        scanf("%d%d", &ch[i][0], &ch[i][1]);
        if (ch[i][0] != -1)
            ch[i][0] += n;
        if (ch[i][1] != -1)
            ch[i][1] += n;
        setFather(ch[i][0], i), setFather(ch[i][1], i);
    }
    int root1, root2;
    for (int i = 1; i <= n; i++)
        if (fa[i] == 0)
            root1 = i;
    for (int i = n + 1; i <= n + m; i++)
        if (fa[i] == 0)
            root2 = i;
    dfs(root1, 0), dfs(root2, 1), printf("%lld\n", ans);
    return 0;
}

C – 鸡腿の游戏

我特么是中了邪，一直写缩点，最后发现跟 BLO 很像。

首先，按照割点的套路去写个 Tarjan。当该点为割点时，我们就需要计算其在搜索树上的 LCA 为 \(u\) 的点对方案。跟 BLO 几乎一样吧（存疑），然后就解决了（我真是个sb）。

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

using namespace std;

const int MAX_N = 5e4 + 200, MAX_E = 1e5 + 200;
typedef long long ll;

int head[MAX_N], current, n, m, dfn[MAX_N], low[MAX_N], ptot, tot[MAX_N];
ll ans[MAX_N];

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

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

void tarjan(int u, int fa)
{
    ll cnt = 0;
    dfn[u] = low[u] = ++ptot;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            if (dfn[edges[i].to] == 0)
            {
                tarjan(edges[i].to, u), low[u] = min(low[u], low[edges[i].to]);
                tot[u] += tot[edges[i].to];
                if (low[edges[i].to] >= dfn[u])
                {
                    ans[u] -= cnt * tot[edges[i].to], ans[u] += 1LL * (n - tot[edges[i].to] - 1) * tot[edges[i].to];
                    cnt += tot[edges[i].to];
                }
            }
            else
                low[u] = min(low[u], dfn[edges[i].to]);
    ans[u] += n - 1, tot[u]++;
}

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);
        if (u != v)
            addpath(u, v), addpath(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0)
            tarjan(i, 0);
    for (int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}