17.3.18 考试小记 && UOJ Round #17

发布于 2018-03-19  2.7k 次阅读


17.3.18

T1

给出一张有向图,从上面选出一些边,使得任意一条1~n的路径上有且仅有一条边被选择且被选择的边权值和最小。

考场上打了个n^2条边的网络流,因为数据范围比较小所以过了,讲一下大致的思路以及优化的方法。

首先,对于两点在同一SCC内的边,一定是非法的。因为如果选中这条边,那么一定存在经过这条边多次的路径。那么,我们只要Tarjan跑一遍看看1、n是否在同一SCC内即可判断解的存在性。

接着,我们考虑使用最小割来解决问题。我的n^2条边的建图方法非常naive,就是和“切糕”那题的思路差不多,首先找出能到达这个点u且能到达n的所有前驱节点v,连边(u,v,inf)。这样,就保证了如果割的边在这条边“以下”那么它上面的边一定不会割掉。优化的话也很简单,因为多连的边没啥用,只要像串糖葫芦一样连向第一个前驱即可,也就是正解的思路。

这回我的代码真的是又丑又长又慢啊。。。

 

T2

不会做= =

题意可以转化为,边权为[1,m]的n个点的二分图计数,但是黑色和白色是等价的。

用常用套路,设h[i]为i个点的答案,f[i]为i个点的连通的二分图个数,g[i]为i个点瞎连的二分图个数,那么有如下关系:

$$h[i]=\sum_{j=0}^{i-1}C_{i-1}^{j}f[j+1]h[i-1-j]$$

即枚举第一个点连通块大小j+1,从剩下i-1个点里面选,其中j+1个点的方案数为f[j+1],剩下的是h[i-1-j]。

 

$$g[i]=\frac {\sum _{j=0} ^{i} C_{i}^{j} (m+1)^{(i-j)j} } {2}$$

即枚举两个集合的大小,把边权为0视为不存在边,除以2是为了让黑白等价,去除反色方案。

 

$$f[i]=g[i]-2\sum_{j=0}^{i-2}C_{i-1}^{j}f[j+1]g[i-1-j]$$

考虑从g中刨去不连通的方案,枚举连通块的大小,强制让一部分连通,另一部分随便连。因为这些方案都是带标号的,所以并不会重复枚举,乘2也是因为这个。

然后就做完了。

 

T3

数据结构题。

出题人为了隐藏LCT的本质,把题面弄得又长又烦好讨厌。

事实上就是统计子树到达根节点经过的虚边数量之和。那么,我们维护LCT的链顶和链底,轻重边切换的时候在线段树上区间加减就好了。换根操作只影响线段树操作,如果新根和当前涉及到的节点DFS序不相交或者被新根包含那么照常处理,如果是当前点包含根的话就对除了根子树部分进行操作。

 


UR #17

只改了一道题= =

T1

值域很小,而且有n=100的点,提醒我们可以从值域的角度来搞一搞。

首先最优解无论如何都是一条链,因为分叉肯定不优,考试的时候居然没想这个。那么,我们可以设f[s]:需要变成0的二进制位状态为S(即需要的状态或起来)所需要的最小代价,f[s]=min{f[s&a[i]]+(s&a[i])}。那么,我们可以在外层枚举S,抽出来共有的相同部分,内层枚举每个物品(为什么要这样?因为要保证小的状态先计算)。最后加上共有的部分的答案就好了。

可以通过枚举每个S的子集来优化这个过程,设g[i]表示是否存在使得一个数&i为0,之后就可以倒序枚举S,内层枚举子集了。


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974