2024 ICPC复习 20-30页

https://www.luogu.com.cn/problem/CF1703G

首先这个题一定要意识到 他是一个折半的操作
1e9最多被操作30次 所以我么完全dp第二维可以放这个次数
然后 dp数组就开出来了 时间复杂度也就明确了
对于某一个箱子 可以使用好钥匙打开也可以不用 用坏钥匙
好钥匙打开就是
dp i j=dp[i-1][j]-k+a[i]>>j 坏钥匙 dp[i-1][j-1]+a[i]>>j
不过还需要思考到 如果我已经超过了30把钥匙的情况 dp[i][30]=max(dp[i-1][30]+0,dp[i][30]) 可能自己是第31把了

https://www.luogu.com.cn/problem/CF1692D

这道题还是不太会做 看到心里还是不敢想

题解写法是暴力模拟就行 反正几千分钟之内必须会回来

然后超出了一小时就% 24也是% 如果循环就break