分类标签归档：codeforces
DP 的胜负手在状态定义——状态立住了，转移不过是水到渠成。本合集收录状态定义与递推方向设计类的题目（复杂度优化技巧类见《优化DP》），随训练持续补完。
https://codeforces.com/problemset/problem/2078/D
有 n 对门，每对门分左、右两个通道。初始时左右通道各有 1 个人，且已在通道内的人不能中途切换通道。
通过第 i 对门的某个具体门（左或右）时：
+ a：额外产生 a 个新人，该通道原有人数不变。x a：设该通道操作前有 P...图论一类题的合集，随训练持续补完。用 Python 打 CF，除了算法本身，还得和语言特性过几招——这类实战经验也一并记录在此。
题意：给出无序的边集，它们构成一条链，从端点按序输出这条唯一路径。
思路本身朴素：度为 1 的点是端点，从任一端点 dfs 走到底即可。这题真正的收获是两条 Python 实战经验：
sys.setrecursionlimit(int(2 * 10**5)...数据结构里的高达：拼装麻烦，但拼好之后区间问题基本横着走。本合集收录线段树题目，随训练持续补完。
用 Python 重写的线段树模板。线段树的记忆点在于写代码时脑子里要有那棵树——自顶向下构建，节点 root 的左右孩子是 2*root 和 2*root+1，懒标记在下探时才向下推。
class segment_tree:
def __init__(self, nums):
n = len(nums)
self.nums = nums
self.tree = [0] * 4 ...