|
|
T1 摆花（flower） 入门
当w>=0时，直接对c从大到小排序，而后取w*c[x]*x(1<=x<=n)之和
这里有一个堆优化做法，每次弹出最大值的复杂度是O(log m)，弹出n个的复杂度为O(nlog m)，小于直接排序的O(mlog m)，当n比较小时优化较有效（本题不卡常，且n、m同阶，故sort即可）
当w<0时，根据：负数乘一个较小的正数能得到一个较大的负数（也就是绝对值较小的负数），c由小到大排序即可
注意要开long long。
T2 苹果农场（apple） 普及-
本题卡了一个大规模测试点，正解是桶排
将00.00%到100.00%映射到0到10000，然后每天从10000到0统计，个数够了就输出
时间复杂度O(t)，常数最坏是10000，但实际是远远达不到的（因为是倒序枚举，而输出不严格地单调递增），可以过
T3 海平面（level） 普及/提高-
完整地读完题后，会发现是模拟题，但是是用搜索的方法来模拟的
需要实现两个功能，一个常规DFS（顺便求题目要求的参数），一个连通块
注意要开long long。
T4 山峰旅行（travel） 普及/提高-
如果练过CSP-J 2020 T4的话 这题还是比较水的
参照该题求三个决策的最短路，DP记搜之类都可以，注意某点不满足海拔限制时不应转移状态/继续递归
最后从第1列到最后1列递推求得最短时间：
贪心+递推/简单DP，已经到了最后1行，能往右走就尽可能往右，不能走再退回去
本套题的题目难度不高，但是细节很多，AK还是很考验状态和细心程度的。
|
|
发表于 2021-9-23 20:08:14
置顶卡