almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1063
分析:
不得不说这一年的题目挺好的。
其实这道题我开始想的时候朝各种线性方向去想,结果细节搞的快要崩盘了。。。结果发现题解不是线性的,雪崩。。。
我们知道树链剖分任意两点间的轻边数量在的范围内,既然树链剖分都可以做到,那么我们的最优解肯定在的范围内。由此我们可以想到一种方法。
表示结点的子树中“不便利值”,且与相连的有条重边的方案数。注意这里的不便利值不一定能达到,但是由于答案我们取的是最小值,如果不便利值不一定能达到,那么肯定就在之前就可以得出答案,因此这样是可以的。
方程就贴一个图:


bzoj1062.cpp

 
almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1062
分析:
很显然一条线段经过的时间会回到初始位置,因此可以启发我们把所有的时间都
对于一条线段我们有参数:插入时间,左边界,右边界,以及方向和颜色。因为每一条线段的颜色都不同,所以我们可以忽略颜色这个参数(然而我这个地方数组开小了竟然RE了一次)。
然而这么多条件我们是不好处理的。我们其实只要知道两个值,就是当线段左端点在处的时间以及此时右端点位置,记为
那么这样我们就只有两个变量了,将这两个变量变成坐标,形象化的表示成线段~,就可以尝试在二维平面上弄一些东西了。
考虑一个询问,令,那么询问其实就是将所有的其他线段平移到之后,~这条线段与多少条已知线段相交。这里的平移是指方向平移,因为线段会因时间变化而改变坐标,而变化速度是,所以是
那么我们可以考虑哪些已知线段是满足要求的。
对于每一条已知线段~,假设,那么要满足同理。
画成图的话(没有好的画图软件==,你自己画图可以理解得更好),能在的区域其实是一个不规则的平面区域,那么我们可以把它补全成一个平行四边形(我们用来补全的部分都是不包含点的部分,所以加上了也不会影响答案),问题就变成了询问这样一个平行四边形内有多少个
一个常见的技巧就是对其进行坐标变换,变成一个矩形之后就可以对其使用数据结构查询一个矩形内的和了(我用的二维树状数组),对于那些超界的部分我们要单独考虑。
还有一点要注意的就是当的时候,两边扩展出去的矩形的边界会重合,所以还要特判一下。
总之还是要膜现场大神。
bzoj1062.cpp

 
almost 3 years ago

题目大意:http://www.lydsy.com/JudgeOnline/problem.php?id=1061
分析:
不得不说这是一道网络流建模的好题,看了byvoid的题解后说一下自己的理解。
byvoid的题解:https://www.byvoid.com/blog/noi-2008-employee
---------------------------------分割线-----------------------------------
根据数据范围不难猜出我们建边只能级别, 那么我们对于每一种志愿者,有一个理想的想法就是从服务的起点向终点连一条边。然而我们要满足中间所有的日期都需要受到来自这种志愿者的流,yy一下也可以知道对于每一个相邻日期从连边。那么我们怎么让每一个中间的点由一个单位的流来影响到呢?我们考虑对于相邻的两个点做差就可以了。
---------------------------------以上为口胡内容-----------------------------------
能看懂上面的话那你就是灰常NB= =。(但还是可以看看的。。。)
我们考虑能影响到日期的每种志愿者,设为。令第种志愿者招聘的个数为
那么我们就是要满足第天,天需要的志愿者。
对于相邻两天的两个式子做减法,增加空的第天,那么我们得到了个式子,且每一个都只出现了一个,且出现的位置在第种志愿者的开始时间和结尾时间,一正一负。我们考虑开始时间向结尾时间的节点连一条边,容量,费用为。相对应的,对于连一条容量为,费用为的边。
表示第天需要的志愿者,如果那么从源点向该天连一条容量为,费用为的边,反之连向汇点,然后跑最小费用最大流即可。。。
感觉写的不是很清楚啊。。。你就意识流一下吧。。。
bzoj1061.cpp

 
almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1060
分析:
显然直接贪心计算子树中最大值与全局最大值的差值就好。
然而这题坑爹在数据有问题,所以后三个点打表过去的。。
bzoj1060.cpp

 
almost 3 years ago

题目链接:http://poj.org/problem?id=3694
分析:
我们考虑求出所有的边双,这些边双会构成树的关系,对于每一次操作我们就是插入一条边,假如它们在同一边双中,那么忽略,否则与其构成了一个环,这个环上的点都得删除。这题数据范围小,可以暴力,也可以树链剖分,当然最理想的是并查集路径压缩。
poj3694.cpp

 
almost 3 years ago

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=383
分析:
推荐一个三角剖分的学习网站:http://www.geom.uiuc.edu/~samuelp/del_project.html#goal
我们知道欧几里得最小生成树上的边只可能是三角剖分后的边,所以我们建出三角剖分后直接即可。
时间复杂度
sgu383.cpp

 
almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2961
分析:
直接做肯定是不行的吧,我们考虑分治,按时间分治,然后判断左边对右边的影响。
如何判断这个影响呢?我们首先知道,点在圆内或圆上,当且仅当:

很显然这是一个半平面,如果点在圆内或圆上,那么圆心就必须在这个半平面内。
我们对于分治左边插入的圆维护一个凸包,右边的半平面维护半平面的方向从小到大。
如果一个点在所有的圆内或圆上,那么凸包就在其对应的半平面内,暴力枚举显然是不可行的,那么我们考虑斜率为半平面斜率的直线与凸包的切点,如果这个切点在半平面内,那么凸包就在半平面内,否则就不是。这个我们很显然只需要按方向大小从小到大扫一遍即可。
时间复杂度
bzoj2961.cpp

 
almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4066
分析:
这题很显然强制在线只能用咯,然而我们需要类似替罪羊树的,当左右子树不平衡时暴力重构,不然会(当然也有可能是我的常数太丑了...)
bzoj4066.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1059
分析:
考虑只要我们可以选出个不在同一行,不在同一列的,那么之后我们肯定可以通过交换来使得其全在对角线上,否则肯定无解。
那么我们对于,连一条从的边,做二分图匹配,判断是否有完备匹配即可。
bzoj1059.cpp

 
about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1057
分析:
悬线法的一个应用咯。。。
bzoj1057.cpp