【LOJ】小奇 NOIP 练习题

2019年4月5日6,0602

可以在 https://loj.ac/problems/tag/207 AC 这些题目

小奇采药

小奇取石子

小奇的旅行计划

小奇探险

小奇采药

对于 30% 的数据，\(O(2^n)\) 枚举取 or 不取

对于60%的数据，\(O(nm)\)做01背包，即\(f(i,j)\)表示前i株

草药，耗费 j 的时间能达到的最大代价。

对于 100% 的数据，注意到 m,t,v 纯随机

那么不会选太多的草药，而耗时较少的草药有很大概率存在于最优解中

针对这些性质优化搜索

当然也可以合理使用随机化和卡时，复杂度 O(玄学)

小奇取石子

在n个数字当中取出m个，使得总和小于k。这是一个比较显然的背包动态规划模型，复杂度是\(O(kmn)\)

当然，对于n较小的数据，我们甚至可以使用\(2^n\)的算法暴力搜索每一种匹配方式，然后判断是否符合条件。

同时，我们注意到B组数据的k范围比较大，如果采用背包dp算法时间复杂度太高，我们也开不出那么大的数组来记录状态。

但是B组数据的n太小了，采用暴力搜索反而能过。所以，我们对于不同组的数据需要不同处理。

对于A组数据，我们注意到n和m的数据范围很小，只有10，那么直接暴力搜索或者做背包动态规划都能通过。

对于B组数据，由于k的范围过大，我们只能暴力搜索。

对于C组数据，由于n的范围过大，我们只能背包dp。

小奇的旅行计划

离线处理，将询问按照\(l_i\)从大到小排序，并按时间从晚到早的顺序逐渐加边。

扫描过程中我们可以直接维护\(ans[i][j]\)，即当前扫描时刻从城市i出发，最早要在什么时候到城市j。

添加一条边\((u,v)\)时，只有u和v两个城市出发的答案可能改变——现在它们可以直接走向对方了，而其它城市的答案都不会改变。

显然，加完边后，\(u,v\)两城市到达某一其它城市\(t\)的最早时间改变为了\(min(ans[u][t],ans[v][t])\)，强行维护即可。

时间复杂度\(O(nm+qlogq)\)，4s时限足以通过。

小奇探险

对于\(60\%\)的数据
\(f[i][j]\)表示\([1,i]\)中取了j个数，并且强制i要取
\(f[i][j]=\max\Big\{f[x][j-1]+k^{j-1}\cdot A[i]\ |\ \max(j-1,i-M)\le x<i\Big\}\)
复杂度：\(O(N^3)\)
注意j只和j-1有关，因此可以把第二维滚动掉。
运用单调队列可使得x不必枚举。
由于统计答案时必须要查看所有的\(f[i][j]\)，因此该算法复杂度下界是\(O(N^2)\)

对于\(100\%\)的数据
\(1+2k+3k^2+4k^3=\Big((4k+3)\cdot k+2\Big)\cdot k+1\)
从后往前考虑，在某次乘了k以后，后面的结果也都会乘上k，和后面取了多少个数无关。
我们用f[i]表示[i,N]的答案，则有
\(f[i]=\max\Big\{f[j]\cdot k+A[i]\ |\ i<j\le i+M\Big\}\)
直接用单调队列维护即可。正难则反。