题目链接

刷题统计

题目描述

牛客推出了新手入门、算法入门、算法进阶三部曲题单。

设：

  • — 至少刷过任意一个题单的人数
  • — 刷过新手入门的人数
  • — 刷过算法入门的人数
  • — 刷过算法进阶的人数
  • — 恰好刷过其中任意两个题单的总人数

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

解题思路

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

我们设三个集合：

  • : 刷过新手入门题单的人的集合，则 。
  • : 刷过算法入门题单的人的集合，则 。
  • : 刷过算法进阶题单的人的集合，则 。

根据题意，“至少刷过任意一个题单的人数”为 ，即 。

我们想要求的是“同时刷过全部三部曲的人数”，即 。

三集合的容斥原理公式为：

将题目中的变量代入，得到：

接下来，我们处理变量 。“恰好刷过其中任意两个题单的总人数”可以表示为：

  • 恰好刷过 和 （但没刷 ）的人数：
  • 恰好刷过 和 （但没刷 ）的人数：
  • 恰好刷过 和 （但没刷 ）的人数：

因此， 是这三者之和：

我们设要求的答案 。那么上式可以写成：

移项可得：

现在，我们将这个结果代入最初的容斥原理公式中：

最后，我们解这个关于 的方程：

这就是计算同时刷过全部三部曲人数的最终公式。

代码

#include <iostream>

using namespace std;

int main() {
    int T;
    // 读取测试用例数量
    cin >> T;
    while (T--) {
        long long n, n1, n2, n3, k;
        // 读取输入数据
        cin >> n >> n1 >> n2 >> n3 >> k;
        // 根据推导出的公式计算并输出结果
        long long ans = (n1 + n2 + n3 - k - n) / 2;
        cout << ans << endl;
    }
    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 n1 = sc.nextLong();
            long n2 = sc.nextLong();
            long n3 = sc.nextLong();
            long k = sc.nextLong();
            // 根据推导出的公式计算并输出结果
            long ans = (n1 + n2 + n3 - k - n) / 2;
            System.out.println(ans);
        }
    }
}

# 读取测试用例数量
T = int(input())
for _ in range(T):
    # 读取输入数据
    n, n1, n2, n3, k = map(int, input().split())
    # 根据推导出的公式计算并输出结果
    ans = (n1 + n2 + n3 - k - n) // 2
    print(ans)

算法及复杂度

  • 算法：数学、集合论、容斥原理

  • 时间复杂度：对于每个测试用例，我们只进行常数次算术运算。总共有 个测试用例，因此总时间复杂度为 。

  • 空间复杂度：算法只需要固定的几个变量来存储输入和结果，因此总空间复杂度为 。