#P10796. 『SpOI - R1』我看到了,谢谢你们
『SpOI - R1』我看到了,谢谢你们
题目描述
本题包含多组测试。
特别注意:本题中,border 的定义有所不同。对于串 ,若同时存在 的一对前缀后缀(可空也可为 本身)等于 ,则 是 的 border。
有一个长度为 的字符串 。我们使用这个串上的信息来选举总统。
令 表示 的 长前缀,特别地, 表示包含第 位的空前缀。现在有 位候选人站在这 个前缀上,编号为 ,编号为 的人对应前缀 。每个人有一个票数 和花费 。
得票数量严格超过总票数一半的人可以当选总统。
每一个时刻,任何一个未被控制且之前一直在等待的人 都可以做出三种选择之一:
- 进行一次对 投票操作:将自己的 票花费 的代价投给人 。
- 进行一次对 揽票操作:
- 花费 选中人 ,需要满足 是 的一个 border。
- ,若 是 的一个 border,且 在此时刻未被控制,则 下一时刻变为被控制,他的 票都花费 投给 。
- 等待下一个时刻。
每个候选人都希望其他人不会成为总统,且都是绝顶聪明的。特别地,当他们的操作出现了交叉导致一个人的票需要投给多人时,被交叉者的票可以分别独立投出并都有效(你可以理解为他的票分裂了)。因此,总统可能有多个。
你可以干涉这个过程。具体来说,你可以在 时刻操作一个候选人 ,让 进行指定的一种选择,并钦定选择涉及的所有变量。 此后不能再做任何选择,剩下的人必须从 时刻再开始选择。你干涉的代价就是 这次选择的总花费。
票数 和花费 都会发生 次变化。
每一次变化会改变票数 中的某一项或是花费 中的某一项。票数 可能会变为任意正整数,花费 只会变小或者不变。
在每次变化之后,你都需要找到这样一个人 ,满足你有一种干涉他的方案使得他一定可以成为总统,且你干涉的代价最小。你只需要输出这个最小代价。
可以证明一定存在这样的人。
本题强制在线。
输入格式
第一行一个整数 ,表示数据组数。
对于每组数据:
一行三个整数 ,表示字符串长度、修改次数、是否强制在线。
接下来一行一个长度为 的字符串 。保证 中只含有小写英文字母。
接下来 行,每行两个整数 ,依次表示候选人 到 的初始票数和花费。
接下来 行,每行三个整数 。设 表示上一次输出的答案的绝对值,则 $o\gets o'\oplus(type\times lst),p\gets p\oplus(type\times lst),x\gets (|x'|\oplus(type\times lst))\times (-1)^{[x'\leq 0]}$(其中 为艾佛森括号),然后:
- 时,将 修改为 。
- 时,将 修改为 。保证 。
输出格式
共 行。
第一行输出在初始状态下你干涉的最小代价。
之后,在每次修改后输出你此时干涉的最小代价,共 行。
3
2 1 0
aa
6 1
2 -1
3 2
1 0 2
19 0 0
happythbirthdayshun
1000000000 8
1000000000 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 1
1 0
1 0
5 6 1
acbac
1 3
2 4
1 -5
3 6
2 -3
3 1
11 10 12
9 13 108
8 12 8
10 9 0
6 1 4
4 7 1
1
0
17
9
8
-9
8
-4
-5
-5
提示
样例 #1 解释
对于第一组数据:
考虑第一次修改之前。全场共有 票,则当选总统需要 票。
干涉 号候选人,且选择第一种选择,使用 的花费进行一次对 投票操作后, 号候选人得到 票,直接达到了总统要求,可以证明这是花费最小的答案。
第一次修改后,全场共有 票,则当选总统需要 票。
干涉 号候选人,且选择第二种选择,进行一次对 揽票操作后, 号候选人将得到 票,总花费为 。他直接达到了总统要求,可以证明这是花费最小的答案。
对于第三组数据,去掉强制在线后的修改操作为:
- ;
- ;
- ;
- ;
- ;
- 。
数据范围
请注意常数因子对程序效率的影响。
本题开启子任务捆绑与子任务依赖。
对于 的数据,,,,,且在任何时候都保证 ,。
保证字符串中只含有小写字母。
对于任意一次修改,保证 为 或 ,且 。在 时,; 时,。
特别地, 中的每一项在被操作的过程中一定单调不递增。
Subtask | 特殊性质 | 得分 | 子任务依赖 | |||
---|---|---|---|---|---|---|
1 | 无 | 无 | ||||
2 | 1 | |||||
3 | 无 | |||||
4 | ||||||
5 | ||||||
6 | ||||||
7 | 无 | 1,2,3,4,5,6 |
特殊性质 :保证 。
特殊性质 :保证字符串中的每一个字符都在 个小写字母中独立均匀随机。
特殊性质 :字符串中只含有 。
特殊性质 :保证 。