[ABC236F] Spices
有 \(2 ^ N - 1\) 个数字，分别编号为 \(1, 2, \dots, 2 ^ N - 1\)，想获得编号为 \(i\) 的数字需要支付 \(c_i\) 的代价。
现在你可以从这些数字中选出一些数，使得你可以通过你选择的某些数的编号的异或和来表示出 \([1, 2 ^ N - 1]\) 中的所有数。
请你求出最少需要支付多少代价。
线性基的基本贪心，按照\(c_i\)从小到大排序后，依次插入，可以插入的就是加入答案中的数。
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=5e5+5;
const int M=2e6+5;
struct Base{
ll p[35];
bool ins(ll x){
fd(i,31,0) {
if ((x>>i)&1) {
if (!p[i]) {
p[i]=x;
return 1;
}
else x^=p[i];
}
}
return 0;
}
};
Base t;
ll n;
struct node{
ll i,c;
};
node a[N];
int main(){
// freopen("data.in","r",stdin);
scanf("%lld",&n);
n=(1<<n)-1;
fo(i,1,n) {
scanf("%lld",&a[i].c);
a[i].i=i;
}
sort(a+1,a+n+1,[](node a,node b){
return a.c<b.c;
});
ll ans=0;
fo(i,1,n) {
if (t.ins(a[i].i)) ans+=a[i].c;
}
printf("%lld",ans);
return 0;
}
[WC2011] 最大XOR和路径
给出所有边权，问从1-n的最大XOR和路径是多少。
本质上就是随便选取一条路径的xor和，以及其它所有的环，全部丢到线性基里面。
然后就是贪心取最大值。
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=5e5+5;
const int M=2e6+5;
const ll mo=1e9+7;
struct Base{
ll p[100];
ll rank=0;
bool ins(ll x){
fd(i,60,0) {
if ((x>>i)&1) {
if (!p[i]) {
p[i]=x;
rank++;
return 1;
}
else x^=p[i];
}
}
return 0;
}
};
Base t;
ll head[N],nex[M*2],to[M*2],tot=1;
ll w[M*2],val[N];
bool vis[N];
ll n,m,x,y,z;
void add(ll x,ll y,ll z){
to[++tot]=y; nex[tot]=head[x]; head[x]=tot; w[tot]=z;
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=nex[i]) {
int v=to[i];
if (vis[v]) {
t.ins(w[i]^val[v]^val[x]);
}
else {
val[v]=val[x]^w[i];
dfs(v);
}
}
}
int main(){
// freopen("data.in","r",stdin);
scanf("%lld %lld",&n,&m);
fo(i,1,m) {
scanf("%lld %lld %lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1);
ll ans=val[n];
fd(i,60,0) ans=max(ans, ans^t.p[i]);
printf("%lld",ans);
return 0;
}
P3292 [SCOI2016] 幸运数字
给定一棵树，每个节点有一个权值\(a_i\)，每次询问从x到y路径上所有点\(a_i\)组成的线性基。
每个点维护一个从它到根的线性基，并用一个vector记录这些点，计算当前点的线性基时，首先将自己的点插入，然后将父亲的线性基插入即可。
每次询问的时候，x,y的线性基中深度小于lca的全部插到一个新的线性基即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<iostream>
#include<queue>
#include<set>
//#define A puts("YES")
//#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
typedef long long ll;
//typedef __int128 i128;
typedef double db;
const int N=1e5+5;
int f[21][N],d[N],n,x,y,q;
vector<int> e[N],v[N];
ll a[N];
struct lb{
lb(){
fo(i,0,60) p[i]=0;
}
ll p[61];
bool ins(ll x){
fd(i,60,0) {
if ((x>>i)&1) {
if (p[i]) x^=p[i];
else {
p[i]=x;
return 1;
}
}
}
return 0;
}
ll askmax() {
ll ans=0;
fd(i,60,0) ans=max(ans, ans^p[i]);
return ans;
}
};
vector<int> get(vector<int> t,int x){
vector<int> temp;
temp.clear();
lb r;
if (r.ins(a[x])) temp.push_back(x);
for (int i:t) if (r.ins(a[i])) temp.push_back(i);
return temp;
}
void dfs(int x,int y){
v[x]=get(v[y], x);
for (int v:e[x]) {
if (v==y) continue;
f[0][v]=x;
d[v]=d[x]+1;
dfs(v,x);
}
}
int lca(int x,int y){
if (d[x]<d[y]) swap(x,y);
fd(k,20,0) if (d[f[k][x]]>=d[y]) x=f[k][x];
fd(k,20,0) {
if (f[k][x]^f[k][y]) x=f[k][x],y=f[k][y];
}
if (x!=y) return f[0][x];
return x;
}
void work(int x,int y){
lb t;
int l=lca(x,y);
for (int i:v[x]) if (d[i]>=d[l]) t.ins(a[i]);
for (int i:v[y]) if (d[i]>=d[l]) t.ins(a[i]);
cout<<t.askmax()<<"\n";
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
fo(i,1,n) cin>>a[i];
fo(i,1,n-1) {
cin>>x>>y;
e[x].emplace_back(y);
e[y].emplace_back(x);
}
f[0][1]=1;
v[1].emplace_back(1);
dfs(1,0);
fo(j,1,20) fo(i,1,n) f[j][i]=f[j-1][f[j-1][i]];
while (q--) {
cin>>x>>y;
work(x,y);
}
return 0;
}
[ABC223H] Xor Query
题面翻译
- 给定一个长度为 \(N\) 正整数序列 \(A\)，\(Q\) 次询问。
- 每次询问给出三个正整数 \(L\)、\(R\)、\(X\)，请你判断能否从原序列 \(A_L\)，\(A_{L+1}\)，... ,\(A_R\) 中选出若干个数使其异或和为 \(X\)。
首先需要注意的是，线性基的合并是n(logn)^2，而且这个log是60的级别，所以是不太能像上一道题一样，维护一个vector的，然后暴力插入的。
我们仍然像上一道题一样，记录一个1-i组成的线性基，并且其中的数尽量靠右。
具体来说，我们复制前一个数的线性基，然后我们插入\(a_i\)，使用一个贪心的策略
如果当前的数在i这一位有1，并且\(p_i\)不为0，则比较id的大小，让大的放在这一位，小的继续往后做，
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll inf = 1ll << 60;
const int N = 5e5 + 10;
struct lb {
ll p[61], id[61];
lb() {
memset(p, 0, sizeof(p));
}
void clr() {
memset(p, 0, sizeof(p));
}
void ins(ll x, ll y) {
fd(i, 60, 0) {
if ((x >> i) & 1) {
if (!p[i]) {
p[i] = x; id[i] = y;
return;
}
else {
if (y > id[i]) {
swap(x, p[i]); swap(y, id[i]);
}
x ^= p[i];
}
}
}
}
bool ask(ll x, ll y) {
fd(i, 60, 0) {
if ((x >> i) & 1) {
if (!p[i] || id[i] < y) return 0;
x ^= p[i];
}
}
return !x;
}
};
lb t[N];
ll n, q, a[N], l, r, x;
void solve()
{
cin >> n >> q;
fo(i, 1, n) cin >> a[i];
fo(i, 1, n) {
t[i] = t[i - 1];
t[i].ins(a[i], i);
}
while (q--) {
cin >> l >> r >> x;
if (t[r].ask(x, l)) cout << "Yes" << "\n";
else cout << "No" << "\n";
}
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}