这次J组难度盲评红橙蓝绿~红红紫黄
首先是T2,做法很多,堆、二分、Treap都行,但我直接映射到值域为[0,600]的区间里面去做了。复杂度线性,常数极大。
但是我觉得题目只要稍微改动一下,我的做法就会变成二次,比如加一个变量m,表示分数的范围。
其次T4。首先我说一下,CCF的样例真的非常水,我的记搜是有问题的,但是样例查不出来。
关于T4的记搜,我认为需要考虑搜索的顺序,所以有3!=6种顺序,要搜索6次。因为搜索顺序不同,至少我的写法是会挂的。
我大致说明一下我的方法,搜索的时候用一个参数sum存储当前的权值,如果比之前搜到的最大值更小则不往下搜索去了。否则就更新之前存储的值,然后继续搜索。
另外,关于此题记搜的复杂度,我分析不出来,但我自测极限数据是能够跑过的。