ABC249G
题意：
给定\(n\)张牌，每张牌正面是\(a_i\)，背面是\(b_i\)，要求从里面任选最少一张牌，使得证明的数字异或和不超过\(m\)的同时，背面数字异或和最大。
\(n\leq 2000,m,a_i,b_i\leq 2^{30}\)
题解：
对于两张牌\((a,b)\)和\((c,d)\)
和另外两张牌\((a,b)\)和\((a\oplus c,b\oplus d)\)是完全等价的。
可以互相异或一下发现所有情况都相同。
那么根据线性基理论，可以发现在互相异或之后，最多只有\(30\)张牌正面仍然不为零，且不能被其他牌表示出来，其他牌都可以通过异或让正面为零。
对于一张牌\((0,x)\)来说，这个\(x\)可以无条件使用。
那么这些\(x\)可以放入另一个线性基\(B\)中等着用来拼凑出最大值。
对于不能被其他数字表示出来的\(a\)，可以放进线性基\(A\)中，用来拼凑限制\(m\)，同时每一位有一个对应的异或值\(b\)，表示选用了这个\(a\)就必须异或上一个\(b\)（背面的数字）。
然后对于限制\(m\)，可以先强制要求\(A\)中异或和\(m\)的\(k\)位之前的部分相同，而第\(k\)位刚好\(m\)是\(1\)，我们的异或值是\(0\)，这样低位上就可以随意选择了。
这时候再把低位上的\(b\)和\(B\)中的值放入\(C\)中，来获得一个最大值。
但是按上面的方法，只能得到所有小于\(m\)的答案。
一个\(trick\)是提前把\(m+1\)，这样就完美了。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
struct line
{
int p[30];
void clear()
{
for(int k=0;k<=29;++k) p[k]=0;
}
bool insert(int x)
{
for(int k=29;k>=0;--k) if((x>>k)&1)
{
if(!p[k])
{
p[k]=x;return 1;
}
x^=p[k];
}
return 0;
}
int query(int x)
{
for(int k=29;k>=0;--k) x=max(x,x^p[k]);
return x;
}
}A,B;
inline void main()
{
int n,m;
cin>>n>>m;
++m;
vector<int> a(30,0),b(30,0);
auto insert=[&](int &x,int &y) -> bool
{
for(int k=29;k>=0;--k) if((x>>k)&1)
{
if(a[k]) x^=a[k],y^=b[k];
else
{
a[k]=x;b[k]=y;
return 1;
}
}
return 0;
};
bool flag=0;
B.clear();
for(int i=1;i<=n;++i)
{
int x,y;
cin>>x>>y;
if(!insert(x,y)) {B.insert(y),flag=1;}
}
for(int k=0;k<30;++k)
{
if(!a[k]) continue;
if(a[k]>=m&&!flag)
{
cout<<"-1\n";
return;
}
break;
}
int ans=0;
for(int k=30;k>=0;--k) if((m>>k)&1)
{
int t1=0,t2=0;
for(int i=29;i>k;--i)
{
int b1=(m>>i)&1,b2=(t1>>i)&1;
if(b1^b2) t1^=a[i],t2^=b[i];
}
if((t1>>k)&1) t1^=a[k],t2^=b[k];
//cout<<k<<' '<<t1<<' '<<t2<<"!!"<<endl;
if((t1>>k)&1||t1>=m) continue;
line C=B;
for(int i=0;i<k;++i) C.insert(b[i]);
ans=max(ans,C.query(t2));
}
cout<<ans<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC238E
题意：
有一个长度为\(n\)的序列\(a\)，有\(m\)个已知信息，每个形如\(a[l]\sim a[r]\)的和是已知的，最后能不能推出\(a[1]\sim a[n]\)的和？
\(n,m\leq 2*10^5\)
题解：
区间和可以转化成前缀和作差，那么\(a[l]\sim~a[r]\)的和的信息等价于知道了\(b[r]-b[l-1]\)的值，其中\(b\)是前缀和数组。
一开始的条件只有\(b[0]=0\)，最后要知道\(b[n]\)的值。
那么每个信息，我们可以得知\(l-1\)和\(r\)是可以互相推导的，所以最后只要\(0\)和\(n\)联通，就可以得到\(a[1]\sim a[n]\)的和。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<int> f(n+1);
for(int i=1;i<=n;++i) f[i]=i;
function<int(int)> find=[&](int k) -> int
{
return f[k]==k?k:f[k]=find(f[k]);
};
for(int i=1;i<=m;++i)
{
int l,r;cin>>l>>r;
f[find(l-1)]=find(r);
}
if(find(0)==find(n)) cout<<"Yes\n";
else cout<<"No\n";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC128E
题意：
给定有\(n\)个位置\(x_i\)在\([st_i-0.5,ed_i-0.5]\)时间内施工，有\(m\)个人，第\(i\)个人从位置\(0\)，时刻\(d_i\)开始往右走，一秒走一米，遇到第一个障碍停下，问每个人会走多少米？不会停下输出\(-1\)
\(n,m\leq 2*10^5\)，其他数字小于等于\(10^9\)
题解：
离散化后线段树很显然，但是这样写不优雅。
先把施工时间转化到起点对应的出发时间去，然后按位置\(x_i\)从小到大排序，把每个人的出发时间塞到一个\(set\)里。
对于一个施工时间，二分找到对应的在这段时间内出发的人，把它们的答案改掉之后从\(set\)里删掉。
这样每个人只被删除一次。既不用离散化也不用数据结构
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
struct node
{
int l,r,x;
bool operator < (const node &t) const
{
return x<t.x;
}
};
vector<node> a(n);
for(int i=0;i<n;++i)
{
int l,r,x;
cin>>l>>r>>x;
l-=x; r=r-x-1;
a[i]=(node){l,r,x};
}
sort(a.begin(),a.end());
typedef pair<int,int> pr;
set<pr> q;
vector<int> ans(m,-1);
for(int i=0;i<m;++i)
{
int x;cin>>x;
q.insert(pr(x,i));
}
for(int i=0;i<n;++i)
{
auto l=q.lower_bound(pr(a[i].l,-inf));
auto r=q.upper_bound(pr(a[i].r,inf));
if(r==q.begin()||l==q.end()) continue;
while(l!=r)
{
auto tmp=*l;
auto pre=l++;
q.erase(pre);
ans[tmp.second]=a[i].x;
}
}
for(int i=0;i<m;++i) cout<<ans[i]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/