NOIP2015,2016简要题解
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，发过题解。