题目链接
T1
这题实际上并不难(我就是没打出来),只不过需要能够发现其中的奥妙就可以了。
我拿到这题时首先想的是状压DP,然后自己瞎打一通
1 | for (Re S=1; S<(1<<K); ++S) |
嗯。。。打了这么一个东西,后来发现这是错的。。。
并不能说我没想过正解的做法,只不过是被我迅速否定了。
接下来讲讲正解:
实际上我们很容易注意到K≤5这个条件,肯定就是在这上面做文章(傻*才想状压)。
所以我们可以考虑先做K遍的SPFA预处理出K个超市到各个地方的距离。
预处理后又有什么用呢?
我们考虑任意一个起点u(u不是超市),对于u来说,肯定是走到这K个超市中的某一个,然后走到其他几个超市(可能经过自己),最后再从某个超市回来。
所以呢,我们可以考虑再预处理一个数组f[i][j],表示走完这K超市,起点为第i个超市,终点为第j个超市的最短路径(可能经过我们的u)。
这样我们可以通过dfs预处理出f数组。
那么统计答案的时候我们只需要枚举个这K个超市中的起点和终点就可以了。
统计答案:ans=min(ans,dis[p][i]+dis[q][i]+f[p][q])
到此,这题就被我们暴力过掉了。
1 |
|
T2
这道题官方题解的做法是倍增,实际上有更好的做法。
先看一下官方题解吧
对于20%的数据可以每次询问扫一次所有边,用并查集判断是否还是一棵树。
对于另外20%的数据,需要观察出一个性质:如果新加入的那条边的两个端点在原树上
面的路径包含删去的边,那么增删边之后还是一棵树,否则就不是。由于这部分数据树为随
机生成,所以期望树高是logn级别的,因此可以直接每次往上跳判断经过的边。(也许还能
有别的水法?)
对于100%的数据,我们继续沿用刚才的算法,由于树高可能相当大,我们可以先遍历
一次原树,确定每个点在原树的深度,然后每次询问用倍增算法找到询问加入的边的两个端
点往上跳到的删去的边所在深度,再判断一下是不是删去的那条边就可以了。
感觉就非常麻烦。而所谓更简便的做法就是利用树的dfs序做文章。
我们考虑断边的操作,它的实质就是把我们一棵完整的树拆成了一棵小子树(不含根节点)和一大团的东西(含根节点)。
再考虑一下连边的操作,如果我们能够证明出连边的两点分别在这两坨东西里面,我们就会发现CD没有得逞。
那么怎么证明呢。
在考场的时候,我用的是并查集(果然蒟蒻就是只会暴力)
实际上用树的dfs序可以很好地进行判断。(至于树的遍历、dfs序是什么不在本题解范围内,请自行了解)
我们记录每个结点变灰的时间G[i],每个节点变黑的时间B[i],然后判断连边的两点是否是一点在小子树中,一点不在小子树中。时间复杂度为O(N+Q)的。(跑的飞快啊)
1 |
|
T3
这题其实并不难,代码量也不大。但是思路比较难想。
很多人可能都会想树状数组、线段树能不能做(包括我这个蒟蒻)。
其实这题完全不用,用倍增就好了。
我们设f[i][j]为在i位置时,向后选2j条线段所能达到的最小右端点(Ri)
初始时,f[i][0]为以i为左端点(Li)的所有线段中取一个右端点最小的。(贪心法可证)
但我们在求解f[i][j]时要注意,由于线段不能重叠,所以说我们必须这样递推f[i][j]=f[f[i][j−1]+1][j]
就是在跳小步的时候要+1。
然后还有在i比较大时,可能在i位置时,后面都没有线段,所以要特判掉。
1 |
|