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大神教我斜率优化。