标签 二分答案 下的文章
- 首页
- 二分答案
「Codeforces 1156C」Match Points
题目链接：Codeforces 1156C
在一条数轴上有 $n$ 个点 $x_1, x_2, \dots, x_n$，两个点 $i, j$ 可以匹配当且仅当两者都满足：
- 两个点 $i, j$ 都没有和别的点匹配。
- $\lvert x_i - x_j \rvert \ge z$。
请求出最多可以匹配多少对点。
数据范围：$2 \le n \le 2 \times 10 ^ 5$，$1 \le x_i, z \le 10 ^ 9$
「CTSC 2012」熟悉的文章
题目链接：Luogu 4022
阿米巴是小强的好朋友。
在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。
为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得眼熟，小强想出了一个评定作文「熟悉程度」的量化指标：$L_0$。小强首先将作文转化成一个 $01$ 串。之后，小强搜集了各路名家的文章，同样分别转化成 $01$ 串后，整理出一个包含了 $m$ 个 $01$ 串的标准作文库。
小强认为：如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过（即它是标准作文库 的某个串的一个连续子串），那么它是「熟悉」的。对于一篇作文 $A$，如果能够把 $A$ 分割成若干段子串，其中「熟悉」的子串的长度总和不少于 $A$ 总长度的 $90\%$，那么称 $A$ 是「熟悉的文章」。$L_0$ 是能够让 $A$ 成为「熟悉的文章」的所有 $L$ 的最大值。如果不存在这样的 $L$，那么规定 $L_0 = 0$。
现在小强有 $n$ 篇作文需要进行判断，请你分别求出他们的 $L_0$ 值。
数据范围：输入文件的长度不超过 $1.1 \times 10 ^ 6$ 字节。
「SPOJ 220」Relevant Phrases of Annihilation
题目链接：SPOJ 220
你是 Byteland 的国王，你的特工刚刚截获了 $n$ 条敌方的加密信息 $s_i$。你请来的密码学家声称他只能解密文本中最重要的部分，这个文字片段在所有信息中至少出现 $2$ 次且不相交。你需要求出这个文字片段的最长长度。
本题有 $T$ 组数据。
数据范围：$1 \le T \le 10$，$1 \le n \le 10$，$2 \le \lvert s_i \rvert \le 10 ^ 4$。
「POJ 3261」Milk Patterns
题目链接：POJ 3261
农夫 John 发现他的奶牛的产奶量每天都在变化。经过进一步调查，他发现：虽然他不能预知未来的产奶量，但是每天的产奶量有一些规律。
为了进行更严格的研究，他发明了一种复杂的分类方案。他记录下了 $n$ 天内的产奶数据，第 $i$ 个产奶量样本被记录为 $a_i$。他希望找到最长的样本模式，其重复次数至少为 $k$ 次，模式之间可以重叠。
数据范围：$1 \le n \le 2 \times 10 ^ 4$，$0 \le a_i \le 10 ^ 6$，$2 \le k \le n$。
「POJ 1743」Musical Theme
题目链接：POJ 1743
我们用长度为 $n$ 的音符序列 $a_i$ 表示一段音乐旋律，我们定义一个子串是这段音乐的主题，当其满足如下条件：
- 长度至少为 $5$。
- 经过转化后的子串在这段音乐中的其他位置出现过。所谓转化，就是给这个子串的每个元素加上同一个整数。
- 与重复出现的另一个子串不相交。
求出这段音乐中主题的最长长度。如果没有主题，那么输出 $0$。
数据范围：$1 \le n \le 2 \times 10 ^ 4$，$1 \le a_i \le 88$。