BISHI68 刷题统计

在这里插入图片描述这是一个经典的容斥原理应用题。

设三个集合分别为 $A$（新手）、$B$（算法入门）、$C$（算法进阶）。

已知 $n = |A \cup B \cup C|$ （至少刷过一个的总人数） $a = |A|, b = |B|, c = |C|$ （各题单人数） $d$: 恰好刷过两个题单的人数。设 $x$: 同时刷过三个题单的人数（我们要找的解）。

根据容斥原理：
$$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$$
其中，任意两个集合的交集（如 $|A \cap B|$）包含了“恰好刷过两个”的人和“刷过全部三个”的人。因此：$|A \cap B| + |A \cap C| + |B \cap C| = d + 3x$（因为 $x$ 这部分人在三个两两交集中各被算了一次）。

代入公式：
$$n = a + b + c - (d + 3x) + x$$

$$n = a + b + c - d - 2x$$
得出 $x$：
$$2x = a + b + c - n - d$$

$$x = \frac{a + b + c - n - d}{2}$$

流程图

在这里插入图片描述

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine().trim());

        for (int i = 0; i < T; i++) {
            String[] str = br.readLine().split("\\s+");
            long n = Long.parseLong(str[0]);
            long a = Long.parseLong(str[1]);
            long b = Long.parseLong(str[2]);
            long c = Long.parseLong(str[3]);
            long d = Long.parseLong(str[4]);
            long ans = (a+b+c-n-d)/2;

            out.println(ans);
        }

        out.flush();
        out.close();
        br.close();
    }