2019 CSP-J2 题解


数字游戏

简单的字符串操作

公交换乘

按照题目意思模拟。

但需要发现一个性质:题目保证了所有的时间都不相同,而且地铁和公交的时间间隔不能超过 \(45\) 分钟,所以,对于每辆公交车,最多只需要查找他之前的\(45\)次票的情况即可。

时间复杂度 \(O(45n)\)

纪念品

首先需要看透一些东西:

  • 假设一个物品在 \(x\) 天买入 \(y\) 天出手
  • 我们可以把上述的过程看作 \(x\) 天买入,\(x+1\)天卖出再买入,\(x+2\)天卖出再买入,\(\cdots \) \(y\) 天卖出

这样一来,我们就解决了跨度的问题

可以把所有的问题放到相邻的两天来解决

假设价值 \(x\) 可以获得的最大增值是 \(f[x]\) 

因为只考虑相邻的两天,增值就是相邻两天价值的差值,因为可以进行无限次,相当于是一个完全背包问题

可以很容易地得到 \(f[x-p[i][j]]=max{f[x-p[i][j]]+(p[i+1][j]-p[i][j])}\) 

然后每天不断的增加价值上限即可

因为题目保证了“小明手上的金币数不可能超过\(10^4\)” 所以复杂度是有保障的

加工零件

可以很明显的把题目转化成求从 \(1\) 出发到某一个点是否存在长度为 \(l\) 的路径

因为题目是无向图,所以要存在这样的路径,当且仅当满足以下两个条件的时候:

  • 从 \(1\) 出发到某一个点是否存在长度和 \(l\) 的同奇偶的路径
  • 且同奇偶的路径中最短路径必须 \(\le l\)

于是,我们只需要预处理出从 \(1\) 出发到每一个点长度分别为奇数和偶数的最短路径(或者不存在)就可以在询问的时候直接 \(O(1)\) 给出答案了。

图中的路径长度都为 \(1\) ,所以直接 BFS 求最短路就好了

总的时间复杂度 \(O(n+m+q)\) 。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 16,270

Categories

Archive

Comments