CF1554B-Cobb

2022-04-11 题解

题目大意：给出一个长度为 $n$ 的数列 $a[]$ 和一个数字k，找出两个不同的数 $i,j$ ，使得 $f(i,j)=i \times j - k \times (a[i]|a[j])$ 最大。

已知 $a[i]|a[j]\leq 2 \times n$ ，则 $k \times (a[i]|a[j])$ 的最大值为 $2\times k \times n$ 。若 $i \times j$ 与 $(n-1) \times n$ 的差值大于 $2 \times k \times n$ ， $f(i,j) < f(n-1,n)$ 恒成立。所以只需要找满足 $(n-1)\times n - i \times j \leq 2\times k \times n$ 的 $i,j$ 就可以了。由于题目数据范围较小，可以过。

#include <bits/stdc++.h>
using namespace std;
long long a[100005];
int main()
{
    int _;
    long long n, k;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%lld%lld", &n, &k);
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        long long i, j, t1 = n * (n - 1), t2 = 2 * k * n, res = -1e18;
        for (j = n; j && t1 - j * (j - 1) <= t2; j--)
            for (i = j - 1; i && t1 - j * i <= t2; i--)
                res = max(res, i * j - k * (a[i] | a[j]));
        printf("%lld\n", res);
    }
    return 0;
}