Exam in MAC
题意
\(t\) 组数据。
给定一个大小为 \(n\) 的集合 \(s\) 和一个整数 \(c\)，保证 \(0 \leqslant s_i \leqslant c(1 \leqslant i \leqslant n)\)。
求有多少对整数数对 \((x,y)\)，满足：
- \(0\leqslant x \leqslant y \leqslant c\)。
- \(x + y \notin s\) 且 \(y - x \notin s\)。
数据范围
- \(1 \leqslant n \leqslant 3 \times 10^5, 1 \leqslant c \leqslant 10^9\)。
- \(0 \leqslant s_i \leqslant c(1 \leqslant i \leqslant n)\)。
- \(s_i < s_{i + 1}(1 \leqslant i < n)\)。
思路
容斥题。
求不满足两个条件的数对个数，可以转化为总数对个数减满足其中任意一个条件(即 \(x + y \in s\) 或 \(y - x \in s\))的数对个数，再加满足两个条件的数对个数。
- 总数对个数：对于 \(x = 0\)，\(y\) 有 \(c + 1\) 种取法；对于 \(x = 1\)，\(y\) 有 \(c\) 种取法……总个数为 \(\frac{(c + 2) \times (c + 1)}{2}\)。
- 满足 \(x + y \in s\) 的数对个数：由于 \(s\) 中的元素互不相同，那么只要分别处理每个 \(x + y = s_i\) 的数对个数即可。注意 \(x \leqslant y\)，总个数为 \(\left\lfloor \frac{s_i}{2} \right\rfloor + 1\)。
- 满足 \(y - x \in s\) 的数对个数：同理，也只需要分别处理每个 \(y - x = s_i\) 的数对个数即可。转换式子，\(y = x + s_i\)，由于 \(0 \leqslant y \leqslant c\)，所以 \(0 \leqslant x \leqslant c - s_i\)，总个数为 \(c - s_i + 1\)。
- 满足 \(x + y \in s\) 且 \(y - x \in s\) 的数对个数：假设 \(x + y = s_i,y - x = s_j\)，推一下式子，可得 \(\begin{cases}2 \times x = s_i - s_j\\ 2 \times y = s_i + s_j\end{cases}\)。由于 \(x\) 和 \(y\) 都是整数，则 \(s_i - s_j\) 和 \(s_i + s_j\) 都必须是偶数。易得当 \(s_i\) 和 \(s_j\) 奇偶性相同时存在数对 \((x,y)\)。很明显，\(y =\frac{s_i + s_j}{2} \leqslant c\)。令 \(a\) 为 \(s\) 中元素的奇数个数，\(b\) 为 \(s\) 中元素的偶数个数，总个数为 \(\frac{(a + 1) \times a}{2}+\frac{(b + 1) \times b}{2}\)。
记得答案要开 long long。
复杂度
- 时间：\(O(n)\)。
- 空间：\(O(1)\)。
Code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int T, n, c, sum[2]; // sum[0] 记录偶数个数，sum[1] 记录奇数个数
long long ans; // 答案开 long long
void Solve () {
cin >> n >> c;
ans = 1ll * (c + 2) * (c + 1) / 2; // 初始数对个数
for (int i = 1, x; i <= n; i++) {
cin >> x, ans -= x / 2 + 1 + c - x + 1, sum[x % 2]++; // 减去满足任意一个条件的数对个数
}
cout << ans + 1ll * (sum[0] + 1) * sum[0] / 2 + 1ll * (sum[1] + 1) * sum[1] / 2; // 加上满足两个条件的数对个数
sum[0] = sum[1] = 0;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
for (cin >> T; T--; Solve(), cout << '\n') {}
return 0;
}