NOIP训练赛 #2
T1 探险
【数据范围】
\(1\leq n,m,k\leq 10^3,1\leq x_1,x_2 \leq n,1\leq y_1,y_2\leq m\)
题解
直接BFS即可
注意这道题不能用 \(vis\) 数组,因为一个点有可能会被更新多次,只需要在遍历 \(k\) 的时候多加一个如果当前要更新的点( \(nx,ny\) )的值比当前点( \(x,y\) )的答案加一的值还要小就停止更新(后续的点可以用 \(ans_{nx,ny}+1\) 而不是 \(ans_{x,y}+2\) 来更新)
时间复杂度 \(O(nmk)\)(实际根本跑不满)
T2 合成
给出一个长度为 \(n\) 的数组，执行下列操作：
找到最小的，至少出现了两次的数字 \(x\)，将第一次出现的 \(x\) 从数组中删除，将第二次出现的 \(x\) 改为 \(2\times x\) 。直到无法再进行这样的操作为止。
输出最后的数组
【数据范围】
\(1 \leq n\leq 1.5\times 10^5,0 \leq a_i \leq 10^9\)
题解
使用优先队列储存全部n个数。每次取出最小的两个数出来，如果两个数相同，则把第二个数 然后放回优先队列，删除第一个数；否则将两个数
都删除了。直到不能再删除为止
时间复杂度 \(O(nlogn)\)
T3 健身
【数据范围】
\(1 \leq n\leq 20,0\leq a_{i,j}\leq 10^4\)
题解
看到 \(n\) 的范围就知道是状压DP
状态设计:设 \(dp_i\) 表示当前训练状态为 \(i\) 时的最大价值和
状态转移:
首先枚举状态然后枚举那一个项目没有在当前的状态中,然后统计新加入大项目和已选的项目的贡献和 \(sum\)
所以 \(sum=\sum_{k=0}^{n-1}num_{j,k}[i\&(1<<k)]\)
状态转移方程为: \(dp_{i|(1<<j)}=\max(dp_{i|(1<<j),dp_i+sum})\)
答案即为 \(dp_{2^n-1}\)
时间复杂度 \(O(2^n\times n^2)\)
T4 顽皮的猴子
【数据范围】
\(1\leq n,m,q \leq 10^5,k\leq 10\)
题解
对于树上的两个点 \(x,y\) 来说,答案就是 \(x\sim lca(x,y)\) 的前 \(k\) 小和 \(y\sim lca(x,y)\) 的前 \(k\) 小中的前\(k\) 小
故考虑在倍增的时候对于每一段倍增直接跳的区间预处理这些段里的前 \(k\) 小,每次合并两个队列即可,因为 \(k\) 最多不超过 \(10\) ,所以空间复杂度不会爆炸(但不能用 \(STL\) 的 \(queue\),否则空间就炸了)
时间复杂度 \(O(qlog^2n)\)