小工具知识网

当前位置: 首页 > 行业知识 > Codeforces Round 932 (Div. 2)D. Exam in MAC 正难则反,容斥,对顺序求一些值

行业知识

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 

上一篇:WPS下载指南,轻松获取并安装WPS Office

下一篇:轻松上手!Radeon软件下载及操作指南全解析