Rescue Nibel! - 每天一把CF - 20201009

每天一把CF : 2020-10-09

文章目录

• • 题目
  • 思路
  • 代码实现

题目

原题链接:https://codeforc.es/problemset/problem/1420/D

思路

题目大意：有n盏灯，每盏亮起和熄灭的时间是li和ri，现在需要选取k盏灯，这k盏灯需要满足必须在同一时刻是都亮着的,问最多有多少种选法。

思路：

刚看到这道题还说怎么那么简单，就直接写了个一维差分来做，结果直接数组超限，而且解决不了在同组灯中的时间交集内重复计数的问题。

硬顶了半天后还是乖乖的看了HINT,结果hint也没看懂…

The intersection of any k segments is either empty or is a segment. Let’s fix the left bound of the intersection and calculate the number of sets of k segments such that their intersection starts in this left bound.

还是看了别人的博客，说把这n盏灯进行排序后才有的思路。

首先我们亮的时间点为第一要素，灭的时间为第二要素进行排序。

然后我们一盏盏灯看过去，统计其前面熄灭时间大于等于这盏灯亮的时间的灯的个数cnt，若cnt>=k，加入这盏灯后我们能够有C（k，cnt）种选择方式。

然后思考，若cnt>k，则C（k，cnt）种选择方式中必定有C（k，cnt）已经被选取过了，所以我们要去掉。将公式列出来后我们能发现一个公式，即

ll ans = k;
		for (int i = 1; i < k; i++)
			ans *= cnt - i, ans %= mod;

但是这个方法止步于样例10，但前9个都对的，我觉得应该是哪里细节没处理好，明天我再来看看。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define ll long long
const ll MAX = 3e5 + 5, mod = 998244353;

typedef struct node {
	ll a, b;
}node;

ll  li, ri, ans;
ll n, k, fak = 1;
node a[MAX];

bool cmp(node& a, node& b) {//引用传递 不创建临时变量 提高效率
	if (a.a < b.a)
		return true;
	else if (a.a > b.a)
		return false;
	else
		if (a.b == b.b)
			return false;
		else if (a.b < b.b)
			return true;
		else
			return false;
}

ll pro(ll x, ll mod, ll k, ll fak) {
	ll  tp = a[x].a;
	ll  cnt = 0;
	for (int i = x; i; i--)
		if (a[i].b >= tp)
			cnt++;

	if (cnt >= k) {
		if (cnt == k)
			return 1;

		ll ans = k;
		for (int i = 1; i < k; i++)
			ans *= cnt - i, ans %= mod;

		ans /= fak;
		return ans;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> k;
	for (ll i = 1; i <= n; i++)
		cin >> a[i].a >> a[i].b;

	for (int i = 2; i <= k; i++)
	{
		fak *= i;
		fak %= mod;
	}

	sort(a + 1, a + 1 + n, cmp);

	//for (ll i = 1; i <= n; i++)
	//	cout << i << "\t" << a[i].a << "\t" << a[i].b << endl;

	ans = 0;
	for (ll i = k; i <= n; i++)
	{
		ans += pro(i, mod, k, fak);
		ans %= mod;
	}

	cout << ans << endl;
	//cout << "--->" << ans << endl;

	return 0;
}

本文地址：https://blog.csdn.net/weixin_45761327/article/details/108987430