行业知识
Codeforces Round 932 (Div. 2)D. Exam in MAC 正难则反,容斥,对顺序求一些值
2026-11-17 03:29:48
来源:互联网转载
Problem - D - Codeforces
()目录
()题意:
思路:
总的对数:
x+y==ai:
y-x == ai:
两个都不符合:
参考代码:
题意:
给你一个n个数的集合a,和整数c
求0~c中有多少对x,y的组合可以使得x+y与y-x都不出现在集合a中。
思路:
我们可以求出总的对数,减去不合法数即可。
由于有两个不合法的条件,我们可以使用*容斥* (减去任意一个不合法的再加上两个都不合法的)
总的对数:
//0 : c+1 x为0时,y可以是0~c的任意一个,有c+1种
//1 : c
//c : 1
// (c+2)*(c+1)/2
x+y==ai:
//0 ai
//1 ai-1
//2 ai-2
//...
// 一共 ai/2 +1 对
(如ai == 7 :
//0+7,1+6, 2+5, 3+4
4种,7/2 == 3下取整, 再加一
y-x == ai:
ai 0
ai+1 1
...
c (c-ai)
一种 c-ai+1 对
两个都不符合:
x+y == ai
y-x == aj
解得:
y = (ai+aj)/2
x = (ai-aj)/2
必须是整数,所以ai+aj是偶数。同时ai也必定大于aj,x也满足。
但总数是多少呢?
其实就是看集合a中多少个奇数对和偶数对。
我们遍历的过程中就能求出来。
统计i之前有多少个奇数cnt1和偶数cnt2即可(包括自己,即ai == aj ,x为0的情况),a[ i ]是奇数就加cnt1种,偶数则cnt2种。
参考代码:
#includeusing namespace std;#define ll long long#define endl "\n"#define int long long// 7//1+6,2+5,3+4//还有0和7!void solve(){int n, c;cin >> n >> c;vectorarr(n + 1);for (int i = 1; i > arr[i];sort(arr.begin(), arr.end());ll ans = (c + 2) * (c + 1) / 2;int s1, s2, c1, c2, s3;s1 = s2 = s3 = 0;c1 = c2 = 0;for (int i = 1; i