题解：CF1554B Cobb

思路

考虑暴力，每次询问暴力枚举

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 记录。
具体细节看代码吧！

代码

CPP

#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;
}

文章操作

思路

代码

相关推荐

评论

题解：CF1554B Cobb