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
上一篇: PHP学习笔记:php网络流量统计系统
下一篇: c语言,可变参数列表实现任意个数求平均值