社区讨论

翻译

魔魔塔哈奇
AT_arc087_c[ARC087E] Prefix-free Game参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6tkiw7
此快照首次捕获于
2025/11/20 10:35
4 个月前
此快照最后确认于
2025/11/20 10:35
4 个月前
查看原帖
对于两个字符串 s,ts, t , 如果 ss 不是 tt 的前缀且 tt 不是 ss 的前缀，则称他们是 prefix-free 的。
给定一个正整数 LL，如果一个字符串集合 SS 符合下列条件，则我们称他为 good string set：
  • SS 中的每个字符串的长度都在 11 和 LL 之间（包括），并且之包含字符 ′0′'0' 和 ′1′'1'
  • SS 中的每两个的字符串都是 prefix-free 的
我们有一个 good string set S=s1,s2...,snS = {s_1, s_2 ... , s_n}，Alice 和 Bob 在玩一个游戏，他们轮流做下列操作：
  • 向 SS 中添加一个新字符串，并使 SS 仍是 good string set
无法进行这个操作的人输掉游戏。假设二人都按最优策略进行游戏，求谁会赢。

数据范围

1≤N≤1051 \leq N \leq 10^5
1≤L≤10181 \leq L \leq 10^{18}
s1,s2,...,sns_1, s_2, ..., s_n 是不同的
s1,s2,...,sn{s_1, s_2, ..., s_n} 是 good string set
∣s1∣+∣s2∣+...+∣sn∣≤105|s_1| + |s_2| + ... + |s_n| \leq 10^5

回复

共 2 条回复，欢迎继续交流。

正在加载回复...