首页 > 代码库 > bzoj 2460: [BeiJing2011]元素

bzoj 2460: [BeiJing2011]元素

2024-09-05 02:08:20   215人阅读

线性基%%%%（说的那么玄乎，就是数学学的基底（只不过垃圾高中数学只学了2,3维，那么扩充到n维是一样的））

对于线性基的构造：

因为给出一个数列，由这个数列可以构造出来的数，肯定可以由线性基构造出来，且数都一样。

为什么呢？因为线性基正是由原来的这些数构造出来的，而且我们构造每个数最高位（二进制）都不相同，即这些数就包含了所有能出现二进制位。

因为这些个数是由原数xor出来的，肯定是能xor回去的（2333，我太弱，只能这样证明）

可以证明的是，线性基的真子集是不会出现0的。

然后，对于最大值的构造，以及这个题什么最大和（这个题最大和是用的贪心策略，证明不会，看神犇说用拟阵（不想看））都拿着线性基是使劲往最高位上加1就好了

（1LL<<i）（不带LL就错，真坑爹）

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 inline LL ra()
 7 {
 8     LL x=0,f=1; char ch=getchar();
 9     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
10     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
11     return x*f;
12 }
13 LL p[100];
14 struct node{LL val;LL num;}a[N];
15 bool cmp(node a, node b){return a.val>b.val;}
16 int main()
17 {
18     LL n=(int)ra(); LL ans=0;
19     for (int i=1; i<=n; i++)
20         a[i].num=ra(),a[i].val=(int)ra();
21     sort(a+1,a+n+1,cmp);
22     for (int i=1; i<=n; i++)
23     {
24         for (int j=65; j>=0; j--)
25             if ((1LL<<j)&a[i].num)
26             {
27                 if (!p[j]) {p[j]=a[i].num; break;}
28                 else a[i].num^=p[j];
29             }
30         if (a[i].num) ans+=a[i].val;
31     }
32     cout<<ans;
33     return 0;
34 }

 

bzoj 2460: [BeiJing2011]元素


联系
我们