2015 Multi-University Training Contest 1 题解&&总结

时间:2021-06-26 08:03:31

----------

HDU 5288 OO’s Sequence

题意

  给定一个数列(长度<$10^5$),求有多少区间[l,r],且区间内有多少数,满足区间内其它数不是他的约数。

  数的范围$[1,10000]$。结果对$10^9+7$取模。

Solution

  首先可以预处理每个数的约数有哪些。对每个数存下它的位置有哪些。

  然后可以枚举每一个位置,利用二分找到左边第一个是它约数的数,和右边第一个是他约数的数。

  假设向左有L个数,向右有R个数。那么ans应该加上(L*R)。

  时间复杂度$O(n*log(n)*log(m))$


HDU 5289 Assignment

题意

  给定一个数列(长度<$10^5$),求有多少区间,满足区间内任意两数差的绝对值小于k。

Solution

  1. 维护两个优先队列,一个大值优先,一个小值优先。移动区间的两个端点l和r  

    如果当前最大值-最小值>=k,将l从两个队列中删除,l++。

    如果当前最大值-最小值&lt;k,ans+=(r-l+1),r++。

    时间复杂度$O(n*log(n))$

2. 维护ST,枚举左端点l,二分右端点r。ans+=(r-l+1);

    时间复杂度$O(n*log(n)*log(n))$


HDU 5290 Bombing plan

题意

  X国有n($n<10^5$)个城市,用n-1条无向边连接。

  城市i有一个权值$w_i(w_i<100)$,如果炸毁城市i,那么距离i不超过$w_i$的节点也会被炸毁。

  求炸毁所有城市最少需要炸几次。

Solution

  相比前几天做的 SGU 280 不同之处在与这题对每个点有不同的k。

  但这一题不能贪心,只能采用dp的方法。形式上却也差不多,都是对子树的讨论。

  令f[i][j]为以i为根的子树,能向子树外拓展i个节点最少需要炸毁几个城市。

  G[i][j]为以i为根的子树,子树内有节点未被炸毁,且距离根为j最少需要炸毁几个城市。
  

  转移方程:

  不炸毁u点

    $f[u][j]=f[v][j+1]+min(f[k][0~j+1],G[k][0~j])$;

    $G[u][0]=f[u][0]$;

    $G[u][j]=G[v][j-1]+min(f[k][0~j-1],G[k][0~j-1])$;

  炸毁u点

    $f[u][w[u]]=1+min(f[v][0~w[u]+1],G[v][w[u]])$;

  这里需要对f[][]和G[][],求前缀最小值。

  节点比较多,避免爆栈不能直接用递归的方法做。

  时间复杂度$O(n*w)$


HDU 5291 Candy Distribution

题意

  有n($n<200$)种糖果,每种有$a_i$ ($a_i<200$)个。

  求有多少种方法从n个糖果中取一部分并分成数量相同的两份。

  结果对$10^9+7$取模。

Solution

  令DP[i][j]为前i种糖果分完后第一部分比第二部分多了j个的种数。

  设$a_{i+1}=t $ 可以得到转移.

  $DP[i+1][j]=DP[i][j+k]*((t-|k|)/2+1),(|k|<=t)$

  这个转移是$O(n)$的,我们需要让它简单一点。

  注意到当t为偶数且t=4的时候,以j为准。

  从j-4到j+4的乘法系数的差为-2,-2,-1,-1,0,-1,-1,-2,-2

  再看转移$DP[i+1][j+1]$时

  从j-3到j+5的乘法系数的差为       -2,-2,-1,-1,0,-1,-1,-2,-2

  从这里发现可以通过预处理$DP[i]$,来使得可以$O(1)$由$DP[i+1][j]$转移到$DP[i+1][j+1]$。

  只要加上右边偶数(包括0)位,减去左边奇数位。

  t为奇数的情况类似。

  时间复杂度$O(n^3)$


HDU 5292 Pocket Cube

题意

  一个2*2的魔方,掉在地上分开后重新组装,给出组装后的样子,判断该魔方是否可以通过旋转还原。

>规律题,不甚了解。


HDU 5294 Tricks Device

题意

  给一个$n(n<2000)$个点,$m(m<60000)$条边的无向图。

  分别求最少删掉多少条边该图从1到n的最短路长度变大,最多删掉多少条边该图从1到n的最短路不发生变化。

Solution

  先分别以1和n点为起点做一次单源最短路。求出哪些边哪些点在所有的最短路中。

  然后用所有的最短路边做一次最小割。就能得出最少删掉的边的数目。

  用m减去边最少最短路的边数,就可以求出最多可以删掉的边数。


HDU 5296 Annoying problem

题意

  给一棵$n(n≤10^5)$个节点的树,再给$q(q≤10^5)$个操作,初始集合S为空,

  每个操作要在一个集合S中删除或增加某些点,输出每次操作后:要使得集合中任意两点互可达所耗最小需要多少权值。

Solution(官方题解)

官方题解


HDU 5297 Y sequence

题意

   给定正整数$n(n<2*10^{18})$和$r(r≤62)$,定义数列为从正整数序列中删除所有能表示成$a^b(2≤b≤r)$的数后的数列

  求数列的第n个数是多少。30000组数据。

Solution

  利用容斥计算前k个数有多少个在数列里面。然后可以二分或者迭代k。

  时间复杂度$O(30000*log(n)*62)$


HDU 5299 Circles Game

题意

  给$n(n<20000)$个圆,任意两圆的只有包含和相离关系。

  两个人玩游戏,每次可以消去一个圆和它包含的所有圆,最后不能消去的失败。

  判断先手赢还是后手赢。

Solution

  树上博弈。可以先对半径排序。半径最小的包含圆i的圆就是它的父亲。直接暴力判断建树都能过,稳妥的方法还是用线段树。

  叶子节点的SG值为0,中间节点的SG值为它的所有子节点的SG值加1后的异或和。直接dfs就行。