logo AlgoBeat OnlineJudge
登录 注册

#215078. [USACO26JAN1] COW Splits B

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给定 Bessie 一个正整数 和一个长度为 的字符串 ,该字符串是由 个长度为 的字符串拼接而成,每个字符串都是 的一个循环移位。换句话说,每个字符串将是 中的一个。

字符串 是一个平方串,当且仅当存在一个字符串 使得 ,其中 表示字符串拼接。例如, 是平方串的例子,但 不是。

在一次操作中,Bessie 可以从 中移除任意一个子序列 ,其中 是一个平方串。一个字符串的子序列是指通过从原字符串中删除若干(可以是零个)字符而得到的字符串。

你的任务是帮助 Bessie 判断是否可能将 转化为空字符串。此外,如果可能,你必须提供一种实现方法。

Bessie 还会收到一个参数 ,其值为 。设 为你构造方案中的操作次数。

  • 如果 ,则 必须等于可能的最小操作次数。
  • 如果 ,则 最多可以比可能的最小操作次数多

输入格式

第一行包含 ,表示独立测试用例的数量(),以及 )。

每个测试用例的第一行有 )。

每个测试用例的第二行有

所有测试用例的 之和不超过

输出格式

对于每个测试用例,按照以下流程输出一行或两行。如果不可能将 转化为空字符串,则在一行中输出

否则,在第一行输出 ——你构造方案中的操作次数。在第二行,输出 个由空格分隔的整数。第 个整数 表示 的第 个字母是在第 次操作中被删除的()。

样例

样例输入 1

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

样例输出 1

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1

样例输入 2

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

样例输出 2

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2

数据范围与提示

对于最后一个测试用例,最优的操作次数是 ,因此任何 的有效构造方案都会被接受。

对于 ,这里是一种可能的构造方案:

  1. 在第一次操作中,移除最后 个字符。现在剩下
  2. 在第二次操作中,移除子序列 WW。现在剩下
  3. 在最后一次操作中,移除所有剩余字符。

  • 输入 -
  • 输入 -
  • 输入 -

翻译由 DeepSeek V3 完成