• 2022年10月中旬刷题记录

    在这里插入图片描述

    cf826 div3G

    状压，分组背包

    #include
using namespace std;
const int N=1e4+10;
const int M=1<<6;
int f[M],n,m,T,a[M],b[N],ren,car[N],sb,t[M],k;
vector<int>g[N];
int d[7][N];
void bfs(int u,int o=0){
    for(int i=1;i<=n;i++)d[o][i]=-1;
    d[o][u]=0;
    queue<int>q;
    q.push(u);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto j:g[u]){
            if(d[o][j]==-1)d[o][j]=d[o][u]+1,q.push(j);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)g[i].clear();
        while(m--){
            int a,b;
            cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        cin>>ren;
        for(int i=1;i<=ren;i++)cin>>b[i],car[i]=1;
        cin>>k;
        for(int i=1;i<=k;i++){
            int x;
            cin>>x;
            car[x]=0;
            a[i]=b[x];
        }
        bfs(1);
        sort(a+1,a+1+k,[&](int i,int j){
            return d[0][i]<d[0][j];
        });
        for(int i=1;i<=k;i++)bfs(a[i],i);
        set<int>S;
        memset(f,0,sizeof f);
        f[0]=1;
        for(int i=1;i<=ren;i++){
            if(car[i]==0)continue;
            for(int j=1;j<(1<<k);j++){
                vector<int>v;
                for(int x=0;x<k;x++){
                    if(j>>x&1)v.push_back(x+1);
                }
                int s=d[0][a[v[0]]];
                for(int i=1;i<v.size();i++)s+=d[v[i-1]][a[v[i]]];
                s+=d[v.back()][b[i]];
                t[j]=s==d[0][b[i]];
            }
            for(int j=(1<<k)-1;j;j--){
                for(int k=j;k;k=(k-1)&j){
                    f[j]|=f[j^k]&t[k];
                    if(f[j])S.insert(j);
                }
            }
        }
        int ans=0;
        for(int i=1;i<(1<<k);i++){
            if(f[i])ans=max(ans,__builtin_popcount(i));
        }
        // int ans=0;
        // for(auto x:S)ans=max(ans,__builtin_popcount(x));
        cout<<k-ans<<'\n';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77

    牛客练习赛89

    #include
using namespace std;
#define INF 1e9
const int N =220*220,M=N*10;
int h[N],e[M],f[M],ne[M],idx,d[N],cur[N],q[N];
int n,m,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()  // 创建分层图
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;  // 没有增广路
}

int find(int u, int limit)  // 在残留网络中增广
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;  // 当前弧优化
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}
// int vis[N];
// void dfs(int u){
//     vis[u]=1;
//     for(int i=h[u];~i;i=ne[i]){
//         if(f[i]&&!vis[e[i]])
//         dfs(e[i]);
//     }
// }
int xx[]={1,-1,0,0};
int yy[]={0,0,1,-1};
int st[220][220];
signed main(){
    memset(h,-1,sizeof h);
    int c;
    cin>>n>>m>>c;
    S=0;
    vector id(n,vector<int>(n));
    int o=1;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)id[i][j]=o++;
    T=o;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(S,id[x][y],INF);
        st[x][y]=1;
    }
    for(int x=0;x<n;x++){
        for(int y=0;y<n;y++){
            if(!st[x][y])add(id[x][y],T,c);
            for(int i=0;i<4;i++){
                int dx=x+xx[i];
                int dy=y+yy[i];
                if(dx>=0&&dx<n&&dy>=0&&dy<n){
                    add(id[x][y],id[dx][dy],1);
                }
            }
        
        }
    }
//     cout<
    cout<<dinic();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99

    字典树

    最大异或和

    #include
#define ls tr[u][0]
#define rs tr[u][1]
using namespace std;
const int N=6e5+10,M=N*30;
int n,s[N],m,L[M],root[N],o,tr[M][2];
void pushup(int u){
    L[u]=max(L[ls],L[rs]);//max_id当前子树中下标最大值
}
void ins(int i,int k,int p,int &u){
    if(!u)u=++o;
    if(k<0){
        L[u]=i;
        return;
    }
    int v=s[i]>>k&1;
    if(p)tr[u][v^1]=tr[p][v^1];
    ins(i,k-1,tr[p][v],tr[u][v]);
    pushup(u);
}

int que(int l,int r,int x){
    int p=root[r];
    for(int i=23;i>=0;i--){
        int v=x>>i&1;
        if(L[tr[p][v^1]]>=l)p=tr[p][v^1];
        else p=tr[p][v];
    }
    return x^s[L[p]];
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    L[0]=-1;
    ins(0,23,root[0],root[0]);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]^=s[i-1];
        ins(i,23,root[i-1],root[i]);
    }
    for(int i=1;i<=m;i++){
        char op;
        int l,r,x;
        cin>>op;
        if(op=='A'){
            cin>>x;
            ++n;
            s[n]=x^s[n-1];
            ins(n,23,root[n-1],root[n]);
        }
        else{
            cin>>l>>r>>x;
            cout<<que(l-1,r-1,s[n]^x)<<'\n';
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    828div3 F

    


    • 1
    • 2

    abc273E

    #include
using namespace std;
const int N=1e6+10;
int a[N],fa[N],idx,p,T,x;
map<int,int>mp;
string s;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    a[0]=-1;
    while(T--){
        cin>>s;
        if(s[0]!='D')cin>>x;
        
        if(s[0]=='A')a[++idx]=x,fa[idx]=p,p=idx;
        if(s[0]=='D')p=fa[p];
        if(s[0]=='S')mp[x]=p;
        if(s[0]=='L')p=mp[x];
        cout<<a[p]<<'\n';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    abc273F

    非常好的一个区间dp

    #include
#define int long long
using namespace std;
const int N=5050;
int n,x,a[N],ans,p,q;
map<int,int>f,id;
int dp[N][N][2];
map<int,int>Wall,Hammer;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>a[i],Wall[a[i]]=1;
    for(int i=n+1;i<=n+n;i++)cin>>a[i],f[a[i-n]]=a[i];//找到每堵墙对应它的锤子位置
    a[2*n+1]=0,a[2*n+2]=x,ans=1e18,n=2*n+2;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        id[a[i]]=i;//找到他们对应的下标
        
        if(a[i]==0)dp[i][i][0]=dp[i][i][1]=0;
        else dp[i][i][0]=dp[i][i][1]=1e18;
        
        if(a[i]==0)p=i;
        if(a[i]==x)q=i;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            //如果不是墙可以转移
            //如果是墙但是锤子在【L，R】里面可以转移
            x=id[f[a[l]]];
            if(!Wall[a[l]]||(l+1<=x&&x<=r))dp[l][r][0]=min(dp[l+1][r][0]+a[l+1]-a[l],dp[l+1][r][1]+a[r]-a[l]);
            else dp[l][r][0]=1e18;
            x=id[f[a[r]]];
            if(!Wall[a[r]]||(l<=x&&x<=r-1))dp[l][r][1]=min(dp[l][r-1][0]+a[r]-a[l],dp[l][r-1][1]+a[r]-a[r-1]);
            else dp[l][r][1]=1e18;
            
            if(l<=min(p,q)&&max(p,q)<=r)ans=min({ans,dp[l][r][0],dp[l][r][1]});
            // if(p>q&&l<=q&&p<=r)ans=min({ans,dp[l][r][0],dp[l][r][1]});
        }
    }
    if(ans==1e18)ans=-1;
    cout<<ans;
    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    填数字

    好题，线性dp的设计,贡献的计算

    #include
using namespace std;
#define int long long
const int mod=1e8+7;
const int N=220;
int f[N][N][N],n;
int C(int len,int op=1){
    if(op==2)return len*(len-1)/2;
    return len;
}

signed main(){
    cin>>n;
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=(i-j);k++){
                int &x=f[i][j][k],len;
                x+=f[i-1][j][k];
                //放1个1在0
                if(j-1>=0)len=(i-1)-(j-1)-k+1,x+=f[i-1][j-1][k]*C(len,1);
                //放2个1在0
                if(j-2>=0)len=(i-1)-(j-2)-k+1,x+=f[i-1][j-2][k]*C(len,2);
                //放2个1在1
                if(k-2>=0)x+=f[i-1][j+2][k-2]*C(j+2,2);
                //放1个1在1
                if(k-1>=0)x+=f[i-1][j+1][k-1]*C(j+1,1);
                //放1个1在1并放1个1在0
                if(k-1>=0)len=(i-1)-j-(k-1)+1,x+=f[i-1][j][k-1]*C(j,1)*C(len,1);
                //放1个2在0
                if(k-1>=0)len=(i-1)-j-(k-1)+1,x+=f[i-1][j][k-1]*C(len,1);
                x%=mod;
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            ans=(ans+f[n][i][j])%mod;
        }
    }
    cout<<ans;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    同核心思路abc273g

    #include
using namespace std;
#define int long long
const int mod=998244353;
const int N=5050;
int n,f[N][N],a[N],b[N],sum,cnt;
int C(int len,int op){
    if(op==2)return len*(len-1)/2;
    if(op==1)return len;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    int sum0=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum0+=a[i];
    for(int i=1;i<=n;i++)cin>>b[i],sum+=b[i];
    if(sum0!=sum){
        cout<<0;
        return 0;
    }
    for(int j=1;j<=n;j++)cnt+=(b[j]==2);
    f[0][cnt]=1;
    for(int i=1;i<=n;i++){
        sum-=a[i];
        for(int x=0;x<=n;x++){
            int y=sum-2*x;//目前x个0列，y个1列，都是关于f[i]的确切状态
            if(y<0)break;
            if(a[i]==0)f[i][x]=f[i-1][x];
            if(a[i]==1){
                f[i][x]+=f[i-1][x]*C(y+1,1);//1-1
                f[i][x]+=f[i-1][x+1]*C(x+1,1);//1-0
            }
            if(a[i]==2){
                f[i][x]+=f[i-1][x]*C(y+2,2);//1-1,1-1
                f[i][x]+=f[i-1][x+1]*C(x+1,1)*C(y,1);//1-0,1-1
                f[i][x]+=f[i-1][x+2]*C(x+2,2);//1-0,1-0
                f[i][x]+=f[i-1][x+1]*C(x+1,1);//2-0
            }
            f[i][x]%=mod;            
        }
    }
    cout<<f[n][0];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    树上路径边权异或和最大值

    #include
#include
#include
using namespace std;
const int N=1e5+10,M=2*N;
int n,a,b,c,h[N],e[M],ne[M],w[M],idx,ans;
int ch[N*31][2],o;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void modify(int x){
    int u=0;
    for(int i=30;i>=0;i--){
        int j=x>>i&1;
        if(!ch[u][j])ch[u][j]=++o;
        u=ch[u][j];
    }
}
int query(int x){
    int ans=0;
    int u=0;
    for(int i=30;i>=0;i--){
        int j=x>>i&1;
        if(ch[u][j^1])ans+=1<<i,u=ch[u][j^1];
        else u=ch[u][j];
    }
    // cout<<"query("<
    return ans;
}
void dfs(int u,int sum=0,int fa=0){
    ans=max(ans,query(sum));
    modify(sum);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs(j,sum^w[i],u);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>n){
        idx=o=0;
        for(int i=0;i<=n*30;i++)ch[i][0]=ch[i][1]=0;
        for(int i=0;i<=n;i++)h[i]=-1;
        for(int i=1;i<n;i++){
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c);
        }
        ans=0;
        dfs(0);
        cout<<ans<<'\n';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    求数组mex

    求数组mex的时候，我们可以·把数组中未出现的数组插入Trie
    然后mex操作就是求最小值

    对数组全部元素异或一个x之后求mex
    相当于query_min(x)

    #include
using namespace std;
const int N=3e5+10;
int n,ch[N*31][2],o,x,m,t;
int vis[N*2];
void modify(int x){
    int u=0;
    for(int i=31;i>=0;i--){
        int j=x>>i&1;
        if(!ch[u][j])ch[u][j]=++o;
        u=ch[u][j];
    }
}
int query(int x){
    int u=0;
    int ans=0;
    for(int i=31;i>=0;i--){
        int j=x>>i&1;
        if(ch[u][j])u=ch[u][j];
        else ans+=1<<i,u=ch[u][j^1];
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x;
        vis[x]=1;
    }
    for(int i=0;i<N*2;i++)if(!vis[i])modify(i);
    while(m--){
        cin>>x;
        t^=x;
        cout<<query(t)<<'\n';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    可持续化01Trie

    #include
#include
#include
using namespace std;
const int N=1e5+10;
int n,m,a[N],root[N],u,x,idx;
int o,in[N],out[N],son[N*31][2],cnt[N*31][2];
vector<int>g[N];
void build(int &u,int p,int x,int k=30){
    if(k<0)return;
    u=++o;
    int j=x>>k&1;
    son[u][j^1]=son[p][j^1];
    cnt[u][j^1]=cnt[p][j^1];
    cnt[u][j]=cnt[p][j]+1;
    build(son[u][j],son[p][j],x,k-1);
}
int query(int l,int r,int x){
    int ans=0;
    for(int i=30;i>=0;i--){
        int j=x>>i&1;
        int sz=cnt[r][j^1]-cnt[l][j^1];
        if(sz)ans+=1<<i,l=son[l][j^1],r=son[r][j^1];
        else l=son[l][j],r=son[r][j];
    }
    return ans;
}
void dfs(int u,int fa=0){
    in[u]=++idx;
    build(root[in[u]],root[in[u]-1],a[u]);
    for(auto j:g[u])dfs(j);
    out[u]=idx;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>n>>m){
        o=idx=0;
        son[0][0]=son[0][1]=0;
        cnt[0][0]=cnt[0][1]=0;
        for(int i=0;i<=n;i++)g[i].clear();
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=2;i<=n;i++){
            int fa;
            cin>>fa;
            g[fa].push_back(i);
        }
        dfs(1);
        while(m--){
            cin>>u>>x;
            cout<<query(root[in[u]-1],root[out[u]],x)<<'\n';
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    可持续化01Trie+双向链表维护区间次大值

    考虑枚举序列中的每一个值作为次大值，how？
    维护一个双向链表，然后按照a数组从小到大的顺序枚举p
    边枚举边删除，这样就会有左边L权值大于我，右边R权值大于我
    都是开区间，

    #include
using namespace std;
const int N=1e5+10;
int n,a[N],p[N],pre[N],nxt[N],ans;
int root[N],o,cnt[N*30][2],son[N*30][2];
void ins(int &u,int p,int x,int k=30){
    if(k<0)return;
    u=++o;
    int j=x>>k&1;
    cnt[u][j^1]=cnt[p][j^1],son[u][j^1]=son[p][j^1];
    cnt[u][j]=cnt[p][j]+1,ins(son[u][j],son[p][j],x,k-1);
}
int query(int l,int r,int x){
    int sum=0;
    for(int i=30;i>=0;i--){
        int j=x>>i&1;
        int sz=cnt[r][j^1]-cnt[l][j^1];
        if(sz)sum+=1<<i,l=son[l][j^1],r=son[r][j^1];
        else l=son[l][j],r=son[r][j];
    }
    return sum;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)pre[i]=i-1,nxt[i]=i+1,p[i]=i;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ins(root[i],root[i-1],a[i]);
    }
    sort(p+1,p+1+n,[&](int i,int j){
        return a[i]<a[j];
    });
    for(int i=1;i<=n;i++){
        int l=pre[p[i]],r=nxt[p[i]];
        // cout<<"i="<// cout<<"L R="<
        // cout<<"L R="<
        pre[r]=l;
        nxt[l]=r;
        if(l)ans=max(ans,query(root[pre[l]],root[r-1],a[p[i]]));
        if(r!=n+1)ans=max(ans,query(root[l],root[nxt[r]-1],a[p[i]]));
    }
    cout<<ans;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
  • 相关阅读:
    写代码只是皮毛，这才是计算机科学
    判断数据库中表是否存在
    20.支持向量机—数学原理知识
    从无人机到实景三维海洋系统
    VS Code常用操作
    基于AERMOD模型在大气环境影响评价中的实践技术
    电子电气架构设计需要考虑哪些方面？
    【微服务】SpringCloud中Ribbon的WeightedResponseTimeRule策略
    如何手写动态代理实现数据库事务
    《MongoDB》在docker中用得到关于MongoDB一行命令
  • 原文地址：https://blog.csdn.net/supreme567/article/details/127330173