首页 > 其他分享 >关于mutiset的应用的几个题

关于mutiset的应用的几个题

时间:2023-09-27 22:56:39浏览次数:37  
标签:int res up mutiset 关于 应用 it2 find it1

关于mutiset的应用的几个题

今天kk同学给了我两个题,都是是multiset的题。它的一些性质和应用还是很重要哒!

G - Minimum Xor Pair Query

题意:你可以进行以下操作

  1. 加入一个数
  2. 删除一个数
  3. 输出任意两个数异或最小值

思路:首先我们要知道一个性质(重要!):两个数差值越小,异或值也越小。

那么我们要求异或最小值,那么答案一定在排序后相邻两个数中产生。

为了便于写,防止在set里面找不到的情况出现,我们手动插入下界和上界。

考虑我们的操作:

对于加入一个数,我们的答案有什么影响呢?

假设我们插入的值是\(x\)。

假设我们的情况是:\(l\) \(x\) \(r\)

首先如果\(l\)和\(r\)都存在,那么显然此时\(l\)和\(r\)的异或值不可能成为答案,我们把它删去

然后在答案里面加入x^l和 x^r(前提是l,r存在)

void add(ll x)
{
    s.insert(x);
    multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
    it1--, it2++;
    if(*it1 != -1 && *it2 != up) 
        res.erase(res.find((*it1) ^ (*it2)));
    if(*it1 != -1)
        res.insert(x ^ (*it1));
    if(*it2 != up)
        res.insert(x ^ (*it2));
    //cout<<x<<'\n';
}

对于删一个数的情况呢?

那就和加一个数的操作反过来就行了。

void del(ll x)
{
    multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
    it1--, it2++;
    if(*it1 != -1 && *it2 != up) 
        res.insert((*it1) ^ (*it2));
    if(*it1 != -1)
        res.erase(res.find((*it1) ^ x));
    if(*it2 != up)
        res.erase(res.find(x ^ (*it2)));
    s.erase(s.find(x));
}

下面是AC代码:

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const ll up = 1ll<<60;
multiset<ll>s,res;
void add(ll x)
{
    s.insert(x);
    multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
    it1--, it2++;
    if(*it1 != -1 && *it2 != up) 
        res.erase(res.find((*it1) ^ (*it2)));
    if(*it1 != -1)
        res.insert(x ^ (*it1));
    if(*it2 != up)
        res.insert(x ^ (*it2));
    //cout<<x<<'\n';
}
void del(ll x)
{
    multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
    it1--, it2++;
    if(*it1 != -1 && *it2 != up) 
        res.insert((*it1) ^ (*it2));
    if(*it1 != -1)
        res.erase(res.find((*it1) ^ x));
    if(*it2 != up)
        res.erase(res.find(x ^ (*it2)));
    s.erase(s.find(x));
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin>>q;
    s.insert(-1),s.insert(up);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x;
            cin>>x;
            add(x);
        }
        else if(op==2)
        {
            int x;
            cin>>x;
            del(x);
        }
        else
        {
            cout<<*res.begin()<<"\n";
        }
    }


    return 0;
}

G. The Great Equalizer

题意:

一次运行包含以下操作:

  1. 对当前数组排序(不降序),然后删除重复的元素
  2. 如果当前数组大小是1,那么停止运行,输出运行结果
  3. 对于数组元素加上一个等差数列\(\{n,n-1,n-2,...,1\}\)其中\(n\)是当前数组长度
  4. 返回第一步

给你\(q\)个询问,每次给你\(i\) \(x\),表示把\(a[i]\)赋值为\(x\)。然后运行上述。

思路:

第一次写的时候TLE了,因为我这样写会每次重新计算答案,复杂度很高。下面是错误代码QAQ

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int t,n,q,a[N],b[N],d[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];

        cin>>q;
        while(q--)
        {
            int i,x;
            cin>>i>>x;
            a[i] = x;
            multiset<int>s;
            for(int i = 1;i <= n; i++)
                b[i] = a[i];
            sort(b+1,b+1+n);
            for(int i = 1;i < n; i++)
                d[i] = b[i+1]-b[i];
            // cout<<"b[i] = ";
            // for(int i = 1;i <= n; i++)
            //     cout<<b[i]<<" ";
            // cout<<"\n";
            // cout<<"d[i] = ";
            // for(int i = 1;i < n; i++)
            //     cout<<d[i]<<" ";
            // cout<<"\n";
       
            for(int i = 1;i < n; i++)
                s.insert(d[i]);
           
            ll ans = b[1];
            int ff = 0;
            while(!s.empty())
            {
                int sz = s.size();
                // cout<<"sz = "<<sz<<" fi = "<<*s.begin()<<"\n";
                // cout<<"ff = "<<ff<<"\n";
                ans += (sz+1)*(*s.begin()-ff);
                int tmp = *s.begin();

                ff = ff+tmp-ff;
                s.erase(tmp);    
            }
            cout<<ans<<" ";
        }
        cout<<"\n";
    }
/*
1
3
2 4 8
3
1 6
2 10
3 1
*/

    return 0;
}

那么正解是什么呢?

通过找规律,我们可以发现,最后的答案是数组最大的元素值+排序后数组中两个数差的最大值。

因为,每次操作,排序后的数组,相邻两个数的差值-1,数组中最大值+1,那么答案就是数组最大的元素值+排序后数组中两个数差的最大值。和上一题类似,不过改成了维护两个数差的最大值。

注意:其实改一个数可以想象成把原本的数删了加入一个新的数。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int t,n,q,a[N];
multiset<ll>s,res;
const ll up = 1ll<<60;
void add(ll x)
{
    s.insert(x);
    multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
    it1--, it2++;
    if(*it1 != -1 && *it2 != up) 
        res.erase(res.find((*it2) - (*it1)));
    if(*it1 != -1)
        res.insert(x - (*it1));
    if(*it2 != up)
        res.insert((*it2) - x);
    //cout<<x<<'\n';
}

void del(ll x)
{
    multiset<ll>::iterator it1 = s.find(x), it2 = s.find(x);
    it1--, it2++;
    if(*it1 != -1 && *it2 != up) 
        res.insert((*it2) - (*it1));
    if(*it1 != -1)
        res.erase(res.find(x - (*it1)));
    if(*it2 != up)
        res.erase(res.find((*it2) - x));
    s.erase(s.find(x));
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>t;
    while(t--)
    {
        cin>>n;
        res.clear(),s.clear();
        s.insert(-1),s.insert(up);
        for(int i = 1;i <= n; i++)
            cin>>a[i],add(a[i]);
        cin>>q;
        while(q--)
        {
            int i,x;
            cin>>i>>x;
            del(a[i]);
            a[i] = x;
            add(a[i]);
            if(n==1){
                cout<<a[n]<<"\n";
                continue;
            }
            cout<<*(--(--s.end()))+*(--res.end())<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

标签:int,res,up,mutiset,关于,应用,it2,find,it1
From: https://www.cnblogs.com/nannandbk/p/17734583.html

相关文章

  • 关于MMEngine随机性的一些整理
    1、随机性来自哪里?(1)torch算法的随机数种子实现defset_random_seed(seed:Optional[int]=None,deterministic:bool=False,diff_rank_seed:bool=False)->int:"""Setrandomseed.Args:seed(in......
  • 单片机原理及应用(第四章)小结
    1.C语言中while和dowhile的不同点是什么?while满足条件才会循环dowhile先运行一次再判断条件2.若在C语言中的switch操作漏掉break,会发生什么?会接着执行下一个case无论下一个case满足不满足条件,直至switch结束或遇到break3.编写程序用for循环实现1-20连加......
  • 【JAVA】关于抽象类的概念
    个人主页:【......
  • 优维低代码实践:应用级配置
    优维低代码技术专栏,是一个全新的、技术为主的专栏,由优维技术委员会成员执笔,基于优维7年低代码技术研发及运维成果,主要介绍低代码相关的技术原理及架构逻辑,目的是给广大运维人提供一个技术交流与学习的平台。优维低代码实践连载第19期《应用级配置》▽除了全局特性开关,有时我们希望......
  • 关于gpt的使用
    1.安装环境(建议使用python3.9以及以上版本)gradio==3.31.0langchain==0.0.173loguru==0.5.3moviepy==1.0.3openai==0.27.6openai_whisper==20230314pandas==1.3.4pymongo==3.12.1requests==2.28.1retry==0.9.2tqdm==4.65.0whisper==1.1.10redispymongo==3.12.12.......
  • realloc函数应用&IO泄露体验
    本题主要介绍realloc函数,平时我们使用realloc最多便是在打malloc_hook-->onegadget的时候,使用realloc_hook调整onegadget的栈帧,从而getshell。在realloc函数中,也能像malloc一样创建堆,并且比malloc麻烦一些,但是倒是挺有趣的。reallocrealloc(realloc_ptr,size)有两个参数,并且在......
  • FatFs文件系统移植应用笔记
    FatFs文件系统移植应用笔记使单片机拥有按文件访问存储器中数据的能力,要满足两个必要的条件。其一是存储器已完成格式化操作,即存储器按FAT/FAT16/FAT32等格式记录数据,其二是软件中实现文件系统功能,即能够按照存储器中文件记录的格式,操作已有的数据或添加新数据。FatFs是一个轻......
  • 关于ROS 的疑问
    一、https://blog.csdn.net/CH_monsy/article/details/108001875  二、 三、https://zhuanlan.zhihu.com/p/83598756  : 四、 五、 六: 七、 八、一、安装ubuntu18.041、Ubuntu18.04下载,等待在vmware中安装。2、vmware下载安装。腾讯云“在Vmware......
  • 关于数据结构单链表
    单链表作为最基础也是最常用的数据结构之一,在这门课程中占据着十分重要的地位。本文将对单链表这一章节的知识点进行总结,包括单链表的定义、基本操作、常见应用以及时间复杂度等方面。一、单链表的定义和基本操作单链表的定义:单链表由节点组成,每个节点包含数据和指向下一个节点的指......
  • 视频识别技术的发展和应用有哪些?
    视频识别技术的发展和应用非常广泛,以下是其中几个具体领域:智能监控:视频识别技术可以应用于智能监控领域,通过监控视频,自动识别特定目标,例如人脸、车牌等,实现快速定位和追踪。这项技术也可以用于安全监控,例如在银行、商场等重要场所进行视频监控,提高安全防范能力。自动驾驶:视频识......