#P12311. [2025年联测]费用流

    ID: 11460 传统题 1500ms 512MiB 尝试: 10 已通过: 1 难度: 10 上传者: 标签>贪心字符串后缀数组数据结构字符串哈希CF3200线段树

[2025年联测]费用流

费用流(mcmf)

题目描述

给定长度为 nn 的非负整数数组 aa,以二进制形式描述。你要构造非负整数数组 bb,满足 bi≥aib_i\ge a_i,且对任意 i<ji<j,biANDbj=0b_i\mathbin{\mathrm{AND}}b_j=0。其中 AND 为按位与。

求最小的 ∑i=1nbi\sum_{i=1}^n b_i。

输入格式

从标准输入读取数据。第一行正整数 nn。接下来 nn 行,第 ii 行先给出 kik_i,再给出 kik_i 个数 xi,1,…,xi,kix_{i,1},\ldots,x_{i,k_i},表示 ai=∑j=1ki2xi,j−1a_i=\sum_{j=1}^{k_i}2^{x_{i,j}-1}。

输出格式

在标准输出中输出一行,表示最小和的二进制表示,不带前导零。

样例 1

输入

2
1 1
2 1 2

输出

101

解释

a=[1,3]a=[1,3],可取 b=[1,4]b=[1,4],总和为 55。

样例 2

输入

4
2 1 2
1 1
5 4 5 6 7 9
2 1 8

输出

111111111

解释

可取 b=[4,1,376,130]b=[4,1,376,130]。

数据范围

令 M=∑ixi,kiM=\sum_i x_{i,k_i},X=max⁡ixi,kiX=\max_i x_{i,k_i}。1≤n,M≤1061\le n,M\le10^6,ki≥1k_i\ge1,1≤xi,1<⋯<xi,ki1\le x_{i,1}<\cdots<x_{i,k_i}。

子任务 n≤n\le X≤X\le M≤M\le 特殊约束 分值
1 2 10510^5 10510^5 无 10
2 1000 A 9
3 10510^5 10510^5 10
4 5 无 8
5 10510^5 11
6 50 2500
7 1000 10510^5 12
8 10510^5 14
9 10610^6 15

特殊性质 A:所有 ki=1k_i=1。每个子任务内的所有测试点均通过,才能得到该组分数。