专栏文章

题解：CF985G Team Players

OOIer_ACMer
CF985G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minap1c6
此快照首次捕获于
2025/12/01 23:19
3 个月前
此快照最后确认于
2025/12/01 23:19
3 个月前
查看原文

恐怖容斥一命速通：CF985G

关键点：

我们发现反向建边太麻烦就可以考虑和它思想差不多（去除不合格的留下合格的）但更难却更高效的方法——容斥。

思考步骤：

  1. 首先，我们既然要做容斥，就要知道容斥的公式：总体方案数-最多可能重复的种类数加上次多可能重复的种类数……；
  2. 尽管公式不会证，但我们首先来考虑我们这几种分别是什么，怎么算；
  3. 首先，最多可能的，也就是总体方案，肯定是任选三个点组成的三元组的答案，由于我们很容易发现 (1,2,3)(1,2,3) 和 (2,3,1)(2,3,1) 都会在枚举过程中出现，但它们属于一种，所以我们默认 a<b<c a<b<c，下面也是一样，防止重复，这样我们很快就能知道 aa，bb，cc 在各自的位子上的贡献是多少；
  4. 当我们考虑要求一条边的情况时，也会有重复，我们就钦定 u<vu<v，那么剩下的就是再在这个分类讨论里分析下一个点 ww 的大小，因为 ww 的大小的确无法判定；
  5. 接下来是两条边，因为我们只能确定一个点，所以剩下两个点 vv 和 ww 又会有重复情况，所以钦定 v<wv<w，之后就是判断 u<v<wu<v<w，u>w>vu>w>v，v<u<wv<u<w，这几种的答案怎么算；
  6. 最后一种就是三条边都选，就是三元组问题，和上一道差不多；
  7. 最后公式就是总方案数减去至少有一条边加上至少至少两条边减去至少三条边就是答案。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
int sum[2000009];
vector<int> g[2000009];
vector<int> e[2000009];
pair<int, int> E[2000009];
int du[2000009];
bool vis[2000009];
signed main()
{
    n = read();
    m = read();
    int A = read();
    int B = read();
    int C = read();
    int ans = 0, ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
    for (int i = 1; i <= n; i++) // Section I
    {
        g[i].push_back(0);
        ans1 += A * ((unsigned long long)(n - i - 1) * (n - i) / 2) * (i - 1) + B * (i - 1) * (n - i) * (i - 1) + C * (i - 1) * ((unsigned long long)(i - 1) * (i - 2) / 2);
    }
    // cout << "ans1=" << ans1 << endl;
    for (int i = 1; i <= m; i++) // Section II
    {
        int x = read(), y = read();x++;
        y++;
        g[x].push_back(y);
        g[y].push_back(x);
        E[i] = {x, y};
        
        du[x]++;
        du[y]++;
        if (x > y)
        {
            swap(x, y);
        }
        ans2 += (x - 1) * ((x - 1) * B + (y - 1) * C) + ((unsigned long long)(x - 1) * (x - 2) / 2) * A + (y - x - 1) * ((x - 1) * A + (y - 1) * C) + ((unsigned long long)(y + x - 2) * (y - x - 1) / 2) * B + (n - y) * ((x - 1) * A + (y - 1) * B) + ((unsigned long long)(y + n - 1) * (n - y) / 2) * C;
    }
    // cout << "ans2=" << ans2 << endl;
    for (int i = 1; i <= n; i++)
    {
        sort(g[i].begin(), g[i].end());
    }
    for (int u = 1; u <= n; u++) // Section III
    {
        int rk = 0, cntr = 0, cnt = 0;
        for (int i = 1; i <= du[u]; i++)
        {
            if (g[u][i] < u)
            {
                rk = i, cntr += g[u][i] - 1;
            }
            else
            {
                break;
            }
        }
        for (int i = 1; i <= du[u]; i++)
        {
            int v = g[u][i];
            if (v < u)
            {
                ans3 += (i - 1) * ((u - 1) * C + (v - 1) * B) + cnt * A;
            }
            else
            {
                ans3 += (i - rk - 1) * ((u - 1) * A + (v - 1) * C) + (cnt - cntr) * B;
                ans3 += rk * ((u - 1) * B + (v - 1) * C) + cntr * A;
            }
            cnt += v - 1;
        }
    }
    // cout << "ans3=" << ans3 << endl;
    for (int i = 1; i <= m; i++) 
    {
        if (du[E[i].first] > du[E[i].second])
        {
            e[E[i].second].push_back({E[i].first});
        }
        else if (du[E[i].second] > du[E[i].first])
        {
            e[E[i].first].push_back({E[i].second});
        }
        else
        {
            if (E[i].first < E[i].second)
            {
                e[E[i].first].push_back({E[i].second});
            }
            else
            {
                e[E[i].second].push_back({E[i].first});
            }
        }
    }
    for (int u = 1; u <= n; u++)
    {
        // for (int i = 0; i < e[u].size(); i++)
        // {

        // }
        for (int i = 0; i < e[u].size(); i++)
        {
            vis[e[u][i]] = 1;
        }
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            for (int j = 0; j < e[v].size(); j++)
            {
                int w = e[v][j];
                if (vis[w])
                {
                    // cout << "u=" << u << " v=" << v << " w=" << w << endl;
                    ans4 += (min({u, v, w}) - 1) * A + (u + v + w - min({u, v, w}) - max({u, v, w}) - 1) * B + (max({u, v, w}) - 1) * C;
                }
            }
        }
        for (int i = 0; i < e[u].size(); i++)
        {
            vis[e[u][i]] = 0;
        }
    }
    // cout << "ans4=" << ans4 << endl;
    ans = ans1 - ans2 + ans3 - ans4;
    cout << ans << endl;
    return 0;
}

Trick：

容斥原理实在是太困难了，为防止以后回顾这些题傻了，就放个通俗易懂的方法增援未来： 7xiHTL.png

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...