威风镰鼬

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #Best Cow Fences#

思路求长度不小于L的平均值最大的子区间。可以用前缀和+二分的思想去做，复杂度O(nlogn)。对于每个数减去二分的平均值，并且算出前缀和。那么我们用一个数记录前i个数中总和最小的区间[0,k]，那么只需要判断前i个数最大区间[0,i]-[0,k]是否大于0即可。代码 #include<bi...

二分前缀和

2021-09-14

2 430

题解 | #数学考试#

思路用前缀和去处理[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]的和。重点是这两个区间不相交，我们如果去枚举两个区间的位置肯定会超时的。那么我们可以考虑一个指针从k出发到n-k，移动过程中记录左边区间的最大值，（可能不变）同时我们右边区间是不断变化的，两者...

dp 前缀和

2021-06-24

1 442

题解 | #送分了QAQ#

思路看到楼上有dp做法的，原谅我难以看懂，我是直接暴力过的。前缀和可以O(1)得到答案，只需要进行预处理求1~1e6讨厌的数个数就好了。O(1e6)判断一个数是否讨厌，可以对其每一位模4，每两位模38. 代码 #include<bits/stdc++.h> using namespac...

前缀和

2021-06-16

9 613

题解 | #毒瘤xor#

思路可以用位运算和前缀和的相关知识。要让X异或a[i]求和最大SUM，则SUM的每一位都是1，我们需要求的是X的每一位该取0还是1。我们可以用一个二维数组a[i][j]记录前i个数第j位是1的个数，这样我们就能知道L~R范围内某一位的0多还是1多。运用异或的性质我们知道，在0多的情况下X那一位该取...

前缀和异或位运算

2021-06-12

4 466