题目大意
给出一个长度为
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
)
i\times j - k\times(a_i | a_j)
i×j−k×(ai∣aj),其中|
表示or
,
k
k
k是指定参数。
时间限制
1s
数据范围
a i ≤ n ≤ 1 0 5 a_i\le n\le 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_s\times g_s -k\times 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];
}
else
if (f[S] == f[s])
{
if (g[s] < g[S]) g[s] = g[S];
}
else
if (f[S] > g[s]) g[s] = f[S];
if (bz[s])
{
bz[s] = 0;
r++;
q[r] = s;
}
}
}
printf("%lld\n", ans);
}
return 0;
}