首页 > 试题广场 >

小红的01子序列构造（hard）

[编程题]小红的01子序列构造（hard）
  • 热度指数：1285 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}小红希望你构造一个长度为 n 的 \tt 01 串，满足 m 个性质：对于 i \in [1, m] ，区间 [l_i, r_i] 有恰好 x_i 个 \tt 0 ，y_i 个 \tt 1 ，k_i 个 \tt 01 子序列。
\hspace{15pt}给定的限制区间为两两包含关系。即对于 i \neq j ，若 l_i \leq l_j ，则 r_i \geq r_j ，反之亦然。

\hspace{15pt}子序列为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

输入描述:
\hspace{15pt}第一行输入两个正整数 n,m \left(1\leq n,m \leq 10^5\right) 代表 \tt 01 串的长度、限制的数量。
\hspace{15pt}接下来的 m 行，每行输入五个非负整数 l_i,r_i,x_i,y_i,k_i \left(1\leq l_i \leq r_i \leq n;\ 0\leq k_i \leq 10^{10};\ 0\leq x_i,y_i \leq r_i-l_i+1;\ x_i+y_i=r_i-l_i+1\right) ，代表构造的 \tt 01 串需满足区间 [l_i,r_i] 有恰好 x_i 个 \tt 0 ，y_i 个 \tt 1 ，k_i 个 \tt 01 子序列。
\hspace{15pt}保证给定的任意两个区间均为互相包含关系。


输出描述:
\hspace{15pt}如果答案不存在，直接输出 -1 ；否则，在一行上输出一个长度为 n 的 \tt 01 串。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

4 2
1 4 2 2 4
2 3 1 1 1

输出

0011
示例2

输入

4 2
1 4 2 2 3
2 3 1 1 1

输出

-1
算法知识视频讲解
添加回答
Python3
emdnauoy头像 emdnauoy
ls1 = list(map(int,input().split()))
n = ls1[0]
m = ls1[1]

def is_right(condi,s):
    l = condi[0]
    r = condi[1]
    x = condi[2]
    y = condi[3]
    k = condi[4]
    in_s = s[l-1:r]
    c_0 = in_s.count('0')
    c_1 = in_s.count('1')
    cnt = 0
    for i in range(len(in_s)-1):
        for j in range(i+1,len(in_s)):
            if in_s[i] == '0' and in_s[j] == '1':
                cnt += 1
    if c_0 == x and c_1 == y and cnt ==k:
        return True
    else:
        return False
condition = []
for i in range(m):
    ls = list(map(int,input().split()))
    condition.append(ls)

b_str = ''.join('1' for _ in range(n))
de = int(b_str,2)
for i in range(de+1):
    s_b = bin(i)[2:].zfill(n)
    k1 = is_right(condition[0],s_b)
    k2 = is_right(condition[1],s_b)
    if k1 and k2:
        print(s_b)
        break

   

发表于 2025-04-20 00:34:30 回复(0)
提交观点

问题信息

数论
难度：
1条回答 321浏览

热门推荐

相关试题

小红的01子序列构造（hard）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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