题解 | #刷题统计#

题目链接

刷题统计

题目描述

牛客推出了三个题单：新手入门、算法入门、算法进阶。给定以下五个整数：

$N$ : 至少刷过任意一个题单的总人数
$N_A$ : 刷过「新手入门」的人数
$N_B$ : 刷过「算法入门」的人数
$N_C$ : 刷过「算法进阶」的人数
$N_2$ : 恰好刷过其中任意两个题单的总人数

数据保证存在唯一非负整数解。请计算同时刷过全部三部曲的人数。

输入:

第一行一个整数 $T$ ，表示测试用例数量。
接下来 $T$ 行，每行五个整数 $N, N_A, N_B, N_C, N_2$ 。

输出:

对每个测试用例，输出一行，表示同时刷过全部三个题单的人数。

解题思路

这是一个典型的集合问题，可以使用容斥原理（Principle of Inclusion-Exclusion）来解决。

我们设三个集合 $A, B, C$ 分别代表刷过「新手入门」、「算法入门」、「算法进阶」的人群。根据容斥原理，三个集合的并集大小为： $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$

我们将题目中给出的变量代入这个公式：

$N = |A \cup B \cup C|$
$N_A = |A|$
$N_B = |B|$
$N_C = |C|$

我们要求的是同时刷过三个题单的人数，即 $|A \cap B \cap C|$ 。我们将其设为 $N_{ABC}$ 。公式变为： $N = N_A + N_B + N_C - (|A \cap B| + |A \cap C| + |B \cap C|) + N_{ABC}$

接下来处理 $N_2$ ，即恰好刷过两个题单的人数。这个值等于“刷过A和B但没刷过C的人”+“刷过A和C但没刷过B的人”+“刷过B和C但没刷过A的人”。用集合运算表示： $N_2 = (|A \cap B| - |A \cap B \cap C|) + (|A \cap C| - |A \cap B \cap C|) + (|B \cap C| - |A \cap B \cap C|)$

整理后得到： $N_2 = (|A \cap B| + |A \cap C| + |B \cap C|) - 3 \cdot |A \cap B \cap C|$ $N_2 = (|A \cap B| + |A \cap C| + |B \cap C|) - 3 \cdot N_{ABC}$

这样我们就可以用 $N_2$ 和 $N_{ABC}$ 表示两两相交的集合之和： $(|A \cap B| + |A \cap C| + |B \cap C|) = N_2 + 3 \cdot N_{ABC}$

现在，将这个结果代入最初的容斥原理公式中： $N = N_A + N_B + N_C - (N_2 + 3 \cdot N_{ABC}) + N_{ABC}$ $N = N_A + N_B + N_C - N_2 - 2 \cdot N_{ABC}$

最后，我们整理这个方程，解出我们想要的 $N_{ABC}$ ： $2 \cdot N_{ABC} = N_A + N_B + N_C - N_2 - N$ $N_{ABC} = \frac{N_A + N_B + N_C - N_2 - N}{2}$

由于题目保证存在唯一非负整数解，因此我们直接使用这个公式计算即可。使用 long long 或 long 可以避免中间和过大导致溢出。

代码

cpp
java
python

#include <iostream>

using namespace std;

void solve() {
    long long n, na, nb, nc, n2;
    cin >> n >> na >> nb >> nc >> n2;
    long long ans = (na + nb + nc - n2 - n) / 2;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();
            long na = sc.nextLong();
            long nb = sc.nextLong();
            long nc = sc.nextLong();
            long n2 = sc.nextLong();
            long ans = (na + nb + nc - n2 - n) / 2;
            System.out.println(ans);
        }
    }
}

t = int(input())
for _ in range(t):
    n, na, nb, nc, n2 = map(int, input().split())
    ans = (na + nb + nc - n2 - n) // 2
    print(ans)

算法及复杂度

算法：数学、容斥原理
时间复杂度： $\mathcal{O}(T)$ ，每个测试用例是 $\mathcal{O}(1)$ 的计算。
空间复杂度： $\mathcal{O}(1)$ 。