当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6855:Auto-correction

Special Judge 特殊评判
题目描述
It is preferrable to read the pdf statment.

Cuber QQ is poor in English writing, and in the process of preparing this contest, he realized that he is making too many grammar mistakes that an auto-correction engine is needed. Instead of using online tools like ''Microsoft Aim Writing'' or ''Grammarly'', he was interested in building a new engine on his own.

In particular, he adopted a naive sequence-to-sequence model, that takes a sequence, which is usually a sentence, and predict for each token, which is usually a word or character, whether there is something wrong with it, and if yes, what it should be replaced with. Here are several examples:


  • In ''Cuber QQ was one of the admirers Quber CC.'', ''admirers'' should be replaced with ''admirers of''.

  • In ''Cuber QQ confess his love to Cuber QQ just now.'', ''confess'' should be replaced with ''confessed''.

  • In ''Quber CC said that they are being and always will be good friends.'', ''are being'' should be replaced with ''are''.



You might notice that, in this sequence-to-sequence model, the phrase to replace should be at least one token, and the target should be at least one token too. This is related to the architecture and training approach of his model. We will not go into too many machine learning details here, as it will make the statement tedious. The problem is however, the training data does not conform with such format. In the training data, a sequence with flaws can be annotated with three types of annotations: add, delete and replace. Concretely,


  • $A$ $l$ $s_1$ $s_2$ $\cdots$ $s_v$: to add sequence $s$ before position $l$.

  • $D$ $l$ $r$: to delete from $l$-th token to the $r$-th token, inclusive.

  • $R$ $l$ $r$ $s_1$ $s_2$ $\cdots$ $s_v$: to replace sub-sequence from $l$-th token to $r$-th token, inclusive, with sequence $s$.



All the annotations are applied directly to the original sequence, i.e., the indices like $l$ and $r$ refers to the original indices, instead of the indices after modification.

As ''add'' and ''delete'' will not be supported in the model, the preprocessing step needs to rewrite all ''add'' and ''delete'' with ''replace''. Furthermore, as there are many ways to achieve such goal, Cuber QQ wants to find the cheapest way, i.e., after the annotation rewriting, the total number of replaced tokens should be as minimum as possible. If there is a tie, the number of annotation records should be as minimum as possible. In case there is still a tie, any one of them is acceptable.
输入解释
The input starts with an integer $t$ ($1 \le T \le 50~000$), denoting the number of test cases.

For each test case, the first line contains two space-separated integers $n$ and $q$ ($1 \le n, q \le 2~000$), where $n$ is the number of tokens in the original sequence, and $q$ is the number of original annotations.

In the next line, $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) are presented, denoting the sequence.

The $i$-th of the following $q$ lines is in one of the 3 formats:


  • $A$ $l_i$ $s_{i,1}$ $s_{i,2}$ $\cdots$ $s_{i,{v_i}}$ ($1 \le l_i \le n + 1$, $1 \le s_{i,k} \le n$). Notably, when $l_i = n + 1$, it is to add tokens at the end of sequence.

  • $D$ $l_i$ $r_i$ ($1 \le l_i \le r_i \le n$).

  • $R$ $l_i$ $r_i$ $s_{i,1}$ $s_{i,2}$ $\cdots$ $s_{i,{v_i}}$ ($1 \le l_i \le r_i \le n$, $1 \le s_{i,k} \le n$).



It is guaranteed that $l_i \le l_{i+1}$ for all $1 \le i < n$, and $l_i = l_{i+1}$ only happens when $i$ is $A$ and $i+1$ is not, which means, there is at most one ''add'' at the same position. The annotations are non-overlapping, i.e., $r_i \le l_{i+1}$ for all $1 \le i < n$ if $r_i$ is available for $i$. Furthermore, the corrected sequence after applying all the annotations is not empty.

It is guaranteed that for each test case, the corrected sequence is neither empty nor longer than $4~000$. The sum of $n$ and the total length of corrected sequences both do not exceed $50~000$.
输出解释
For each test case, in the first line output two space-separated integers: minimum number of tokens that will be replaced, $x$, and minimum number of converted annotations, $y$.

In the following $y$ lines, you can output the annotations in any order. $R$ should be omitted as it is the only type that is allowed. The annotations should be non-overlapping, non-empty and follow the exactly same format as input.

Note


For the first test case, $[2, 3]$ is replaced with $1$, $[4, 6]$ is replaced with $2,3$, and the corrected sequence is $1,1,2,3$. The optimal correction with only $R$ is to replace $[2, 6]$ with $1,2,3$.

For the second test case, the corrected sequence is $1,2,4,6,5$. Although $A$ and $D$ cannot be used, if we merge the consecutive annotations, only 4 tokens need to be replaced.

In the third test case, we show that the corrected sequence can be longer than the original sequence, which is $2,1,2,3,4,5,5,6$.
输入样例
3
6 2
1 2 5 3 4 6
R 2 3 1
R 4 6 2 3
6 3
1 2 2 3 4 6
R 3 4 4
D 5 5
A 7 5
6 2
1 2 3 4 5 6
A 1 2
A 6 5
输出样例
5 1
2 6 1 2 3
4 1
3 6 4 6 5
2 2
6 6 5 6
1 1 2 1
来自杭电HDUOJ的附加信息
Recommend IceyWang

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6855

最后修改于 2020-10-25T23:34:57+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/5000MS(Java/Others) 524288/524288K(Java/Others)