Codeforces Round #735 (Div. 2) B. Cobb

Codeforces Round #735 (Div. 2) B. Cobb

题目大意

给出一个长度为 n n n的数组 a 1 , a 2 , ⋯ , a n a_1,a_2,cdots,a_n a1​,a2​,⋯,an​
求 i × j − k × ( a i ∣ a j ) itimes j - ktimes(a_i | a_j) i×j−k×(ai​∣aj​)，其中|表示or， k k k是指定参数。

时间限制

1s

数据范围

a i ≤ n ≤ 1 0 5 a_ile nle 10^5 ai​≤n≤105

题解

两个数做or运算，十分不好处理，并不能在二叉树上找出对应的数。
也很难分离出与不与 j j j只与 i i i直接关联的部分。

换一种思路，假设已经确定了 a i ∣ a j a_i | a_j ai​∣aj​，那么显然就要找到最大两个 i , j i,j i,j，而 a i a_i ai​并不是很大，于是就可以按照这个思路来处理。

不妨设 f s f_s fs​表示满足 a i & s = a i a_i & s = a_i ai​&s=ai​的最大的 i i i。
设 g s g_s gs​表示满足 a i & s = a i a_i & s = a_i ai​&s=ai​的最大的 i i i。
那么转移就可以用一个 b f s bfs bfs来实现。
答案就是 f s × g s − k × s f_stimes g_s -ktimes s fs​×gs​−k×s

Code

//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <map>
#define ll long long
#define G getchar
using namespace std;int read()
{char ch;for(ch = G();ch < '0' || ch > '9';ch = G());int n = 0;for(;'0' <= ch && ch <= '9';ch = G())n = (n<<1)+(n<<3)+ch-48;return n;
}void write(int x)
{if (x > 9){write(x / 10);putchar(x % 10 + 48);}else putchar(x + 48);
}const int N = 131092;int n , m , k , a[N] , q[N] , f[N] , g[N];
int z[18] , s , K , l , r , S;
bool bz[N];
ll ans , tmp;int main()
{//freopen("b.in","r",stdin);//freopen("e.out","w",stdout);z[0] = 1;for (int i = 1 ; i < 18 ; i++)z[i] = z[i - 1] << 1;for (int T = read() ; T ; T--){ans = -1152921504606846976;n = read();K = read();for (k = 0 ; z[k] <= n ; k++);m = z[k];for (int i = 0 ; i < m ; i++){f[i] = g[i] = 0;bz[i] = 1;}for (int i = 1 ; i <= n ; i++){a[i] = read();if (f[a[i]] == 0) f[a[i]] = i; else{g[a[i]] = f[a[i]];f[a[i]] = i;}}l = 0;r = 1;q[1] = 0;for ( ; l < r ; ){l++;S = q[l];if (g[S]){tmp = f[S];tmp = tmp * g[S];tmp = tmp - (ll) K * S;ans = max(ans , tmp);}for (int i = 0 ; i < k ; i++){if (z[i] & S) continue;s = S | z[i];if (f[S] > f[s]){g[s] = f[s];f[s] = f[S];if (g[S] > g[s]) g[s] = g[S];}elseif (f[S] == f[s]){if (g[s] < g[S]) g[s] = g[S];}elseif (f[S] > g[s]) g[s] = f[S];if (bz[s]){bz[s] = 0;r++;q[r] = s;}}}printf("%lldn", ans);}return 0;
}