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。