因为暑假一周四练,精力有限,只补题,会了的题不再解释了。

1011

思路:因为存在负数,我们需要对每个位置考虑四个值,负数最大/小值,正数最大/小值。
对于转移,我用一个例子给你解释。比如值A的所在下标是6(110),那么A就能一步转移到4(100),2(010),两步转移到0(000)
再来一个,对于7(111)它能一步转移到(110,101,011),两步,三步转移同理。如此一来我们就知道了,可以按照下标值二进制表示的一的数量进行排序,从高到低维护计算出每个下标的四个值。
进而每个下标算最大的C[i],又由于题目给定的c[k] (i&j>=k),得到从大到小的ans计算,ans每次加都是最大值。题目还有一些小细节的处理,在代码里面解释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//team: lots of balloons
//author: TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=998244353;
const ll maxn=3e5+7;
const double pi=acos(-1);
using namespace std;
int _,n,m;
ll yi[maxn];
ll id[maxn];
ll a[maxn],b[maxn],a1[maxn],b1[maxn];
ll c[maxn];
ll ans;
int cal(int n)
{
int res= 0;
while(n)
{
if(n&1)
{
res++;
}
n>>=1;
}
return res;
}
void init()
{
for (int i=0;i<=300000;i++)
{
yi[i]=cal(i);
}
}
bool cmp(int x,int y)//大的放到前面去
{
return yi[x]>yi[y];
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("mine.out","w",stdout);
//统计一的个数
init();
scanf("%d",&_);
for(;_;_--)
{
//ans=0;
scanf("%d",&n);

for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
a1[i]=a[i];
}
for(int i=0;i<n;i++)
{
scanf("%lld",&b[i]);
b1[i]=b[i];
}
for(int i=0;i<n;i++)
{
id[i]=i;
}
sort(id,id+n,cmp);
for(int i=0;i<n;i++)
{
//4选1
c[id[i]]=max(a[id[i]]*b1[id[i]],a[id[i]]*b[id[i]]);
c[id[i]]=max(c[id[i]],a1[id[i]]*b[id[i]]);
c[id[i]]=max(c[id[i]],a1[id[i]]*b1[id[i]]);
// c[id[i]]=max(1ll*a1[id[i]]*b[id[i]],max(1ll*a[id[i]]*b1[id[i]],max(1ll*a[id[i]]*b[id[i]],1ll*a1[id[i]]*b1[id[i]])));
//给id[i] 的一数量进行减少一个的操作
//因为按数量递增,递减完后,后面的再接着递减就好
//这样就遍历了所有子集
for(int j=1;j<=id[i];j=j*2)
{
if(id[i]&j)// id[i]这个位置上有1 , 就消掉这个1
{
a[id[i]-j] = max(a[id[i]-j],a[id[i]] ) ;
a1[id[i]-j] = min(a1[id[i]-j],a1[id[i]] ) ;
b[id[i]-j] = max(b[id[i]-j],b[id[i]] ) ;
b1[id[i]-j] = min(b1[id[i]-j],b1[id[i]] ) ;
}
}
}
ll mx=c[n-1];//有负数!!!别用0
ans=(c[n-1]%mod+mod)%mod;
for(int i=n-2;i>=0;i--)
{
mx=max(c[i],mx);
ans=((ans+mx)%mod+mod)%mod;

}
printf("%lld\n",((ans)%mod+mod)%mod);
// cout<<(ans%mod+mod)%mod<<endl;
}
return 0;
}