欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Rescue Nibel! - 每天一把CF - 20201009

程序员文章站 2022-04-14 08:53:39
每天一把CF : 2020-10-09文章目录题目思路代码实现题目原题链接:https://codeforc.es/problemset/problem/1420/D思路题目大意:有n盏灯,每盏亮起和熄灭的时间是li和ri,现在需要选取k盏灯,这k盏灯需要满足必须在同一时刻是都亮着的,问最多有多少种选法。思路:刚看到这道题还说怎么那么简单,就直接写了个一维差分来做,结果直接数组超限,而且解决不了在同组灯中的时间交集内重复计数的问题。硬顶了半天后还是乖乖的看了HINT,结果hint也没看....

每天一把CF : 2020-10-09

文章目录

题目

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

Rescue Nibel!  - 每天一把CF - 20201009

思路

题目大意:有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