CodeForces 1554B

CodeForces 1554B

题目
题目大意：
n个数的数组a，值范围[0,n]，给定一个不大于100的值k，要求找出一对下标i<j，使得f(i,j)= ij-k(ai|aj) 取得最大值。n的数量级为1E5。
题解：
由于a最大值为n，所以(ai|aj)最大值小于2n。把f分为两部分，即ij和k*(ai|aj)这第一第二两部分，则f(i,j)的最大值不会小于这两部分分别可能取到的最大值之差，即(n-1)n-2kn。记为f(n-1,n)。
在f(i,j)的式子里， i⋅j can be O(n^2), but k⋅(ai|aj) is O(n⋅100). 这意味着，n比较大时，ij的增大一定会使f(i,j)增大。
我们可以对遍历进行剪枝。找到这样一个值，当i小于这个值时，f(i,j)一定不会比f(n-1, n)大。如果想让i足够小，则令第一部分的j等于n，第二部分取可能的最小值即ai=an=0时，第二部分=k0=0。也就是in<(n-1)n-k2n，解得i<n-1-2k，即i<=n-2k。因此这部分的i值我们不用遍历了。只需遍历i>n-2k的部分。时间复杂度为O(k^2)。