11.19 模拟赛

题目质量点赞！好题！

storm

普及组模拟题

god

有趣的 dp 题

key：考察相对位置设计状态

\(f(i,j)\) 表示考虑后 \(i\) 个操作，经过了相对坐标为 \(j\) 的点的概率。

转移中，如果这一步不动，相对坐标不变；否则，相对坐标整体平移。

答案就是 \(f(n,j)\)。

fate

瞎搞贪心题

显然从左到右依次考虑能否放左括号，关键在于判定“同组”的是否合法。

场上用线段树维护后缀和，按照括号匹配的一般思路，要求后缀和最大值不大于 0。

常数较大，卡了一会才过。

题解是一个结论：

合法括号匹配的左括号序列被 \(1,3,5,\dots,2n-1\) 偏序

故考虑给每个左括号匹配一个值，set 维护当前还未匹配的值，每次查询能否匹配即可。

rectangle

容斥 + 扫描线 码力题

将每个矩形看作一个点，有交的矩形之间连边，问题转化为求有多少个 \((i,j,k)\) 的生成子图没有边。

考虑容斥，用所有三元组的数量减去有边的三元组的数量。记有 1 条边的个数为 \(c_1\)，2 条边的个数为 \(c_2\)，3 条边的个数为 \(c_3\)，答案为 \({n \choose 3} - c_1 -c_2 -c_3\)。

step1：用度数 \(d_i\) 求出 \(c_1+c_2\)

• 至少有一条边时（选一个点 i，再选一个与 i 相连的点 j，再随便选一个点 k）：\(\sum d_i(n-2)=2c_1+4c_2+6c_3\)
• 至少有两条边时（选一个点 i，再选两个与 i 相连的点 j,k ）：\(\sum {d_i \choose 2} =c_2+3c_3\)

step2：扫描线求出 \(d_i\)

考虑正常的从左往右扫，此时可以保证横向全都有交，只需考虑纵向。

(a,b) 纵向有交 当且仅当 \(yl_b\le yr_a\) 且 \(yr_b \ge yl_a\)（已知两两不同）

故用 \(\le yr_a\) 的 \(yl\) 数量减去 $< yl_a $ 的 \(yr\) 数量，最后再减掉自己即可。

step3：容斥求出 \(c_3\)

考虑在 \(xl\) 最大的位置统计三元组，不妨为 \(i\)。

从与 \(i\) 有交的点中选 \(j,k\)，再减去 \(j,k\) 不交的情况。

发现此时 \(xl_j\le xl_i\le xr_j\) 且 \(xl_k\le xl_i\le xr_k\)，即 \(j,k\) 横向必有交，故只需考虑纵向。

不妨令 \(yr_j<yl_k\)，则必有 \(yl_i\le yr_j<yl_k\le yr_i\)，可以用线段树维护。

附：线段树维护信息
\((a,b,c)\) 表示区间内有 \(a\) 个 \(yr\)，\(b\) 个 \(yl\)，\(c\) 对 \(yr<yl\)
合并时 \(a,b\) 直接相加，\(c\) 要加上左边的 \(a\) 乘右边的 \(b\)