「POJ 3693」Maximum Repetition Substring
题目链接:POJ 3693
我们定义一个字符串的重复数为最大的数字 $R$ 满足这个字符串可以被分割为 $R$ 个相同的连续子字符串。
给定一个长度为 $n$ 的字符串,你需要找到它的重复数最大的子串。如果有多个答案,输出字典序最小的子串。
数据范围:$1 \le n \le 10 ^ 5$。
题目链接:POJ 3693
我们定义一个字符串的重复数为最大的数字 $R$ 满足这个字符串可以被分割为 $R$ 个相同的连续子字符串。
给定一个长度为 $n$ 的字符串,你需要找到它的重复数最大的子串。如果有多个答案,输出字典序最小的子串。
数据范围:$1 \le n \le 10 ^ 5$。
题目链接:Codeforces 1143E
最近 Lynyrd 和 Skynyrd 来到超市购物,Lynyrd 购买了一个长度为 $n$ 的排列 $p$,Skynyrd 购买了一个长度为 $m$ 的包含 $1$ 到 $n$ 的数组 $a$。
他们给你了 $q$ 个询问,每个询问均为如下形式:“在数组 $a$ 的第 $l$ 到 $r$ 个位置之间,是否存在一个子序列满足它是 $p$ 的一个循环位移?”
对于每个询问,如果存在这样的子序列则输出 $1$ 否则输出 $0$。
数据范围:$1\le n, m, q\le 2\times 10 ^ 5$。
题目链接:LOJ 2074
JSOI 的国境线上有 $N$ 座连续的山峰,其中第 $i$ 座的高度是 $h_i$。为了简单起见,我们认为这 $n$ 座山峰排成了连续一条直线。
如果在第 $i$ 座山峰上建立一座高度为 $p(p \ge 0)$ 的灯塔,JYY 发现,这座灯塔能够照亮第 $j$ 座山峰,当且仅当满足如下不等式:
$$ h_j \le h_i + p - \sqrt{\vert i − j\vert} $$
JSOI国王希望对于每一座山峰,JYY 都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度。你能帮助 JYY 么?
数据范围:$1< n\le 10 ^ 5$,$0< h_i \le 10 ^ 9$。