题解：CF1554B Cobb

Jayfeather2012 · 2025-04-09 18:47:58 · 题解

思路

考虑暴力，每次询问暴力枚举 i 和 j（i>j），找到所有情况算出结果，比较最大值。
这种做法时间复杂度 O(n^2)，显然会超时，考虑优化：
对于每一次枚举 i 的循环，如果 i\times(i-1)-k\times a_i\le ans，那么就不进行枚举 j 更新最大值。
原因：i\times(i-1) 是 i\times j 的最大值，因为一个数和另一个数进行按位或运算结果肯定比原数大，所以 k\times a_i 是 k\times(a_i|a_j) 的最小值，最大值减最小值肯定是最大值，最大值都不比 ans 大，就没必要考虑这种情况了。
AC 记录。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
//100000*100000>2000000000，记得开long long
int t,n,k,a[100005];
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;++i)cin>>a[i];
        int ans=-1e18;
        //初始化最小值
        for(int i=n;i>=2;--i){
            //从大到小枚举更快找到最大值，减少后面的枚举，节省时间
            if(i*(i-1)-a[i]*k<=ans)continue;
            //如果最大值都不比ans大，没必要更新最大值
            for(int j=i-1;j>=1;--j)ans=max(ans,i*j-k*(a[i]|a[j]));
            //有必要更新，根据题意更新最大值
        }
        cout<<ans<<"\n";
    }
    return 0;
}