#P18752. [2027年国家集训队互测] Wealth Across Three Lifetimes
[2027年国家集训队互测] Wealth Across Three Lifetimes
Wealth Across Three Lifetimes
题目背景
“好孩子,假如给你三生三世的财富,学否?”
今天,玛德琳和坏德琳来到了一个梦幻的机器面前。机器里面有四种颜色的球,各有各的用处。蓝色弹球是最基础的弹球,你弹上去会获得一次冲刺能力。粉色弹球是加强版,你弹上去会获得两次冲刺。白色弹球弹上去不能获得冲刺。黄色弹球弹了一次之后会长出刺,并且以后你不能在接触它。
这里面的关卡可以通过一个颜色序列来描述。玛德琳和坏德琳在里面玩了很久,但还没通过第一关。于是玛德琳急哭了!她决定通过修改器作弊!这个修改器很特别,只能修改白弹球和黄弹球,且只能修改成蓝弹球和粉弹球,而且每一次被修改的弹球位置是确定的。而坏德琳得知了此事,她决定阻止玛德琳作弊,所以黑了这个修改器,获得了修改黄弹球颜色的权限。同时,玛德琳认为,一连串相同的弹球会让关卡变得简单。她认为一个关卡的简单度是同色段长度的最大值。玛德琳想要最大化这个值,而坏德琳想要最小化这个值。
题目描述
Alice 和 Bob 在一个长度为 的序列上博弈。序列中每个元素的值只能是 或 ,且每个元素的取值时刻在游戏开始前就已确定。
给定长度为 的序列 和 ,其中 是 的一个排列,。
序列的第 个元素会在第 个时刻确定取值,规则如下:
-
若 ,则该元素被赋值为 ;
-
若 ,则该元素被赋值为 ;
-
若 ,则该元素的值由 Alice 在该时刻决定;
-
若 ,则该元素的值由 Bob 在该时刻决定。
游戏开始前,Alice 和 Bob 都知道序列 和序列 。游戏共进行 个时刻,第 个时刻确定的是满足 的那个位置 的取值; 个时刻结束后,序列的每个元素都恰好被确定了一次取值。
同色连续段被定义为一个二元组 满足 ,且第 个元素到第 个元素的值全部相同;若它不能再向左右延伸(即 或第 个元素与它们不同,且 或第 个元素与它们不同),则称它是一个极长同色连续段。 的长度为 。
Alice 希望最大化第 个时刻后序列所有极长同色连续段长度的最大值,Bob 希望最小化该值。
给定正整数 。
如果 ,双方都会按最优策略行动,请求出最终序列极长同色连续段长度的最大值。可以证明答案是确定的。
如果 ,额外给出长度为 的序列 。,表示博弈的第 个时刻发生的决策为:令 为唯一满足 的 中的正整数,将序列的第 个元素赋值为 (可能发生宇宙射线击中了第 个位置导致 且 的情况)。请求出对于 ,如果第 个时刻及之前都按照 序列的决策博弈,第 个时刻结束后双方都按最优策略行动,最终序列中最长同色连续段的长度 。
输入格式
本题强制在线
第一行包含一个正整数 ,表示数据组数。
接下来一共 组数据,在每组数据中:
第一行包含两个正整数 和 。
第二行包含 个整数 。
第三行包含 个整数 。
如果 ,第四行包含 个整数 。
真正的 为 与 按位异或后模 的结果。
输出格式
对于每一组数据:
如果 输出一行一个整数,表示双方都按最优策略行动时,最终序列中最长同色连续段的长度。
如果 输出一行 个整数,表示对于 ,如果第 个时刻及之前都按照 序列的决策博弈,第 个时刻结束后双方都按最优策略行动,最终序列中最长同色连续段的长度。
样例
样例输入 #1
1
3 1
3 1 2
-1 -2 -1
样例输出 #1
3
样例解释 #1
表示 :第 个元素在第 个时刻确定,第 个元素在第 个时刻确定,第 个元素在第 个时刻确定。于是时刻顺序为:
-
时刻 :确定第 个元素(,由 Bob 决定);
-
时刻 :确定第 个元素(,由 Alice 决定);
-
时刻 :确定第 个元素(,由 Alice 决定)。
Alice 想要最长同色段尽可能长,Bob 想要尽可能短。Bob 虽然先手,但只掌控正中间的第 个元素;Alice 掌控第 、 两个端点元素。
Bob 把第 个元素定为 后,Alice 可以把第 、 个元素也都定为 ,最终序列为 0 0 0,最长同色段长度为 ;Bob 若把第 个元素定为 ,Alice 同样都取 ,最终序列为 1 1 1,最长同色段长度仍为 。
Bob 的两种选法导致的结果完全相同,他无法把答案压到 以下;而 Alice 也至多让整个序列同色,故答案为 。
样例输入 #2
1
2 1
2 1
-1 -1
样例输出 #2
2
样例解释 #2
表示 :第 个元素在第 个时刻确定,第 个元素在第 个时刻确定。两个元素的 值都是 ,故都由 Alice 决定:
-
时刻 :确定第 个元素(,由 Alice 决定);
-
时刻 :确定第 个元素(,由 Alice 决定)。
Alice 想要最大化最长同色段。两个元素都由她决定,她只要给两者赋相同的值,就得到 0 0 或 1 1,此时 是长度为 的极长同色连续段;而序列总长度只有 ,故这也是她能取得的最好结果。
样例输入 #3
3
2 1
1 2
-1 -2
4 2
1 3 2 4
-1 0 -2 -1
1 0 0 1
3 1
3 1 2
0 0 1
样例输出 #3
1
2 2 3 2 2
2
数据范围
本题开启合理的子任务依赖。
对于所有数据,保证:
-
, , , 。
-
是 的一个排列。
-
。
-
。
| 子任务编号 | 特殊性质 | 分值 | ||||
|---|---|---|---|---|---|---|
| A | ||||||
| 无 | ||||||
| B | ||||||
| 无 | ||||||
特殊性质 A: 保证 。
特殊性质 B: 保证 和 在长度为 且符合限制的序列中随机生成。
注意:子任务 被子任务 依赖。
