专栏文章

题解：P14239 [CCPC 2024 Shandong I] 多彩的线段 2

CConfused_Fhy
P14239题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjsfkw
此快照首次捕获于
2025/12/02 03:34
3 个月前
此快照最后确认于
2025/12/02 03:34
3 个月前
查看原文
区间覆盖板题。

题目描述

共有 nn 条线段，每条线段可以涂 kk 种颜色中一种，要求任意两条颜色相同的线段没有重合，求不同的涂色方案有多少种。

思路

显然，我们可以用一个优先队列维护每一条线段的左端点，找到前面有多少与它没有交集的线段，最后利用排列组合算出答案即可。
别忘了对传奇模数 998244353998244353 取模。
别忘了清空优先队列。

Code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rap(i, a, b) for(int i = a; i < b; i ++)
#define dwn(i, a, b) for(int i = a; i >= b; i --)
#define iosfst ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
const int mod = 998244353;
int pre[501000];
struct node{
	int l, r;
};
node a[501000];
bool cmp(node a, node b){
	if(a.l == b.l) return a.r < b.r;
	return a.l < b.l;
}
priority_queue<int, vector<int>, greater<int>> q;
void solve(){
	int n, k; cin >> n >> k;
	rep(i, 1, n) cin >> a[i].l >> a[i].r;
	sort(a + 1, a + n + 1, cmp);
	int ans = 1;
	rep(i, 1, n){
		while(!q.empty() && q.top() < a[i].l) {
			k ++;
			q.pop();
		}
		ans *= k;
		ans %= mod;
		k --;
		q.push(a[i].r);
	}
	while(q.size()) q.pop();
	cout << ans << '\n';
}
signed main() {
	iosfst;
	int t; cin >> t;
	while(t --){
		solve();
	}
	return 0;
}
STL 万岁。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...