NOIP2015,2016简要题解

发表于 2017-10-18

NOIP2015

day1

神奇的幻方

纯模拟 #### 信息传递首先发现每从一个点出发一定可以走进一个循环。

所以我们可以对每个点开始走，走到了走过的点就是走进了循环。走的时候记录一下走到这里的步数，两次的步数差就是循环的长度。

直接暴力走会\(O(n^2)\)，会T，但我们发现，如果一个点在另一次搜索中搜过了，那么这一次搜索如果搜到这个点就可以退出去，因为再走也是进入一个同样的循环。

时间复杂度\(O(n)\) #### 斗地主暴力枚举顺子，剩下的贪心出牌。

官方数据没有什么像把四个拆成两个对子，把三个拆成一个单一个对之类的套路之类的。

注意一个王可以单出也可以三带一/四带二带出去，两个王不行。 ### day2 #### 跳石头二分答案，判断需要去掉的石头数是否\(\le m\) #### 子串设\(f[i][j][k]\)表示A串匹配到第i个字符，B串凑出了前j个字符，取出k个子串，并且用了第i个字符。设\(g[i][j][k]\)表示A串匹配到第i个字符，B串凑出了前j个字符，取出k个子串，不一定用第i个字符。则\(f[0][0][0]=g[0][0][0]=1\) 当\(j,k>0\)且\(A[i]=B[j]\)时，\(f[i][j][k]=f[i-1][j-1][k]+g[i-1][j-1][k-1]\) 否则\(f[i][j][k]=0\) \(g[i][j][k]=g[i-1][j][k]+g[i][j][k]\) 时空复杂度均为\(O(nmk)\)，时间复杂度OK，但是会MLE，所以我们可以用滚动数组优化，空间复杂度变为\(O(mk)\) ### 运输计划 注意常数优化 注意常数优化 注意常数优化 > 原题求：这m个运输计划都完成时的最短时间

说明要使这m个运输计划需要时间的最大值最小，又是二分答案。

我们可以二分一个答案，看有哪些路径的长度大于这个值，有没有边同时在这些路径上并且改造它会满足要求。

同时在这些路径上

这个东西可以用树上差分解决。记\(w[x]\)表示x点到x点父亲的边被\(w[x]\)条路径经过，利用树上差分，可以这么做：记录一条路径\(<s,t>\)，就w[s]+1，w[t]+1，w[lca]-2，然后计算真正的\(w[x]\)就是以x为根的子树\(w[x]\)的和。因为记录路径的时候是\(w[s],w[fa[s]],w[fa[fa[s]]\)以此类推全部+1，t也一样，然后从\(lca\)开始向上就要全部-2（因为本来不用计算却算了两遍）所以记录了w[s]就要上传到各个祖宗节点，所以这样是对的。时间复杂度\(O(log_2n)\),其中S为最长路径的长度。

注意常数优化 注意常数优化 注意常数优化

怎样卡常呢，可以参考我的提交记录 ## NOIP2016 ### day1

玩具谜题

几乎是纯模拟了。 #### 天天爱跑步 NOIP2017最难的题。可以把\(<s,t>\)的路径拆成\(<s,lca>\)和\(<lca,t>\)两条路径，然后分别维护有多少人看到。

同样使用树上差分。当维护\(<s,lca>\)这条路径时，要求路径上的点x能看到这个人当且仅当\(dis[x]+w[x]=dis[s]\) 其中dis[x]表示x的深度树上差分暴力维护子树信息。

维护\(<lca,t>\)这条路径时，首先把这条路径翻转成为\(<t,lca>\)，然后要求路径上的点x能看到当且仅当\(dis[x]-w[x]=dis[lca]-(dis[s]-dis[lca])\) 也就是\(dis[lca]\)减去从s到lca的最短路。同样树上差分维护，可以看我uoj的代码。 #### 换教室期望DP，之前发了博客 ### day2 #### 组合数问题当\(m=0\)或\(m=n\)时，\(C_n^m=1\) 否则\(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\) 直接递推取膜。记\(cnt_{n,m}\)表示\(0 <= i <= n，0 <= j <= min(i,m)\)中\(C_i^j \mod k= 0\)的i,j对数。则\(cnt_{n,m}=cnt_{n-1,m}+cnt_{n,m-1}-cnt_{n-1,m-1}+[C_i^j \mod k =0]\) 时空复杂度\(O(nm)\) #### 蚯蚓首先可以很直观的想到如果除了切开的蚯蚓其它的都增长q相当于全部增长q并且这两条蚯蚓缩短q。然后可以优先队列维护并得到65分甚至更高。具体是这样的：

每次找出最长的蚯蚓，设已经全部增长k次了，现在存的蚯蚓长度为s,则切好以后的两只蚯蚓长度为\(\lfloor p(s+kq) \rfloor\)和\((s+kq)-\lfloor p(s+kq) \rfloor\)

存的时候再减去\((k+1)q\)

但是我们发现，每次切的蚯蚓存的长度是单调递减的，切后的两只蚯蚓存进优先队列后的长度也是单调递减的。那么我们就可以用三个队列直接维护。第一个队列表示没切过的蚯蚓的长度。第二个队列表示切好后长度为\(\lfloor px\rfloor\)的蚯蚓长度。第三个队列表示切好后长度为\(x-\lfloor px\rfloor\)的蚯蚓长度。这三个队列都是单调递减的（第一个一开始要排序）。每次在三个队列的队首中取出长度最大的按上面的方法操作，然后得到的两条蚯蚓分别放进第二个和第三个队列。时间复杂度\(O(m+nlog_2n)\) #### 愤怒的小鸟装压DP，发过题解。