本文从WordPress迁移而来, 查看全部WordPress迁移文章
有点可惜啊,整场比赛,写的代码里面有很多小bug,所以提交AB两次的时候有些慢了,不过过了之后排名还好,好像是90多,然后看了C,想了可能有20分钟的样子,想了出来,但是写起来也是有很多小bug,想赶着在1小时前过掉的,但是调小bug浪费了时间,最后1小时02分钟过了,排名很满意了19,后来跌了一下也是25左右。提交前有想过测试一下 10 10 10 10 10 这种数据的,但是急了,没测试,最后就是输出答案的时候,ans = INF,对于那种数据ans不会被更新的,最后输出了INF,应该是输出0的,所以 system test的时候C题挂了,最后的排名是144,很可惜,但是这就是比赛的一部分,下去加油。另外比赛中想出了D题的做法,就是相对暴力地搞,不过水平太差,没能在比赛中写出来,赛后写完了,继续努力吧
A.B 略
C.
如果一个数字改变了,只会对它两边的两个数字产生影响,所以对于一个数字x,开一个vector,把每个x两边的数字都放入x中(如果两边的数字有x,那么不用放,只放非x的数字)
我们枚举x,即把x变为某个数字,看看结果会不会变小,对于每个x,应该变为什么呢?那就看x对应的那个vector了,取中间大的那个数字z,让x变为z就行了,原因很浅白,因为是求一堆数字和一个数字的绝对值之和,那么这个数字,在这堆数字的中间值的时候,和最小
这样做,整个算法的复杂度是O(n)
1 |
|
D.
暴力地搞
对于一行,把1区间保存下来,1区间是值一段连续为1的区间
例如:
第1行:[2,5], [8,9], [11,12]表示2到5列是1,8到9列是1,11到12列是1
对于一列,也这样保存下来
对于修改一个点(r,c),改变的只有r行,c列,所有重新去保存那些1区间,复杂度是O(n) n是行长,列长
对于查询,就想上,下,左,右,四个方向去找一次
例如上,下方向找,那就是对于 c 这一列,在没一行找到一个1区间是包含c的,如果有1行不包含就退出了
向左,右方向找是一样的,我写了一个类,只实现上下方向找的方法,对于左右找,那就把矩阵转90度就行了,所以有两个矩阵,都是上下方向找
不过代码太长了,呵呵
1 |
|