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


这段时间做了区间DP在此总结下 POJ 1651 Multiplication Puzzle 题意 给出序列$a$,求出最小得分—— 取出的数左边的数右边的数 (不能取两边),实质为矩阵链乘变形,设$d

2017 ICPC Xian Xor树上异或

题意 给出一棵树,$n≤5e4 $, $ \left(q≤5e4 \right)$次询问,每次询问三元组$ \left(u,v,k \right) $,返回从$ u $,到$v$ 上序号$ \left(from \ 0 \

HDU 6023 ping ping ping

Time Limit: 2000⁄1000 MS (Java/Others) Problem The structure of the computer room in Northeastern University is pretty miraculous. There are $ n$ servers, some servers connect to the gateway whose $ IP$ address is $ 0$ directly. All servers are connected with each other by $ n$ netting twines. It is said that this structure is favorable for maintaining physical problem of servers. But because of an unexpected rainstorm, the



在有根树中,两个节点u和v的公共祖先中距离最近的那个成为其最近公共祖先,在树上两点因为存在唯一的最短路,故其LCA为最短路上深度最小的点。通过求解LCA我们可以处理如求解树或DAG上任意两点的最短距离,将RMQ转化为LCA,结合树链剖分操作等。 求解$LCA$的各种方法全部以HDU 2586为例(自娱自乐)