A
萌萌题,但是看错题。
代码
B
典典题。
二分平均值 x x x。统计均值小于 x x x 的方案数,每个数减去 x x x 后即统计多少个区间和 < 0 <0 <0。容易发现是个二维偏序问题,归并排序统计即可。
代码
C
典典题。
n
≤
1500
n \le 1500
n≤1500,
O
(
n
3
)
O(n^3)
O(n3) 可以用 bitset
优化。
记
S
S
S 为
u
,
v
u,v
u,v 均能到达的点集,答案为:
∑
(
u
,
v
)
∈
E
(
deg
(
u
)
−
1
)
×
(
deg
(
v
)
−
1
)
−
∣
S
∣
\sum_{(u,v)\in E} (\deg (u) - 1) \times (\deg(v) - 1)-|S|
(u,v)∈E∑(deg(u)−1)×(deg(v)−1)−∣S∣
代码
D
难难题。
O ( n 2 + n + m ) O(n^2+n+m) O(n2+n+m):暴力建边 bfs 即可。
总结
预估 100 + 100 + 100 + 40 100+100+100+40 100+100+100+40,实际 10 + 40 + 100 + 20 10+40+100+20 10+40+100+20。A 题目看错,提交期间重新交了一发。B 用 BIT 多次离散化会比归并多点常数,被卡到了 40 40 40。C 没啥好说的。D 暂无评价。