F. We Were Both Children
题解：约数
- 我们先利用\(map\)记录\(a_i\)的出现次数
- 然后对\(map\)中的每一个元素的在其所有不超过\(n\)的倍数的位置上都加上对应的贡献
- 时间复杂度：调和级数\(O(nlogn)\)
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
int a[N];
map<int, int> mp;
void solve()
{
cin >> n;
mp.clear();
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
mp[a[i]]++;
}
vector<int> ans(n + 10);
for (auto [x, y] : mp)
for (int j = x; j <= n; j += x)
ans[j] += y;
int res = 0;
for (int i = 1; i <= n; ++i)
res = max(res, ans[i]);
cout << res << endl;
}
G. The Morning Star
题解：\(map\) + 组合计数
- 我们开\(4\)个\(map\)记录四个方向上点的数量
- 假设每一个方向上的点数为\(x\)，显然每一个方向上的方案数为\(x \times (x - 1)\)
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
map<int, int> mp[4];
void solve()
{
cin >> n;
mp[0].clear();
mp[1].clear();
mp[2].clear();
mp[3].clear();
for (int i = 1; i <= n; ++i)
{
int x, y;
cin >> x >> y;
mp[0][x]++;
mp[1][y]++;
mp[2][y - x + n]++;
mp[3][y + x]++;
}
int ans = 0;
for (auto [x, y] : mp[0])
if (y)
ans += y * (y - 1);
for (auto [x, y] : mp[1])
if (y)
ans += y * (y - 1);
for (auto [x, y] : mp[2])
if (y)
ans += y * (y - 1);
for (auto [x, y] : mp[3])
if (y)
ans += y * (y - 1);
cout << ans << endl;
}
H. The Third Letter
题解：带权并查集
我们考虑带权并查集做法
并查集中维护每个点到根节点的距离为\(dis_u\)
显然如果两个士兵\(u,v\)有关系的话，那么根据简单容斥得到，两者之间的距离为\(dis_u - dis_v\)
对于两个士兵\(u,v\)来说，如果当前没有关系，那么合并两个点，即将\(u\)的根节点\(fu\)合并到\(v\)的根节点\(fv\)上去，我们考虑如何构造\(dis_{fu}\)
\[dis_u + dis_{fu} - dis_v = w\\ dis_{fu} = dis_v - dis_u + w \]
- 那么如果两个士兵有关系的话，判断两者之间的距离是否合法即可
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m;
// 带权并查集
struct DSU
{
int fa[N], dis[N];
void init()
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
dis[i] = 0;
}
}
int find(int x)
{
if (x == fa[x])
return x;
int rt = find(fa[x]);
dis[x] += dis[fa[x]];
fa[x] = rt;
return fa[x];
}
void merge(int u, int v, int w)
{
int fu = find(u);
int fv = find(v);
if (fu != fv)
{
fa[fu] = fv;
// dis[u] + dis[fu] - dis[v] = w;
dis[fu] = dis[v] - dis[u] + w;
}
}
} dsu;
void solve()
{
cin >> n >> m;
dsu.init();
bool flag = true;
for (int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
if (dsu.find(u) != dsu.find(v))
dsu.merge(v, u, w);
else
{
if (dsu.dis[v] - dsu.dis[u] != w)
flag = false;
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}