尺取

尺取法小结

尺取法顾名思义是用尺子一段一段测量。测量物件长度通常是一端对其,看另一端的刻度得出答案; 借挑战上的话 尺取法通常是数组保存一对下标,即所选取的区间的左右端点,然后根据实际问题不断推进区间,在这其中可以根据已有经验保持右端点从上一状态继续推进。 (更多…)

luoyayu
字符串

Atcoder 88 D-Wide Flip

Time limit : 2sec / Memory limit : 256MB You are given a string $S$ consisting of 0 and 1. Find the maximum integer $K$ not greater than $|S|$ such that we can turn all the characters of $S$ into 0 by repeating the following operation some number of times. Choose a contiguous segment $[l,r]$ in $S$ whose length is at least $K$ (that is,$r-l+1\geq K$ must be satisfied). For each integer $i$ such that $l\leq i\leq r$, do the following: if $S_i$ is 0, replace it with 1; if $S_i$ is 1, replace it with 0. (更多…)

luoyayu