#1960. 这里是,终末停滞委员会。
这里是,终末停滞委员会。
这里是,终末停滞委员会。
题目描述
标题: 这里是,终末停滞委员会。 - Problem - QOJ.ac
#14583. 这里是,终末停滞委员会。
The problem was used in the following contests:
「你们……到底是谁……?」
少女笑了。
「——我们是终末停滞委员会。是一群执意守护这个已经终结的世界的,喜欢做蠢事的家伙!」
题目描述
合理主义的 Corporations——「洗钱机构」。
官僚主义的卡乌斯学院——「官僚人员」。
成果主义的苍之学园——「白衣蛮族」。
……尽管大家总是这样争吵着,可还是有需要一起出任务的时候呢。
考虑到这么长的名字谁记得住啦——为了身为选手的你方便起见,下面我们把三所学园称为 A、B、C。
三所学园共有 n 名学生。任务共有两种,分别有 m1,m2 个,对于每个任务,都指定了两名参与者 ai,bi。
- 对于所有任务:当两名参与者都来自学园 C 时,获得 2 点收益。
- 仅对于第二种任务:如果两名参与者有恰好一名来自学园 C,则遭受 1 点损失。若两名参与者来自同样的学园,则遭受 2 点损失。
现在,某些学生入学的学园已经确定,你需要确定剩余的所有学生入学的学园,来最大化所有任务的总净收益(即,总收益减去总损失)。注意收益和损失可以叠加,例如如果完成第二种任务的两名学生都来自学园 C,则获得的净收益是 2−2=0。
然而,这个问题实在有些太简单了,因此我们给出正整数 k,接下来,把学生所属的学园对应的字母依次连接,得到一个长度为 n 的仅包含 A、B、C 三种字母的字符串,你需要给出所有最大化净收益的方案中,字符串的字典序前 k 小的方案。若方案数小于 k,则你需要给出所有方案。
输入格式
第一行包含四个非负整数 n,m1,m2,k。
第二行包含一个长度为 n 的由 ABC? 组成的字符串,依次代表每名学生入学的学园。如果为 ? 则代表尚未确定。
接下来 m1 行,每行包含两个正整数 ai,bi,代表参与第一种任务的两名学生。
接下来 m2 行,每行包含两个正整数 ai,bi,代表参与第二种任务的两名学生。
输出格式
第一行包含一个整数,代表最大的总净收益。
接下来,设 c 为达到最大净收益的不同方案数。输出 min(c,k) 行,每行为一个长度为 n 的由 ABC 组成的字符串。其中第 i 行的输出对应字典序第 i 小的方案。
样例
样例输入 1
4 2 3 100
????
4 2
4 2
3 1
3 1
1 3
样例输出 1
4
ACBC
BCAC
CCCC
样例输入 2
6 2 8 2
B???B?
2 6
1 3
1 5
1 3
6 4
3 2
5 4
3 4
5 6
1 3
样例输出 2
-4
BBABBA
BCACBC
数据范围
记 m=m1+m2。
对于所有数据:1≤n≤105,0≤m≤105,1≤k≤6×105,max(n,m)×k≤107。
- 子任务 1(2 分):m=0;
- 子任务 2(7 分):n≤15;
- 子任务 3(8 分):n≤2×104,所有的任务都是第一种任务;
- 子任务 4(9 分):n≤2×104,初始时,没有任何学生入学的学园已经确定;
- 子任务 5(24 分):n≤2×104,所有的任务都是第二种任务;
- 子任务 6(20 分):n≤2×104,k=1;
- 子任务 7(18 分):n≤2×104;
- 子任务 8(12 分):无特殊限制。
本题有 Special Judge,如果输出正确的最大收益和错误的方案,也可以获得对应子任务 50% 的分数。如果你只希望获得这 50% 的分数,一种方法是在第一行输出最大收益之后,后续不再输出其它内容。
后记
「所以啊——」
这会成为对你的祈愿诅咒。我深信不疑。
「——你只要做你自己就好。不去当什么轻小说的主角,也可以哦。」
他瞪大了眼睛。从他的眼角,大颗的泪珠滚落而下。
——「啪咔」。
那是他手掌中,小小的手枪碎裂的声音。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 2 3 100
????
4 2
4 2
3 1
3 1
1 3
4
ACBC
BCAC
CCCC
样例 2
6 2 8 2
B???B?
2 6
1 3
1 5
1 3
6 4
3 2
5 4
3 4
5 6
1 3
-4
BBABBA
BCACBC