首页 > 其他分享 >NOI模拟 排序幻觉

NOI模拟 排序幻觉

时间:2024-05-27 17:11:35浏览次数:30  
标签:ch NOI 取反 else char leq 幻觉 排序 find

涉及知识点:二进制,贪心

题意

给一个数组 \(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

相关文章

  • 七大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、归并排序、快速排序
    以下内容转载自文章1.插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找到已排序元素中小于等于tem的元素5.tem插入到该元素的后面,如果已排序所有元......
  • Python小技巧:一种字符串的排序方式
    1.排序方式假设有一个序列,数据为:['n1','n2','n10','n11','n21','n3','n13','n20','n23'],排序后需要达到这个效果:['n1','n2','n3','n10','......
  • 拓扑排序问题
    拓扑排序的英文是Topologicalsorting,要解决的问题是,给定一个包含\(n\)个节点的有向图\(G\),给出所有节点的一种排列,使得对于图\(G\)中的任意一条有向边\((u,v)\),\(u\)在排列中都出现在\(v\)的前面,这样的排列称为图\(G\)的拓扑排序。从拓扑排序的定义中,可以得出两个结论:若图\(G\)......
  • 设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序:先看数据项k1,k1
    题目:设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序:先看数据项k1,k1值小的元素在前,大的在后;在k1值相同的情况下,再看k2,k2值小的在前,大的在后。满足这种要求的排序方法是()A.先按k1进行直接插入排序,再按k2进行简单选择排序B.先按k2进行直接插入排序,再按k1进行......
  • PHP 多维数组排序
    PHP封装多维数组排序函数1functionallKeySort(&$array){2if(!is_array($array)){3return;4}5$keys=array_keys($array);6sort($keys);7$sortedArray=array();8foreach($keysas$key){9$sortedArray[$......
  • CSP历年复赛题-P1055 [NOIP2008 普及组] ISBN 号码
    原题链接:https://www.luogu.com.cn/problem/P1055题意解读:验证ISBN最后一位是否正确。解题思路:直接模拟,不多说,上代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;intcode=0;intcnt=0;for(inti......
  • 【c++提高组】津津的储蓄计划(NOIP2004)
    题目描述津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300元钱,津津会预算这个月的花销,并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末她会加上 20%还给津津。因此津津制定了一个储蓄计划:每个月的......
  • CSP历年复赛题-P1096 [NOIP2007 普及组] Hanoi 双塔问题
    原题链接:https://www.luogu.com.cn/problem/P1096题意解读:汉诺双塔的移动次数,与经典汉诺塔的区间在于同一个尺寸盘子有两个。解题思路:可以直接用经典汉诺塔方法来计算,双塔的结果就最终乘以2即可。首先想到的是递归,但是由于数据量n最大200,递归会超时,但是50%的样例应该没问题,先......
  • Delphi CxGrid/CxDBTreeList等将排序筛选条件改为中文方法
    Delphi CxGrid/CxDBTreeList等将排序筛选条件改为中文方法一、加入cxLocalizer控件二、在FormCreate里加入以下代码procedureTForm1.FormCreate(Sender:TObject);begin cxLocalizer1.LoadFromResource(HInstance); cxLocalizer1.Language:='中文(简体,中国)';......
  • # [NOIP2014 提高组] 生活大爆炸版石头剪刀布
    传送锚点:https://www.luogu.com.cn/problem/P1328题目背景NOIP2014提高组D1T1题目描述石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头......