arc156e专题

【学习笔记】[ARC156E] Non-Adjacent Matching

首先,记 S = ∑ X i S=\sum X_i S=∑Xi​,那么恰好有 S 2 \frac{S}{2} 2S​条边( S S S为偶数);序列 { X i } \{X_i\} {Xi​}合法的充要条件是: 对于任意 i i i,满足 X i + X i + 1 ≤ S 2 X_i+X_{i+1}\le \frac{S}{2} Xi​+Xi+1​≤2S​ 这种东西 Kidulthood 就