2015-ACM多校训练第四场

题外话

思考了一下人生,快打regional了,功利一点说多校的题并不需要每道都补,一些比较丧病或者烦的题我暂时就跳过了吧QvQ,先把正常向的题补了。。


hdu 5327(1001) Olympiad

Solution

SB暴力题,暴力算就好

Code


hdu 5328(1002) Problem Killer

Solution

水题,等差等比$O(N)$扫的时候判断即可

Code


hdu 5329(1003) Question for the Leader

Solution

简化问题,考虑把一棵树分成$k$块,这时一个显然的结论是如果有$k$个子树大小为$
\frac{n}{k}$的倍数,即可以分成$k$块。
考虑原问题,原题是一个基环加外向树,考虑不在环上的点$i$的$sz[i]$,显然可以直接计算。在基环上的点,不妨考虑断掉一条边后每个点为根的子树的$sz$,容易发现是一个前缀和的形式。然后我们对枚举的$k$取模,每次$O(N)$枚举在环上断掉哪条边即可。
复杂度$O(N\times logN)$

Code


hdu 5330(1004) Route Statistics

Solution

dp题,考虑$dp[S][k]$表示与$S$这个点距离为$k$的个数。($S$是一个长度为维度的$0,1,2$串)我们最后求出所有的$dp[S][k]$即可。
我们发现可以枚举中间某位不同,把那位分别替换为$0,1,2$三种情况来转移,简单dp一下即可

Code


hdu 5331(1005) Simple Problem

Solution

这个题其实并不Simple = =模型转换比较神,代码比较长,暂时没补,以后再说QvQ


hdu 5332(1006) Test for Rikka

Solution

这个一道比较有趣的题,$B=A^m,B[1][n]=k$很容易想到,我们相当于从$1$开始走$m$步到达n的方案数是k。
这样至少有个方向了。然后我们考虑特殊的图,完全图。
一个$n$个点的完全图,且每个点都直接与自己相连,走$x$步到达每个点的方案数都是$n^{x-1}$,然后怎么做呢。
我们很容易想到进制拆分,把$k$写成$\sum a[i]\times n^i$的形式,我们只需要搞出$a[i]$就可以了,我们可以把终点n拉出一条链,分别表示成对应$n$的$i$次方,然后不妨考虑完全图上有$a[i]$个点和链上连,这不就是$a[i]\times n^i$了么!至此,问题解决

Code


hdu 5333(1007) Undirected Graph

Solution

LCT题,先跳过= =以后再补


hdu 5334(1008) Virtual Participation

Solution

$k\le 10^5$时,全输出$1$即可
否则,不妨枚举有$i个1,j个2,k个3$,则,$i + j + k + i\times j + i\times k + j\times k=x$,枚举$i,j$即可,看上去复杂度非常高,其实满足条件的$i,j,k$不会特别大的

Code


hdu 5335(1009) Walk Out

Solution

细节题,先一直沿着0走到距离终点最近的距离,把这些点加入队列。
之后显然可以贪心走,输出答案时要注意细节。我写的有点烦= =

Code


hdu 5336(1010) XYZ and Drops

Solution

没什么好说的,大暴力就行,大水滴小水滴个数都不多,暴力复杂度完全可以接受

Code


hdu 5337(1011) Yet Another XYZ Problem

Solution

大型讨论题,先跳过= =


hdu 5338(1002) ZZX and Permutations

Solution

这题题意非常蛋疼,读懂了以后并不难做。
由于字典序要求最大,很容易想到贪心,不妨按位贪心,考虑第$1$位,查询$1$这个数的下一个数,不妨设为$A$,看之前的区间最大值$B$,如果$A$更大的话,标记$A$值使用过了,说明这个循环节可以用后面的替换。如果$B$更大,说明当前位置到$B$之间是一段连续的区间,确定下来了,然后把区间位置插入一个set里,表示这段区间已确定。就搞定了

Code

完结撒花!
继续补题!>_<