| 题目名称 | 1728. [Vocaloid]双子的混唱 |
|---|---|
| 输入输出 | rinlen.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 6 |
| 题目来源 |
 水中音
于2014-10-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：4， 通过率：75% | ||||
 天一阁 |
100 | 0.003 s | 0.72 MiB | C++ |
 水中音 |
100 | 0.008 s | 0.39 MiB | C++ |
|
水中音 |
100 | 0.008 s | 0.41 MiB | C++ |
|
天一阁 |
0 | 0.462 s | 0.72 MiB | C++ |
| 关于 双子的混唱 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
回复 @cstdio :
数据修复 水中音
2014-10-12 13:51
7楼
| ||||
|
现在这题的数据还有问题吗？
 cstdio
2014-10-12 07:55
6楼
| ||||
|
注意点：
1.h[i]以后是指的不包括s[h[i]]的之后取的字串。 2.数据小了一点，不过没关系。 kmp+搜索+贪心 天一阁
2014-10-10 21:14
5楼
| ||||
  乌龙猹
2014-10-10 20:39
4楼
| ||||
|
在下诚心诚意，服务双子大人不含糊
天一阁
2014-10-10 20:30
3楼
| ||||
|
问什么要改输入输出文件名
 天一阁
2014-10-10 20:28
2楼
| ||||
|
丧(gan)心(de)病(piao)狂(liang)
 mikumikumi
2014-10-10 20:23
1楼
| ||||
【题目描述】
在即将到来的跨年祭前夕，镜音铃和镜音连仍在准备着明天的演唱任务，他们被大姐“失误什么的…都是不可原谅的呢~”的由于不可抗力因素导致无法违背的话命令:
要在跨年祭上在观众们要求的n首歌中选取k首进行演唱，并要求在时间不超过t的前提下带给观众的hi度达到m。
但让他们发愁的是，铃和连熟悉的音频范围不同，所以他们对每首歌都有自己的演唱方式，因此很难达到同步，这将在很大程度上降低每首歌的hi度，为达到更好的效果，铃和连同意两人开始演唱的时间可以不同，但同步部分必须是镜音铃的歌曲高潮部分起始点（连是有多可怜…），双子希望能在第i首歌从h[i]处(从0编号)进入高潮部分后，同步时间尽量长，使达到的hi度 i*x (i表示演唱曲目的序号)的总和尽量大。
【输入格式】
第一行三个整型：n,m,t;
以下n组，每组代表一首曲目，
第一行为当前歌曲i的高潮部分起始位置h[i]和歌曲时间l[i];
以下为两个长度l[i]字符串，都以\n结束，代表铃和连风格的歌。
【输出格式】
假如无法达到要求，输出QwQ。
否则第一行输出k和所能达到的最大hi度;
第二行输出歌曲的演唱顺序;
（假设情况不唯一，输出字典序最小）
【样例输入】
2 10 30
5 12
ccbaacbaccba
abbcaaacbacc
7 15
bbbbbcccccccccc
aaaaabbbbbccccc
【样例输出】
2 15
1 2
【提示】
（样例解释：曲目1从高潮部分起的最长重叠部分cbacc长度为5;曲目2从高潮部分起的最长重叠部分ccccc长度为5，最大hi度为5*1+5*2=15）
1<=n<=10;
1<=t<=20000;
1<=m<=50000;
单首曲目最长长度为17000;
【来源】
AiKy