| rank | solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 79 | 8 | O | Ø | O | . | Ø | O | . | Ø | Ø | O |
A
Solved by Henry and XLor.
二分答案。
用 ST 表，类似于笛卡尔树一样分治，判断是否等价。
B
UpSolved by XLor.
求 ∫∞0Πni=11a2i+x2dx。
乘积式不容易积分，展开成和式分别积分。
C
Solved by Forsaken.
好像乱搞水过去了？
E
UpSolved by Forsaken.
F
Solved by Forsaken.
随机撒点，发现期望比上面积的两倍，约等于 11，感受一下很对。
H
UpSolved by Forsaken and XLor.
由期望的线性性，转换为求每个元素在多少个集合内。
求出线性基，线性基的秩为 r。
对于不在线性基中的每个元素，余下不在基中的元素可以任意取，并且对应线性基中的唯一一种组合方式。
对于线性基中的元素，如果他是一个唯一的基，则无法取出元素异或出来为 0，否则参照上面计算贡献即可。
I
UpSolved by XLor.
给定 n 个二维平面上的点，每个点有权值 ai 和 bi。
将点集划分为两个集合，满足任意 A 集合的点 i 和 B 集合点 j，要么 xi<xj，要么 yi>yj。
A 集合的点使用权值 ai，B 集合的点使用权值 bi，要求最大化权值和。
题目即是用一个阶梯型的分段函数将点集划分为两块，A 集合在左上，B 集合在右下，边界上的点属于 B 集合。
线段树维护分界线纵坐标为 i 时的最大权值和 f(i)。
从左至右扫描线，对于一个点 i，如果他作为分界线的转折点，则需要从前面 max 这条分界线转移过来，注意纵坐标由上至下排序。
对于高度大于 y_i 的分界线端点，他一定会取到点 i，即区间加上权值 b_i。
对于高度小于 y_i 的分界线端点，他一定不会取到点 i，即区间权值加上 a_i。
J
Solved by XLor.
int128 水过去了。