hit oj 2687 Candy (线段树动态维护最大连续子段)

题目链接

题意:给出n个数,m个修改,每次修改后询问整个区间的最大连续子段。

思路:考虑一段区间,分成左右两个子区间,这段区间的最大子段有三种情况:只在左区间中,只在右区间中,既在左区间中又在右区间中。前两种很好维护,对于后一种,我们新增加线段树的两个域,mxl,mxr,分别表示一个区间[……]

Read more

codeforces #327 A. Flipping Game

http://codeforces.com/contest/327/problem/A
题意:给定一段序列,只由0,1组成。要求选一段非空区间,做翻转操作(0变1,1变0),问变完之后1最多能有多少。
思路:最后的1个个数=初始的1的个数+变换区间的0的个数-变换区间的1的个数。初始的是常数。那[……]

Read more