7.1测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------------------
shy的题...被虐傻了
-----------------------------------------------------------------------
T1:
题意说是有n个队伍打了三场比赛,如果一对队伍(x,y),x曾经战胜过y,y曾经战胜过x,那么这个无序二元组就产生1的贡献,问总的贡献
我的nlog^2做法:
只需要用总的二元组数减去这样的二元组数:(x,y),x三场都被y虐了
于是就是一个裸的三位偏序问题了
一维排序,一维分治,一维用数据结构搞一搞,nlog^2
nlog标算:(我下次肯定要卡nlog^2了!--shy)
只需要任意两场比赛算逆序对,然后发现每个答案统计了四次,除以4就行了
-----------------------------------------------------------------------
T2:
题意是一个人要从西向东过河,共有n个河道,每条的流速和宽度不同,这个人一共只有t秒去游泳,给定他的游泳速度,问他最多能离出发点多远.
考虑每一段的路程对时间的偏导k,如果某两段这个值不同的话一定可以把小的的时间续给大的,因此就假设这个值相同,推一下公式发现时间关于k是单调的,因此二分答案k,算一下看时间是否达到或者超过t
我考场上写了个40分乱搞:
每次从t中取eps出来续给拿到这eps秒后增长最快的河段
-----------------------------------------------------------------------
T3:
说是有一棵树上有n个帮派,每个帮派控制了一些节点,然后每次给出一个联盟和一个首都,一个联盟是帮派的集合,他所控制的节点是其中所有帮派控制的节点和这些节点两两路径上的节点,问你离首都最近的被控制节点有多近
首先如果只有一个帮派,那么只需要三种情况讨论一下:
①所有城市都在首都的子树中
②首都被控制
③所有城市不在首都的子树中
求一下首都的子树里面有多少个城市就可以分辨这三种情况
对于第一种情况,首都到所有人的lca的距离就是答案
对于第二种情况,答案是0
对于第三种情况,只需要求出最深的子树中有城市的节点,可以二分答案求出首都dfs序左右两边离他最近的城市,那么要求的节点坑定包含这两个中的一个,倍增验证即可
现在不止一个帮派,那么只需要先每个帮派的答案算一次取个最小值,然后把每个帮派随机取一个点出来同样的做一次
不妨假设首都是根
首先如果有一个帮派分在两个不同的子树中,那答案坑定是0了
如果有两个帮派在不同子树中,那么每个拿一个出来坑定可以发现答案是0
现在考虑所有帮派在同一个子树中,因为是树,两个帮派控制的区域要么包含要么不相交,如果包含,被包含的那个是没有用的,如果是不相交,那么分别任取一个出来的lca一定就是总的lca
"我觉得这道题可以50行写完--shy"
-----------------------------------------------------------------------
评论 (0)
