codeforce 421D D. Bug in Code

时间：2021-03-14 08:38:51

题目链接：

http://codeforces.com/problemset/problem/421/D

D. Bug in Code

time limit per test 1 secondmemory limit per test 256 megabytes
#### 问题描述
> Recently a serious bug has been found in the FOS code. The head of the F company wants to find the culprit and punish him. For that, he set up an organizational meeting, the issue is: who's bugged the code? Each of the n coders on the meeting said: 'I know for sure that either x or y did it!'
>
> The head of the company decided to choose two suspects and invite them to his office. Naturally, he should consider the coders' opinions. That's why the head wants to make such a choice that at least p of n coders agreed with it. A coder agrees with the choice of two suspects if at least one of the two people that he named at the meeting was chosen as a suspect. In how many ways can the head of F choose two suspects?
>
> Note that even if some coder was chosen as a suspect, he can agree with the head's choice if he named the other chosen coder at the meeting.
#### 输入
> The first line contains integers n and p (3 ≤ n ≤ 3·105; 0 ≤ p ≤ n) — the number of coders in the F company and the minimum number of agreed people.
>
> Each of the next n lines contains two integers xi, yi (1 ≤ xi, yi ≤ n) — the numbers of coders named by the i-th coder. It is guaranteed that xi ≠ i,  yi ≠ i,  xi ≠ yi.
#### 输出
> Print a single integer — the number of possible two-suspect sets. Note that the order of the suspects doesn't matter, that is, sets (1, 2) and (2, 1) are considered identical.
#### 样例
> **sample input**
> 4 2
> 2 3
> 1 4
> 1 4
> 2 1
>
> **sample output**
> 6

题意

对于特定的两个人(u,v)如果有至少p个人认为其中的一个是buger，那么这两个人就有可能被叫到办公室。现在叫你求所有满足条件的(u,v)。

我们用agr[i]表示质疑i的人数，mp[u,v]记录同时质疑u、v的人数。那么对于(u,v)只要满足agr[u]+agr[v]-mp[u,v]>=p，就有可能被叫到办公室。

为了快速计算结果，这里我们做个转换、ans=sigma(agr[u]+agr[v]>=k)-sigma(agr[u]+agr[v]-mp[u,v]<k)对于agr数组，我们排个序，就能O(n)时间统计出sigma(agr[u]+agr[v]>=k)。而sigma(agr[u]+agr[v]-mp[u,v]<k)只要扫一遍mp里面的元素就可以了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<algorithm>

#define X first

#define Y second

#define mkp make_pair

using namespace std;

const int maxn = 3e5 + 10;

typedef __int64 LL;

int n, m;

int agr[maxn];

map<pair<int, int>, int> mp;

map<pair<int, int>, int>::iterator iter;

int main() {

	memset(agr, 0, sizeof(agr));

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) {

		int u, v;

		scanf("%d%d", &u, &v);

		if (u > v) swap(u, v);

		agr[u]++; agr[v]++;

		mp[mkp(u, v)]++;

	}

	LL ans = 0;

	for (iter = mp.begin(); iter != mp.end(); iter++) {

		int u = (iter->X).X, v = (iter->X).Y, cnt = iter->Y;

		if (agr[u] + agr[v] >= m&&agr[u] + agr[v] - cnt < m) ans--;

	}

	sort(agr + 1, agr + n + 1);

	//for (int i = 1; i <= n; i++) printf("%d ", agr[i]);

	//printf("\n");

	int st = 1, ed = n;

	for (; st < n; st++) {

		while (ed > st&&agr[st] + agr[ed] >= m) ed--;

		ans += min(n - ed,n-st);

	}

	printf("%I64d\n", ans);

	return 0;

}

杂七杂八

这一题最关键的地方就是建模吧！把问题转换成求agr[u]+agr[v]-mp[u,v]。从而利用一些算法和套路来解决实际问题。

相关文章