数列为 [0, 1, 2, ··· k-1, x, x, x, x] 的形式，再扣下细节（ x=k-1， k<n 等 ）
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
| #include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=15;
int main()
{
int _;
cin>>_;
while (_--)
{
int n,k,x;
cin>>n>>k>>x;
if(x<k-1||n<k)
{
cout<<"-1"<<endl;
}else if(x>=k+1)
{
cout<<k*(k-1)/2+(n-k)*(x)<<endl;
}else
{
cout<<k*(k-1)/2+(n-k)*(k-1)<<endl;
}
}
return 0;
}
|
- 按位或
| ：类比或， 0|0=0, 0|1=1, 1|1=1
- 按位异或
^ ：该位不同是1，否则是0， 0^1=1, 0^0=0, 1^1=0
先把数组 $b$ 全或起来得到 $x$ ，此时的 $x$ 二进制中的 1 尽可能的多， 而数组 $b$ 中元素无法改变数组 $a$ 的较高位（这里的较高位指的是比 $x$ 的最高位还高的位）
再分两类，数组 $a$ 大小如果是奇数的话，对 $a$ 中每个元素用 $x$ 按位或后再按位异或为最大值，不进行按位或是最小值
如果 $a$ 的大小为偶数的话，对 $a$ 每个元素按位或后再异或会在结尾出现很多 0， 即为最小值，不按位或即为最大值
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
| #include<iostream>
using namespace std;
const int N=2e5+10;
int a[N];
int b[N];
int main()
{
int _;
cin>>_;
while (_--)
{
int n,m;
cin>>n>>m;
int mx=0,mn=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int x=0;
for(int i=1;i<=m;i++)
{
cin>>b[i];
x|=b[i];
}
for(int i=1;i<=n;i++)
{
mx^=a[i];
mn^=(a[i]|x);
}
if(mx<mn)
{
swap(mx,mn);
}
cout<<mn<<' '<<mx<<endl;
}
return 0;
}
|
如图，易知 $b$ （绿色部分） 关于左上右下对角线对称，所以包含元素 $x$ 的矩形必定是一个正方形。对于 $b$ 中某元素 $x$ ，可以找到一个最左边的 $x$ 和最右边的x，设两者的横向距离为 $L$ ，则包含所有该元素的最小矩形（正方形）宽和高之和为 $L*2$
用 $l[i]$ 和 $r[i]$ 分别记录i的最左边和最右边，则对于某元素i，该正方形宽高之和为 (r[i]-l[i]+1)*2 注：该元素得在a中出现，否则直接输出0
用 $now$ 记录可能出现在 $b$ 的元素， $now$ 从 $1$ 开始遍历，对于第一列， b[i,1]=min(a[i],a[1]) , 所以对于当前的 $now$ ，若 now<=a[i] ，则令 $l[now]=i$ ，再 now++ 继续遍历。 $r[i]$ 的话从 $a[n]$ 到 $a[i]$ 遍历
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
| #include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int l[N];
int r[N];
bool pd[N];
int main()
{
int _;
cin>>_;
while (_--)
{
memset(pd,false,sizeof(pd));
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pd[a[i]]=true;
}
int now=1;
for(int i=1;i<=n;i++)
{
while (now<=a[i])
{
l[now++]=i;
}
}
now=1;
for(int i=n;i>=1;i--)
{
while (now<=a[i])
{
r[now++]=i;
}
}
for(int i=1;i<=k;i++)
{
if(!pd[i])
{
cout<<"0"<<' ';
}else
{
cout<<(r[i]-l[i]+1)*2<<' ';
}
}
cout<<endl;
}
return 0;
}
|
