涉及知识点:二进制,贪心
题意
给一个数组 \(a[1], a[2], \ldots, a[n]\),选择一个数 \(b\),如果 \(b\) 满足:
\[(a[1]\oplus b) \leq (a[2]\oplus b) \leq \ldots \leq (a[n]\oplus b) \]则称 \(b\) 是数组 \(a\) 的幻数。
有 \(q\) 次询问,每次永久修改一个数。对于原数组与每次询问后输出最小的幻数,不存在幻数输出 \(-1\)。
\(n,q\leq 10^6,a[i]\leq 2^{30}\)。
思路
对于这种按位异或的题目,可以去尝试每位单独考虑。
对于 \(a,b\),称它们二进制下从左往右第一个不同的位为第 \(k\) 位(以下“位”均指二进制下)。
- \(a>b\)时,我们同时将 \(a,b\) 第 \(k\) 位左边的位取反不会影响它们的大小关系,因为第 \(k\) 位左边它们两都一样,取反不会影响大小关系;而如果将第 \(k\) 位右边的位取反也没用,因为第 \(k\) 位已经不一样了,判断大小时是从高位到低位比的。所以只能把第 \(k\) 位取反才能反转它们的大小关系。
- \(a=b\) 时,无论同时取反哪一位,\(a\) 都永远等于 \(b\)。
- \(a<b\) 时,同理取反第 \(k\) 位左边或右边的位都不会影响它们之间的大小关系,唯有取反第 \(k\) 位会反转它们的大小关系。
因此我们对于所有 \((a_{i-1},a_i)\) 求出它们的 \(k\),如果 \(a_{i-1}<a_i\) 那么第 \(k\) 位不能取反,如果 \(a_{i-1}>a_i\) 那么第 \(k\) 位必须取反,如果有冲突说明无解,否则,必须取反的位为 \(1\),其余位为 \(0\) 的二进制数便是最小的幻数。
如何处理修改呢?一个数的贡献只与旁边的两个数有关,分开记录“必须取反”与“不能取反”,一个数的做出贡献在第 \(k\) 处 +1
,撤销时在第 \(k\) 处 -1
,每次只需要 \(O(\log n)\) 就可以扫描是否有冲突并求出答案,具体看代码。
代码
#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
static char ch[1<<20],*l,*r;
return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
static char wtbuff[20];
static int wtptr;
if(x==0){
putchar('0');
}
else{
if(x<0){x=-x;putchar('-');}
wtptr=0;
while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
while(wtptr--) putchar(wtbuff[wtptr]);
}
if(endch!='\0') putchar(endch);
}
typedef long long LL;
const int MAXN=1e6+5,MAXB=32;
int n,q;
LL a[MAXN];
int forbid[MAXB],active[MAXB];
inline int find_first_diff(LL x,LL y){
int res=-1;
LL cmp=1;
for(int i=0;i<=30;i++,cmp<<=1){
if((x&cmp)!=(y&cmp)) res=i;
}
return res;
}
inline void check(){
for(int i=0;i<=30;i++){
if(active[i] && forbid[i]){
puts("-1");
return;
}
}
LL res=0,cmp=1;
for(int i=0;i<=30;i++,cmp<<=1){
if(active[i]) res+=cmp;
}
wt(res,'\n');
}
int main(){
rd(n);
for(int i=1;i<=n;i++){
rd(a[i]);
}
for(int i=2;i<=n;i++){
if(a[i]>a[i-1]) forbid[find_first_diff(a[i],a[i-1])]++;
else if(a[i]<a[i-1]) active[find_first_diff(a[i],a[i-1])]++;
}
check();
rd(q);
for(int i=1,p;i<=q;i++){
LL v;
rd(p);rd(v);
if(p!=1){
if(a[p]>a[p-1]) forbid[find_first_diff(a[p],a[p-1])]--;
else if(a[p]<a[p-1]) active[find_first_diff(a[p],a[p-1])]--;
}
if(p!=n){
if(a[p+1]>a[p]) forbid[find_first_diff(a[p+1],a[p])]--;
else if(a[p+1]<a[p]) active[find_first_diff(a[p+1],a[p])]--;
}
a[p]=v;
if(p!=1){
if(a[p]>a[p-1]) forbid[find_first_diff(a[p],a[p-1])]++;
else if(a[p]<a[p-1]) active[find_first_diff(a[p],a[p-1])]++;
}
if(p!=n){
if(a[p+1]>a[p]) forbid[find_first_diff(a[p+1],a[p])]++;
else if(a[p+1]<a[p]) active[find_first_diff(a[p+1],a[p])]++;
}
check();
}
return 0;
}
标签:ch,NOI,取反,else,char,leq,幻觉,排序,find
From: https://www.cnblogs.com/SkyNet-PKN/p/18216009