luogu#P8545. 「Wdoi-2」不败的无尽兵团

    ID: 12531 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>数论洛谷原创提交答案Special JudgeO2优化构造洛谷月赛

「Wdoi-2」不败的无尽兵团

题目背景

畜生界是一个被动物灵所占据的,究极的弱肉强食的空间,也是个被几个组织所支配的世界——劲牙组、鬼杰组、刚欲同盟……

在这些动物灵其中也有一些灵长类动物的灵,也就是人类灵,它们弱小但又手脚灵活,作为完完全全的奴隶苟存在灵长园这一娱乐设施中。

但人类的灵也是有信仰的,它们向神明祈求,神也回应了人类的祈求,向人类给予了信仰的偶像。然而,人类灵原本只是皈依于存在于偶像背后的神性,却逐渐开始信仰起偶像本身来。结果,自然而然地,偶像开始支配人类,使得灵长园变成一个凶恶的失控组织。

畜生界也因为灵长园的暴动变得混乱,为了打倒偶像,鬼杰组希望能够卷入地上的人类,借用人类之手毁灭灵长园。动物灵们也就来到了地上,也就是幻想乡,带领灵梦一行人一同前往地狱。

题目描述

简要题意

对于正整数 nnnn529529625625),A={1,2,,n}A=\{1,2,\cdots,n\}m2m \ge 2 个子集 B1,B2,,Bm(Bi3)B_1,B_2,\cdots,B_m(|B_i| \geq 3) 为好的,如果对于 AA 的每一个三元子集 CC,都存在 恰好 一个 ii 使得 CCBiB_i 的子集。构造一个好的子集族使得 mm 尽量小(不超过题目给定的评分参数)。

原始题意

一路进入畜生界的灵梦,遭遇到了埴轮兵团的首长,杖刀偶磨弓的阻拦。

埴轮兵团由 nn 个战士组成,它们编号为 1,2,,n1,2,\dots,n。战士数量为 529529 或者 625625。作为一个兵团,要做到最好的进攻与防守,埴轮之间存在 mm 组配合关系 B1,B2,,BmB_1,B_2,\dots,B_m,每组关系包含若干个不同(但不少于 33 个)的埴轮战士,但不同组的关系中包含的埴轮战士可以重复。

但是灵梦并不事先知道这些配合关系,而且由于埴轮兵团配合默契,灵梦难以强行击败它们。在动物灵的帮助之下,灵梦发现,这些埴轮满足如下特点:从埴轮兵团中任意选出 33 个埴轮,都存在 恰好 一个 ii,使得这三个埴轮是 BiB_i 的一个子集。在满足这个特点的基础之上,由于磨弓的精力有限,无法同时维护太多组配合关系。因此,mm 是一个大于等于 22 的一个正整数,且其小于等于 mansm_{ans}

现在灵梦告诉了你埴轮兵团的总人数,请你告诉她一种可能的埴轮兵团配合的情况,帮助她打败杖刀偶磨弓,进入灵长园。

输入格式

第一行有一个正整数 nn,含义如题意所示。保证 n=529n=529 或者 625625

输出格式

第一行输出一个正整数 mm,表示你构造的方案使用的集合的总个数。应当满足 m2m\ge 2

接下来 mm 行,每行输出若干个整数。第一个整数 ss 表示你构造的 BiB_i 的大小,应当满足 ns>0n\ge s>0。接下来 ss 个整数描述 BiB_i 内的元素,中间用空格隔开。

4
4
3 1 2 3
3 1 2 4
3 1 3 4
3 2 3 4
5
7
4 1 2 3 4
3 1 2 5
3 1 3 5
3 1 4 5
3 2 3 5
3 2 4 5
3 3 4 5

提示

样例 1 解释

样例仅供理解题意参考。实际数据中,nn 只会为 529529625625

由于 m>1m>1,因此结果不能为 {{1,2,3,4}}\{\{1,2,3,4\}\};又因为 Bi<3|B_i|< 3BiB_i 无用,于是唯一的方案就是列出 {1,2,3,4}\{1,2,3,4\} 的所有三元子集 {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n=} & \bm{m_{\text{ans}}=} & \textbf{分值} \cr\hline 1 & 529 & 1.25\times 10^4 & 75 \cr\hline 2 & 625 & 1.60\times 10^4 & 25 \cr\hline \end{array}$$

如果你输出的方案不合法,那么你将不能获得该测试点的得分。

当你构造的解符合题设,并且 mm 的值不超过 mansm_{\text{ans}},你才能获得该测试点的分值。