夏令营8.3总结

今天还是模考。

T1

老师不讲武德

老师竟然闲得无聊把很难的一题放在了最前面。

我们几乎全班都中招了。因为正常情况下，第一题是正常的签到题。但是这一次的T1难度爆表，很多人甚至没做出部分分。因为是捆绑测试

其实思路就是分段处理所有的纸币，按照面值从大到小使用。

将物品的剩余金额从大到小排列。继续使用上面的方法。

最后，输出结果即可。

T2

这题在考试的时候，花了好久才理解样例，因为一个车站可以同时有多个公交线路。

但是在考试的时候没有完全总结出判断是否合法的逻辑。所以只有22分。

下面是完整的判断逻辑：

1. 遍历过程中，G的数量始终$\ge$R的数量，且$\le$W的数量。
2. 字符串结束时，G和R的总数量相等。
3. 字符串中至少包含一个G。

最后，符合这三个条件的就是合法的序列，否则不合法。

T3

这题考试的时候正解完全不会写，但是写了一个时间复杂度奇怪（好？）的暴力，居然拿了TLE70分！

正解：

• 其实就是递归+回溯
• 一个数能被$2^m$整除，当且仅当该数的最后$m$位二进制表示为$0$。对于十进制数，这意味这该数的最后$m$位组成的数能被$2^m$整除。
• 递归的逻辑就是：从空序列开始，逐步在序列前添加1-9（首位不能为0），每一次添加就检查是否满足条件。
• 最后，再加上一个剪枝即可。

T4

这题似乎挺难的，但是我考试的时候还是不知道怎么样正经地骗分骗了12分。