在纪中，不铺好蚊帐就等着第二天比赛 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;
}