首页 > 试题广场 >

小A的线段（easy version）

[编程题]小A的线段（easy version）
  • 热度指数：94 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}在坐标轴的整数点 1\sim n 上给出 m 条闭区间线段，第 i 条线段用其端点 [\,st_i,\,ed_i\,] 描述。

\hspace{15pt}现在要从这 m 条线段中选择若干条，使得每个整数点被至少两条所选线段覆盖。求满足条件的选择方案数量；两种方案视为不同，当且仅当存在某条线段在两方案中的"选/不选"状态不同。

\hspace{15pt}答案对 P=998\,244\,353 取模。

输入描述:
\hspace{15pt}第一行输入整数 n,m\;(2\leqq n\leqq 10^5,\ 1\leqq m\leqq 10)。 
\hspace{15pt}随后 m 行，每行两个整数 st_i,ed_i（1\leqq st_i<ed_i\leqq n） 描述一条线段。


输出描述:
\hspace{15pt}输出满足条件的方案数对 998244353 取模的结果。
示例1

输入

5 4
4 5
1 5
3 5
1 4

输出

3
算法知识视频讲解
添加回答
pypy3
牛客348448733号头像 牛客348448733号
n, m = map(int, input().split())
line = [[0, 0]]*m
select = [True]*m
for i in range(m):
    sti, edi = map(int, input().split())
    line[i] = [sti, edi]

def check(line):
    cover = [0]*n
    for j in range(len(line)):
        temp = [0]*(line[j][0]-1) + [1]*(line[j][1]-line[j][0]+1) + [0]*(n-line[j][1])
        cover = [temp[i]+cover[i] for i in range(len(temp))]
    return cover

def check_update(state, j, line):
    temp = [0]*(line[j][0]-1) + [1]*(line[j][1]-line[j][0]+1) + [0]*(n-line[j][1])
    cover = [-temp[i]+state[i] for i in range(len(temp))]
    return cover

cnt = [0]
def dfs(i, state, line):
    if i == m:
        cnt[0] = (cnt[0] + 1)%998244353
        return

    if min(state) < 2:
        return
   
    state_ = check_update(state, i, line)
    if min(state_) >= 2:
        dfs(i+1, state_, line)
   
    dfs(i+1, state, line)
   

cover = check(line)
dfs(0, cover, line)
print(cnt[0]%998244353)
发表于 2025-08-14 23:55:38 回复(0)
提交观点

问题信息

dfs
来自：华为机试编程模拟题5
难度：
1条回答 71浏览

热门推荐

相关试题

小A的线段（easy version）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号