#1710. 多控制反转

    ID: 1710 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1059来源:qoj.ac数据:公开样例构造

多控制反转

多控制反转

题目描述

标题: 多控制反转 - Problem - QOJ.ac

#5176. 多控制反转

Statistics

The problem was used in the following contests:

平面上有 m 个 01 变量,编号依次为 0,1,…,m−1,你并不知道这些变量的初始值。

你可以进行若干种操作:

单点反转,形如 1 x,表示把编号为 x 的 01 变量反转(0 变成 1,1 变成 0)。

单控制反转,形如 2 x y(你需要保证 x≠y),表示,假如进行操作时编号为 x 的 01 变量值为 1,那么把编号为 y 的 01 变量反转;否则什么都不干。

双控制反转,形如 3 x y z(你需要保证 x,y,z 两两不同),表示,假如进行操作时编号为 x 和编号为 y 的 01 变量值都为 1,那么把编号为 z 的 01 变量反转;否则什么都不干。

现在给定你 n,Q,其中 n 是一个小于 m 的非负整数,你需要构造一个长度不超过 Q 的操作序列,使得对于这 m 个 01 变量所有可能的初始值,满足:

假如编号为 0,1,…,n−1 的 01 变量初始值都为 1 时,在依次执行完操作序列里的操作后,编号为 n 的 01 变量会反转,而其他变量值都和初始一致。

假如编号为 0,1,…,n−1 的 01 变量初始值不全为 1 时,在依次执行完操作序列里的操作后,所有变量值都和初始一致。

注意:显然我们不可能用所有 2m 种情况都对你构造的操作序列进行检查,在真实测试中,对于每个测试点,我们会选取一部分可能的初始情况进行检查,设这些情况构成的集合为 T,你只需要保证你构造的操作序列在 T 内的所有情况满足条件即可。

输入格式

第一行四个正整数 n,m,Q,case。其中 n,m,Q 含义与题目描述中相同,case 是该数据所在子任务的编号。特别的,如果 case=0,说明这是样例数据。

输出格式

第一行一个整数 k,表示你构造的操作序列长度,你需要保证 0≤k≤Q。

接下来 k 行,对于第 i 行,先输出一个整数 ty∈{1,2,3} 表示第 i 个操作的操作类型,然后输出 ty 个数表示该操作涉及的变量编号,格式参见题面。

样例

样例输入 1

3 5 25 0

样例输出 1

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

枚举所有初始情况即可检验该方案正确性。

数据范围

子任务编号 n≤ Q= m= 特殊限制 子任务分数 子任务依赖 1 20 8n+1 2n+2 A 15 2 50 10 1 3 10 2 4 20 n2+1 n+2 A 10 5 20 4 6 50 28n+1 10 7 100 8n+1 A 10 2,4 8 15 3,5,6,7

特殊限制A:∀(x0x1…xm−1)∈T,保证 xn+1=xn+2=⋯=xm−1=0。

对于所有数据,保证 0≤n≤100,m≥n+2,Q≥8n+1。

时间限制:5s

空间限制:512 MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 5 25 0
4
3 0 1 4
3 2 4 3
3 0 1 4
3 2 4 3