#2745. 「CTSC 2011」字符串重排

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

对于两个字符串 A = a_1a_2\cdots a_n B = b_1b_2\cdots b_m ,定义其最长公共前缀长度 \text{LCP}(A, B) 如下:

\text{LCP}(A,B)=\max \{k|0\le k\le n,k\le m,a_1a_2\cdots a_k=b_1b_2\cdots b_k\}

给定 n 个由小写字母组成的两两不同的非空字符串 S_1, S_2, \cdots , S_n ,对于一个 1 n 的排列 P = (p_1, p_2, \cdots , p_n) ,定义 P 的价值 W(P) 如下:

W(P)=\sum_{i=2}^n (\text{LCP}(S_{p_{i-1}},S_{p_i}))^2

我们设能够产生最大价值的排列为 P_G^*

此外,还有 q 个附加任务。对于第 i 个任务,给定两个 1 n 之间的不同的整数 X_i Y_i 。对于排列 P ,若 P 在满足 W (P) = W (P_G^*) 的前提条件之下,同时满足第 X_i 个字符串 S_{X_i} 恰好排在第 Y_i 个字符串 S_{Y_i} 之前, 即 \text{pos}(S_{X_i}) +1= \text{pos}(S_{Y_i}) ,其中 \text{pos}(S_i) 表示字符串 S_i 在排列中的位置,则排列 P 还将获得 2^i 的奖励。所有任务的奖励之和称之为总任务奖励。

我们设能够使得总任务奖励最大的排列为 P_B^*

试求:

  1. W(P_G^*) ,即可能产生的最大价值;
  2. P_B^* ,在保证最大价值前提下,可以使总任务奖励最大的排列。

输入格式

第一行包含两个整数 n q ,表示字符串和附加任务的数量,中间用一个空格隔开;

接下来 n 行,描述字符串,其中第 i 行包含一个字符串 S_i

接下来 q 行,描述附加任务,其中第 i 行包含两个整数 X_i Y_i ,中间用一个空格隔开。

输出格式

包含三行。

第一行包含一个非负整数 W(P_G^*)
第二行若干个数,每两个数之间用一个空格隔开,这一行第一个数表示满足附加任务的数量 k ,接下来 k 个数为这些任务的序号,序号从 1 开始,按从小到大的顺序输出;
第三行包含 n 个用一个空格隔开的正整数,表示一个 1 n 的排列 P_B^*

样例

样例输入

4 6
a
b
abc
bc
1 2
1 3
3 1
4 2
2 4
2 4

样例输出

2
4 1 3 5 6
3 1 2 4

数据范围与提示

评分标准

对于一个测试点:

  • 如果输出文件的第一行正确可以得到 2 分;
  • 如果输出文件的第二行正确可以得到 4 分;
  • 如果输出文件的第三行正确可以得到 4 分;
  • 如果输出文件的两行都正确则可以得到 10 分。

对于第三问中的排列,如果存在多个解, 则输出任意一个解均可得分。
若某问无法完成,也请按照格式输出,以避免测评失败。

数据范围

对于 10\% 的数据, n\le 10,q=1 ,每个字符串的长度不超过 50
对于 20\% 的数据, n\le 50,q=1 ,每个字符串的长度不超过 50
对于 50\% 的数据, n,q\le 1000 ,每个字符串的长度不超过 1000
对于 70\% 的数据,任意字符串不为其他任何一个字符串的前缀;
对于 100\% 的数据, n\le 4\times 10^4,q\le 10^5 , 每个字符串的长度不超过 10^4 ,所有字符串的长度和不超过 2\times 10^5