Codeforces Round 886 (Div. 4)

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;
}