【LOJ】小奇 NOIP 练习题

2019年4月5日7191

可以在 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\}\)
直接用单调队列维护即可。正难则反。

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Lucky_Dog Recent comment authors
  Subscribe  
提醒
Lucky_Dog
Lucky_Dog

wow黄学长又更新了