从历年NOIP普及~提高-难度的题学调试方法

Luogu1076 寻宝
- 代码思路

纯模拟。但是需要通过模运算优化掉不需要的环。

调试部分

因为题目中有如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间这句话，所以如果这层有 $7$ 个有楼梯的房间，你第一个看到的房间的牌号是 $7$ ，那么你也要走 $7$ 步，而不是 $0$ 步。

所以，取模的代码要写成a[i][j].num=(a[i][j].num-1)%ct[i]+1，这样的话 $5$ 的话输出还是 $5$ 。

Luogu1077 摆花

代码思路

DP。

方程推法

题目有两个限制——每一种花能摆多少盆，一共能摆 $m$ 盆。

那么我们可以假设 $f_{i,j}$ 为摆完第 $i$ 种花有 $j$ 盆。

然后呢，不难想出既然花要一种一种摆，那么我们可以枚举每种花摆多少盆。

那么的话，转移方程就很好推了。

具体看代码。

Luogu1158 导弹拦截

代码思路

使用struct存每个导弹的数据，再将每个导弹到导弹拦截点的距离算出来，最后再排序后枚举哪些导弹可以给二号系统拦截。

其余的全给一号系统。

Luogu1199 三国游戏

贪心策略

不难发现贪心测略和电脑的一样即可。

但是要记住读入时 $(1,n-1)\times(i+1,n)$ 的时间复杂度会超时。

Luogu1309 瑞士轮

代码思路

模拟+合并。但需要注意的是win和lose要分开排序，要不然会被卡常数。

调试策略

在看到自己的代码多次被卡的时候可以考虑把快速排序换成归并排序。

Luogu2058 海港

代码思路

纯模拟。

优化

纯暴力显然过不了。所以我们可以把每个人使用一个结构体存起来——这个人来的时间以及这个人的国籍。

每一艘船到达时，我们需要将(这艘船到达的时间t,这艘船上第i个人的国籍x)存入队列，然后 $ans_x++$ 。

很显然如果 $ans_x=1$ ，说明这是一个新的国家， $sum++$ 。

然后从队头开始遍历，将距离当前时间大于一天的船上的人全部弹出。

如果 $ans_{\text{弹出的人的国籍}}=0$ ，那么 $sum--$ 。每次询问后输出 $sum$ 即可。

Luogu2239 螺旋矩阵

思路

这题思路不好想。

画出矩阵、观察规律、推导公式。 这是解决矩阵类问题似乎一个不错的解。

我们可以得出：

如果是第 $1$ 行，那么第 $j$ 列的数字就是 $j$ ；

如果是第 $n$ 列，那么第 $i$ 行的数字就是 $n+i−1$ ；

如果是第 $n$ 行，那么第 $j$ 列的数字就是 $3 \times n-2-j+1=n\times 3-j-1$ ；

如果是第 $1$ 列，那么第 $i$ 行的数字就是 $4 \times n-4-i+2=n\times 4-i-2$ 。

然后可以递归求解，把螺旋矩阵一层一层地剖开，看看目标位置在哪一层，然后加上这一层最左上角的数字（ $4 \times (n - 1)$ ），即为要求的数字。

感谢洛谷用户Anguei的题解。

Luogu3956 棋盘

代码思路

记忆化DFS可解。

记忆化的方法

我们设 $f_{i,j}=(i,j)$ 的最优解。当程序开始时，我们需要将 $f$ 初始化成 $\infty$ 。对于每一次到达的点，如果当前点已经大于目前的最优解，直接return。

否则再继续dfs下去。

剩下的就是普通的dfs了。

Luogu5662 纪念品

代码思路

DP。

方程推法

显然当 $t=1$ 的时候，你就算今天怎么买，到今天晚上你也得卖出去。有这些精力，去隔壁公园散散步不好？所以 $t=1$ 的最优策略是不要买东西，输出 $m$ 。

不难发现，每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。

这意味着我们可以当天下午买入的纪念品，在第二天早上卖出，第二天下午买入，第三天早上卖出，第三天下午买入，第四天早上卖出，和从第一天下午买入，第四天上午卖出无任何区别。

所以我们只需要观察每天的行为即可。不难发现每天的行为是独立的。

也就是说，问题转换成了——

现在有 $n$ 种物品，每种物品有无数个。你现在可以选择将这个物品塞进背包，获得 $p_{i+1,k}$ 的收益，代价是 $p_{i,k}$ 。其中 $i$ 是第几天， $k$ 是第几个物品，求 $t$ 天结束后你的最大收益。

那这是啥？完全背包啊！

那直接把完全背包板子套上去即可。

可惜考场上没写出来。

Luogu5682 次大值

代码思路

如果只有 $1$ 个数那不存在次大值，输出 $-1$ 。

先排序再去重，然后 $a_i\bmod a_j$ 的次大值就是 $\max(a_{n-2},a_n\bmod a_{n-1})$ 。