#P18720. Remix

    ID: 18056 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-全子集枚举鸽巢原理格雷码相邻状态增量更新不变量分析

Remix

Remix

给定一个由 nn 个整数组成的多重集 SS。你需要重复执行下列三步操作,直到 SS 中只剩一个整数:

  1. 选择 SS 的一个子多重集 TT,满足 ∣T∣≥2|T|\ge2。
  2. 从 SS 中删除 TT 的全部元素。
  3. 向 SS 中插入一个整数 max⁡(T)−min⁡(T)\max(T)-\min(T)。

请构造一系列操作,使最后剩下的整数尽可能大。

输入格式

第一行一个整数 nn,2≤n≤1052\le n\le10^5。

第二行 nn 个整数 S1,S2,…,SnS_1,S_2,\ldots,S_n,0≤Si≤1050\le S_i\le10^5。数值可以重复,也可以为 00;它们按出现次数构成多重集。

输出格式

第一行输出操作次数 kk,1≤k≤n−11\le k\le n-1。

接下来 kk 行,每行先输出所选子多重集的大小 mm,再输出其中的 mm 个数值 T1,T2,…,TmT_1,T_2,\ldots,T_m,顺序任意,2≤m≤n2\le m\le n。这些数值不是初始下标。

操作按输出顺序执行。每步的 TT 必须是此前所有操作完成后当前 SS 的子多重集;如果某个数值被选取多次,当前必须有足够多个副本。最后必须恰好剩一个整数,并且达到最大可能值。可以输出任意一种最优操作序列。

原样例

7
33 24 63 48 97 90 93
4
3 33 93 90
2 63 60
2 48 24
3 97 24 3

原样例说明

样例可以按下表操作。表中带下划线的值表示该步新插入的数:

步骤 选取的 TT 操作后的 SS
0 — {24,33,48,63,90,93,97}\{24,33,48,63,90,93,97\}
1 {33,90,93}\{33,90,93\} {24,48,60‾,63,97}\{24,48,\underline{60},63,97\}
2 {60,63}\{60,63\} {3‾,24,48,97}\{\underline{3},24,48,97\}
3 {24,48}\{24,48\} {3,24‾,97}\{3,\underline{24},97\}
4 {3,24,97}\{3,24,97\} {94‾}\{\underline{94}\}

四步后只剩 9494。可以证明不存在使最终整数更大的操作序列。