题目描述
在一个标有 $1$~$1−n$ 的数轴上给定 $m$ 条线段,第 $i$个线段的左右端点分别为,求有多少种线段的选择方案可以使得数轴上的每个整数点至少被覆盖两次。
定义两种选择方案不同当且仅当至少有一个线段在两种方案中的状态(选/不选)不同。
由于方案数可能很多,所以你需要输出满足条件的方案数对 $998244353$ 取模的结果。
线段类问题
常用的思路是 贪心,通过对区间左/右端点排序,从而求解某些问题
本题数据范围很小(因为是Easy Version),所以直接考虑枚举
枚举所有10根线段选不选,共 $2^{10}$,因此方案数最多 $1024$,不用取模;
枚举的时候采用 状态压缩,二进制位来表示每条线段是否选择;
同时,要将被覆盖的区间的数组统一加上 $1$,采用 差分 即可
c++代码
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
const int N = 100010, M = 15;
int n, m, st[N], res;
pii g[M];
void add(int l, int r)
{
st[l] ++, st[r + 1] --;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++)
scanf("%d%d", &g[i].first, &g[i].second);
for(int i = 1; i < (1 << m); i ++)
{
memset(st, 0, sizeof st);
for(int j = 0; j < m; j ++)
if(i >> j & 1)
add(g[j + 1].first, g[j + 1].second);
bool flag = true;
for(int j = 1; j <= n; j ++)
{
st[j] += st[j - 1];
if(st[j] < 2){
flag = false;
break;
}
}
if(!flag) continue;
else res ++;
}
cout << res << endl;
return 0;
}