2016ICPC大连赛区题解

2016ACM/ICPC亚洲区大连站-重现赛(比赛链接)

1001. Wrestling Match

1003. Game of Taking Stones

 

1004. A Simple Math Problem

官方题解(PDF)

 

1005.Aninteresting game

1006.Detachment

1007. Garden of Eden

1008.To begin or not to begin

1009. Convex

1010. Find Small A

 

2016ICPC沈阳赛区题解

1003.Recursive sequence

http://acm.hdu.edu.cn/showproblem.php?pid=5950

题意:$$f(n)=f(n-1)+f(n-2)*2+$$ $$n^{4}$$,给定前两项,求第n项。

思路:矩阵快速幂,

$$n+1=n+1$$

$$(n+1)^{2}=n^{2}+2n+1$$

$$(n+1)^{3}=n^{3}+3n^{2}+3n+1 $$

$$(n+1)^{4}=n^{4}+4n^{3}+6n^{2}+4n+1$$

所以我的矩阵快速幂有七项,分别是$$f(n),f(n-1),1,n,n^{2},n^{3},n^{4}$$

1005.Counting Cliques

题意:$$n \leq 100$$ 个点,$$m \leq 1000$$ 条边的图,求大小恰好是 $$s \leq 10$$ 的完全图的数量,保证度不超过20。

思路:我用的是bitset+暴搜。本来图是用一个邻接矩阵来存储,但是那样如果要暴力判断一些点是不是完全图的时候,需要$$O(n^{2})$$复杂度,所以我使用bitset存储每一行,这样在DFS时候,如果要判断这个点是不是与祖先们的点都相连,只需要将这一位的bitset与DFS维护的bitset相与,如果结果小于DFS维护的bitset,说明这个点肯定和之前某一个点不相连。

 

1009.The Elder

题意:$$f_{i}= min_{j \ is \ an \ ancestor \ of \ i}(f(j)+dis(i,j)^{2}+(j==root?0:p))$$,求最大的$$f(i)$$。

思路:这个题目是就是HDU3705的增强版,几乎一毛一样,只是把线性改为了树形,首先我们会很容易得出一个$$O(n^{2})$$的DP,那么我们需要斜率优化一下,

首先容易得到一个dp,$$dp[i] = dp[j] + (sum[i] – sum[j])^{2} + p$$,
// 不过复杂度不够,考虑优化。
对于$$k<j<i$$,若j是比k更好的选择,那么
$$dp[j] + (sum[i]-sum[j])^{2} + p \leq dp[k] + (sum[i] – sum[k])^{2} + p$$
推出
$$\frac {dp[j] + sum[j]^{2} – (dp[k] + sum[k]^{2})} { 2sum[j] – 2sum[k] }\leq{sum[i]} $$
我们令$$y_{i}=dp[i] + sum[i]^{2}, x_i=2*sum[i]$$,式子就可以改写成
$$\frac{y_j – y_k}{x_j – x_k}$$$$ \leq sum[i]$$,
如果把$$(x_i, y_i)$$看作一个点,其中左边是斜率,右边是个单调递增(不减),
的函数。

我们令斜率$$K_[k, j]=\frac {y_j – y_k}{x_j – x_k}$$,$$K_[j, i]=\frac{y_i – y_j}{x_i – x_j}$$,.首先如果$$K_[k, j]\leq sum[i]$$, 我们说当前决策点j比k优(由假设推得),并且sum[i]一直
递增,那么j接下来也一直比k优,反之,我们就说当前决策点k比j优。

%e6%96%9c%e7%8e%87%e4%bc%98%e5%8c%961

假设$$K_[i,j] < K_[k,j] \leq sum[i] $$,因为$$K_[k,j] ] \leq sum[i]$$,所以j点不是最优点.

那么如果$$K_[j,i] < K_[k,j] $$&& $$K_[j,i] >sum[i] $$,那么$$K_[k,j] >sum[i] $$,所以k比j点优,j不是最优点。

所以我们需要维护的是一个下图一样的下凸图形,方法是单调队列。

%e6%96%9c%e7%8e%87%e4%bc%98%e5%8c%96
以上是斜率优化的内容,那么对于这个题,我们要考虑树上的问题,因为在子树中,我们可能会对单调队列进行修改,那么递归回来的时候,需要恢复,我用的方法是对于每一个点打一个时间戳,然后对于修改操作用栈来存储,当递归完一颗子树之后,将堆栈中属于子树的操作弹出,恢复数组的样子,然后递归另一颗子树。

这里另外给出qj大神的一种想法,因为每次对于单调队列的操作只会改变尾部的一点,那么可以将这一个点的变化记录下来,恢复的时候就不用全部恢复,只需要回复一个点就好。

再次感谢qj大神教我斜率优化。

 

 

2016CCPC杭州赛区非官方题解

1001. ArcSoft’s Office Rearrangement

题意:有两种操作,一种是把两个数相加,产生一个新的数,一种是将一个数拆分成两个数,但要求要保证和和原来的数相等。

思路:从前往后贪心就行,如果当前的数等于平均数,那么就直接过,如果小于平均数,那么就加上后面的数,然后重新放会队列头,如果大于平均值,那么就减去平均值,然后将剩下的值放到队列的头部,注意要用除法加速。

1002.Bomb

题意:给你一个有向图,每一个点都有一个权值,选择一个点后,他所能遍历到的点都会被覆盖,求最小能够覆盖全图的权值。

思路:先用tarjan缩点,每个新点的的值是当前环中的最小值,然后把入度为零的点的权值相加即可。

1003.Car

题意:有个老司机在开车, 开车过程中车的速度是不减的. 交警记录了这个老司机在n个时间点的位置, 但是时间位置. 已知老司机从位置0出发, 记录的时间点都是整数, 问经过第n个位置最少需要的时间.

题解:通过最后一段路程的时间肯定为 1 秒,只需由速度不降原则倒推出每一段所通过的最小整数时间即可,贪心做法。

1004.Difference

题意:求有多少个y满足等式。

思考,虽然题目没有明确说y的上限,但是我们可以推测出y<=$$10^{10}$$,因为假设y=999999999的话,约为3.8*$$10^{8}$$<=$$10^{10}$$,已经无法满足x>=0的条件,所以y不会太大,那么我们可以首先将f(y,k),(y<=$$10^{5}$$)都预处理出来,然后我们把y分成高五位y1和低五位y2两个数,然后x=(f1-y1)+(f2-y2),这样我们就可以分成两部分处理,我的做法是枚举高五位,然后二分低五位的情况,复杂度是n(logn)。

1006.Four Operations

题意:给你一些数,让你将’+’, ‘-‘, ‘*’ 和 ‘/’四种符号有序的填在其中,使得最后的结果尽量大。

思路:暴力枚举即可。

1011.Kingdom of Obsession

题意:给你两个数组1~n和s+1~s+n只有当y%x=0(y<=s+n&&y>=s+1,x>=1&&x<=n)时,这两个数才可以匹配,问你这两个数组能不能完全匹配。

思路:首先要知道质数只能和 1 或者它本身的匹配,所以如果 [max(s+1,n+1),n+s] 区间内如果有多于一个质数时肯定无解,如果有两个数组有重叠部分,那么我就默认中间重叠部分自我匹配是最优策略,虽然这样会给大家一种钦定的感觉,但是我也想不出更好的策略了。我打出了$$2*10^{9}$$看了看,发现任意连续的两个质数的差值好像不是很大嘛,也就是20左右,所以大胆猜测,如果[max(s+1,n+1),n+s]的区间长度大于35,就是no,否则就匈牙利一发,然后就过了。。。。事后发现,其实相邻两个质数的差值可以有248那么大,我只能说数据水了。。。。。

 

 

2016大连网络赛题解(持续更新)

这场比赛就一个字,邪!

1006

这个题不想多说,XJBG就过了

1009

这个题非常有意思,给你N个点,M条边,然后让你求除去这M条边的补图的最短路,有一种似曾相识的感觉。
在这里我用set维护还没有遍历过的点,总复杂度是O(n+m)。

1010

这个题是我用树状数组过的,首先找到根节点,然后一遍DFS,遍历到某一个点的时候,把这个点加到树状数组,回溯回来的时候再减去。
我觉得麻烦的地方在于预处理,我首先进行了离散化,处理出了match数组,这是一个映射关系数组,math[u]=v,意思是,u点对应的树状数组区间是1~v。

VIM配置

我的版本

大神的版本

点分治算法、树链剖分算法在竞赛中的应用

算法合集之《分治算法在树的路径问题中的应用》

最近拜读了下大神的文章,仔细学了下点分治以及树链剖分,受益匪浅,对这个专题感兴趣的同学强烈推荐这篇论文。
下面我对于几道例题做一下讲解。
poj1655求树的重心

http://poj.org/problem?id=1655
首先讨论一下树的重心,重心的定义是去掉这个点之后,产生森林中树最小的点。那我们做的时候就可以一边DFS搜索就行,对于去掉某一个点来说,产生的新树要不就是它的子树,要不就是它的父亲节点向上产生的树,所以比较一下就可以AC了。

POJ1741

http://poj.org/problem?id=1741
求$$dis(i,j)\leqslant K$$的点对数量,$$n\leqslant 10000$$。
这是一个非常明显的点分治,记$$Depth(i)$$表示点i到根结点的路径长度,$$Belong[i]=x$$(X为根结点的某个儿子,且结点i在以 X 为根的子树内)。那么我们遍历所有节点,在这个点被包含的新树里面,先求出重心$$root$$,然后要统计的就是:
满足$$Depth(i)+Depth(j)\leqslant K$$且$$Belong(i)\neq Belong(i,j)$$的$$(i,j)$$个数
= 满足$$Depth(i)+Depth(j)\leqslant K$$的$$(i,j)$$个数 – 满足$$Depth(i)+Depth(j)\leqslant K$$且$$Belong(i)=Belong(i,j)$$的$$(i,j)$$个数 。

SPOJ1825

http://www.spoj.com/problems/FTOUR2/
这一次统计的是使得经过的黑点数不超过K个,且路径长度最大,$$n \leqslant 200000$$。
具体做法详见论文,我这里附上我的详细代码。

SPOJ375

http://www.spoj.com/problems/QTREE/
现在开始进入树链剖分。
这个题问的是可以修改某些边权,然后问你两个点之间的最大边权是多少。
首先我们要这一颗树线性化,这里我们要先按照重边走,没有重边就走轻边,按照遍历的顺序建立线段树,那么其实算法到这里,基本上就和分治没有关系了,专心写线段树就好了,线段树维护的就是区间最大值。
那么查询的时候,其实就是两个点慢慢往最近公共祖先移动的过程,注意,对于重边来说,不是一个一个点往上移动,而是直接跳到重链头部,这样节省时间,具体详见代码。

SPOJ2798

http://www.spoj.com/problems/QTREE3/
这个题其实比上一道题水一点,求的是距离1节点最近的黑点。那么我们建立线段树的时候,维护的就是区间的最左端点,这里需要深刻理解一下,因为有人可能认为,最左节点不一定是最浅的点呀,但是仔细想一下,我们对于一次查询,只有当$$if(segtree[i].l==l&&segtree[i].r==r)$的时候,我们才会使用这个区间存下的值,那么我们在查询的时候已经会保证l,r这段在树上的路径在线段树中是连续分布的,所以这么查询是没有问题的,一开始提交的时候一直是41.67分,后来发现1 1 这种查询并不能过,改之后100分。