分类 离散化 下的文章

BZOJ 1818: [Cqoi2010]内部白点

Solution网上的做法大多是扫描线 + 树状数组,我的做法也差不多,只不过写的是线段树(没他们的短)。首先可以证明的是不存在永不终止的情况,所以输出 -1 是没分的(垃圾出题人),进一步考虑下可以发现最多变色一次就会把所有点染完色了,如果我们把两个同一行或同一列的两个点看成一个线段,那么染色的点一定就是行列两条线端的交点。我们只要求线段交点个数就可以了,我们可以用线段树来完成这个问题,遇到横向的边就区间更新 +1,遇到纵向的边就单点查询。看起来有点问题是吧?由于纵向的边是一个线段,我们只能要一定纵坐标范围内的横向边,线段树是无法直接维护这个东西的,所以我们离线所有纵向的- 阅读剩余部分 -

BZOJ 2501: [usaco2010 Oct]Soda Machine

Description有N个人要去膜拜JZ,他们不知道JZ会出现在哪里,因此每个人有一个活动范围,只要JZ出现在这个范围内就能被膜拜, 伟大的JZ当然希望膜拜他的人越多越好,但是JZ不能分身,因此只能选择一个位置出现,他最多可以被多少人膜拜呢, 这个简单的问题JZ当然交给你了InputLine 1: A single integer: NLines 2..N+1: Line i+1 contains two space-separated integers: A_i and B_iOutputLine 1: A single integer representing the- 阅读剩余部分 -