题解：AT_agc073_a [AGC073A] Chords and Checkered

one_last_kiss · 2025-10-17 21:40:01 · 题解

思路

一块黑色区域一定被奇数条弦包含。

首先，只被一条线包含的区域很好算，一条线会贡献一个答案，乘上个数 2^{n-1} 即为 n \times 2^{n-1}。

接着，计算被多条弦包含的情况。直接算并不好算，我们令 i,j 两条弦相交，则 i,j 中间的弦必定两两相交。

暴力枚举是会超时的，我们观察 i 和 j 需要满足：

• i > j + 1
• a_j + k \le a_i

所以可以用双指针求解。最后计算方案，若有 cnt 条弦相交，那么方案为 2^{cnt-1}，其他弦任选，为 2^{n-cnt-2}，整理得 2^{n-3} \times cnt。

两者答案相加即可。