博客
归档
友链
关于
博客
归档
友链
关于
P1712 [NOI2016]区间
传送门 考虑把所有线段按照长度排序,在排好序的序列上面跑尺取法,设尺取法维护的区间为[pl,pr][pl,pr][pl,pr],一直移动右端点prprpr,直到现在有一个点在区间[pl,pr][pl,pr][pl,pr]代表的线段上面出现>=m>=m>=m次,停止移动右端点,开始移动左端点,直到没有点在区间[pl,pr][pl,pr][pl,pr]代表的线段上面出现>...
2019-07-31
阅读全文
P4085 [USACO17DEC]Haybale Feast
传送门 考虑尺取法求出所有满足条件的i,ji,ji,j,使∑k=ijFk>=M\sum ^j _{k=i}F_k>=M∑k=ijFk>=M,O(n)O(n)O(n)即可求出。 再考虑如何求max(Si,Si+1,...Sj−1,Sj)\max(S_i,S_{i+1},...S_{j-1},S_j)max(Si,Si+1,...Sj−1,Sj) 用线段树预处理即...
2019-07-25
阅读全文