CSP-J 2018

T1

简单的判断,八个字符,错了真的也是没有办法了

T2

一道可以暴力的模拟题,我也不知道为什么比赛的时候我会少打队列的一个判断,可能太紧张了。基于此应该想到可以利用优先队列(或类似)的数据结构来维护,每次坐公交,在所有价值大于本次票价的优惠券中优先使用过期时间最早的(不用就过期了!),价值最低的优惠券。一旦票过期了,就删掉,但是如果票只是价值不够,那可能后面还会有用,所以还要压回去。

T3

本题思路可以根据数据范围来想。这是一道动态规划题。
刚开始想到的是建立一张全图,但是后来发现节点数量不是N 而是N*T ,并且总价值也不一定只能走一条路。后来发现可以用动态规划解决,首先设f[x]是第x天能够赚到最多多少钱。那么f[1] = m。重点在于状态转移,f[ i ] 肯定是由f[1]到f[i-1]中推出来的,而且单独一个f[i-1]无法表示所有状态。所以假设当前处于状态j ,将第j 天物品的价格可以看作花费,第i天的物品价格看作价值,就做出了一个完全背包问题,背包容量是当天的金币数f[j] 。

if(f[k]<=f[ k-a[i-1][j] ] - a[i-1][j] + a[i][j])
f[k]=f[k-a[i-1][j]]-a[i-1][j]+a[i][j];

跟完全背包基本一样,就是将其改成了数组。考试的时候想不出来,根据那个数据范围,也可以扣个十分甚至更多。

T4

最短路径把。再判断一个有环无环,有环就跳出来,然后一直往前搜。

发表评论

电子邮件地址不会被公开。 必填项已用*标注