60pts离谱思路
查看原帖
60pts离谱思路
1037637
Akabane_Karuma楼主2024/10/26 21:34

赛时想到的离谱 6060 分做法:

O(mn)O(mn) 求检测到第 ii 辆车通过第 jj 个测速仪时是否超速;

然后得到这样一串东西:

000110
011100
111000
001110
111110
000000

删除带有包含关系的区间以及全 00 行和全 00 列,并按左端点排序:

00011
01110
11100

右转 9090 度:

100
110
110
011
001

然后就成了一个线段覆盖问题

所以这个思路怎么优化成 O(nlogn)O(nlogn)

2024/10/26 21:34
加载中...