本文包含了NOIP2015十道题目的题解。
普及T1 金币
模拟
1 |
|
普及T2 扫雷游戏
模拟
1 |
|
普及T3 求和
我们挖掘条件的性质可以发现:$y$无关紧要,当$x$和$z$的奇偶性相同时,他们之间旧就会产生分数。
所以每一种颜色分奇偶计数,然后一种颜色一个奇偶性产生的分数为
其中$s_4$为该种颜色该种奇偶性的格子数,$s_1$为这些格子$xtimes num_x$的和,$s_2$和$s_3$分别为这些格子$x$和$num_x$的和。其中$x$指编号,$num_x$指编号为$x$的格子上的数。
证明过程略,可以自己手动推导。
综上,这个算法的时间复杂度是$O(n+m)$。
1 |
|
普及T4 推销员
一道贪心。
我们可以先算出总的疲劳值,然后每一次选择哪一户人家再也不去。这个时候,我们要保证减少的疲劳值最少。
我们可以发现一次只有$2$种删去住户的决策:
如图,$head$表示当前疲劳值消耗最小的住户编号,$last$表示最低端的住户编号,$front$是$last$前一个住户的编号。
每一次可以去掉$head$,也可以去掉$last$。而去掉$last$就没必要走$front$到$last$的路了,所以第二种决策会减少$(dis[last]-dis[front])times 2+last$需要的疲劳值。
对住户的(疲劳值,编号)二元组按疲劳值排个序,然后维护以上3个量即可:$last$,$front$和$head$。
注意,还需要维护每一个住户是否已经被清除,是的话要打标记,否则$head$指向的住户可能会是$last$,这样就不合法。
时间复杂度:$O(nlogn)$
1 |
|
提高D1T1 神奇的幻方
模拟
1 |
|
提高D1T2 信息传递
乱搞。
题目:求最小环。
解:爆搜/tarjan。
能用tarjan是因为这里面的强连通分量只能是简单环。
DFS解法
1 |
|
Tarjan解法
1 |
|
提高D1T3 斗地主
部分搜索。
先搞掉所有顺子,然后问题转化为一个简单的最优化问题,dp可解。
设$f(i,j,k,l)$为一副牌,有$i$份4张,$j$份3张,$k$份2张,$l$份1张,最少打几次。这个最开始就可以做。然后搜索即可。
1 |
|
提高D2T1 跳石头
看到描述就看的出是二分答案。
二分答案,设为$x$,把石头排序之后扫一遍,看看是否有石头与前一个石头的间隔小于$x$,有的话拆掉该石头,否则把这个石头作为“前一个石头”,再看下一个。如果拆的次数大于$M$就判定失败,否则判定成功。
时间复杂度$O(NlogL)$。
1 |
|
提高D2T2 子串
看数据范围猜算法系列
时间复杂度相信各位都看的出来:$O(nmk)$
怎么刻画状态呢?
首先有$2$维必不可缺:$i$表示$A$前$i$个字符,$j$表示$B$前$j$个字符。这里指的是用前$i$个$A$的字符来匹配$B$的前$j$个字符,串$A$的前$i$个不一定要严格匹配,但串$B$的前$j$个必须严格匹配上。
之后,段也要表示:$t$表示现在做了$t$段。
看到这些段不是连续的,所以使用情况也要表示出来,设一个布尔变量$l$表示串$A$的这个字符是不是被使用了,是为$1$,不是为$0$。
够了,用$f(i,j,t,l)$来表示。
不使用这个字符,就继承串$A$上一位的状态。使用的话,必须匹配成功,然后有$2$个决策:开启新的一段(前一个字符没用的话就默认开启新的一段了),或者接上前一段。
得到状态转移方程:
初始是$f(i,0,0,0)=1$。
要用滚动数组,不然MLE。
1 |
|
提高D2T3 运输计划
直接求解显然很困难,考虑转化为判定性问题,二分一个答案$x$,判定他是否可行。
完成一次运输的时间取决于最长路的大小,也就是保证所有路径的长度都小于$x$。考虑大于$x$的路径,在他们的公共路上删掉一段路才可以使他们一起变小。理所当然的,这段路必须是他们的公共路径中最长的一段。
怎么找这条最长的公共路呢?我们可以玩一玩区间加法,给每一个在$(u,v)$两点上的路径打一个标记,这样就说明这些点在$(u,v)$路径上。如果两点的标记数都等于长度大于$x$的路径总数,呢么两点间的这段路就是他们的公共路径。
区间加法有$2$种实现方式:一种是树剖/$LCT$,一种是树上差分(和序列上的没区别)。由于只需要查询一遍,没必要用什么奇奇怪怪的数据结构,所以用差分,在$x$和$y$上打一个$+1$标记,在$LCA$处打一个$-2$标记。由于是对点操作,所以要把边和点捆绑起来。具体不难实现。
时间复杂度取决于求解$LCA$时所用算法的时间复杂度。用倍增的时间复杂度是$O((n+m)logn)$。
注意卡常。
1 |
|
近期评论