设为首页|收藏本站|
发帖
登录 注册
西兔生活网 › 华人生活 › 移民签证 › Codeforces Round #830 (Div. 2) D1/D2(mex问题)
回复 发帖
返回列表 发新帖
开启左侧

[问答] Codeforces Round #830 (Div. 2) D1/D2(mex问题)

[复制链接]
87893 9
咖啡妹妹 发表于 2022-11-1 04:49:02 | 只看该作者 打印 上一主题 下一主题
 
Problem - D1 - Codeforces
题意：
你需要实现一个数据结构，至此以下操作

  • + \ \  x  添加x到数据结构中，保证x没有出现过
  • ? \ \ k 查询最小未出现的 k 的倍数
操作最多 2*10^5 次。
做法：
关于mex，我写过不少的文章（
严格鸽：序列中未出现的最小的非负整数 mex 入门
严格鸽：ACM教程 求区间mex的多种方法
只有删除操作，也就是我们询问相同的 k ，其答案只会增加，不会减少。
所以我们定义 last[k] 为询问 k 的时候，上一次的答案，每次询问的时候，我们直接暴力跑即可。
用 vis[x] = 1/0 表示 x 是否出现在数据结构中。
while (vis[last[x]])last[x] += x;
考虑 last 发生改变的次数。

Codeforces Round #830 (Div. 2) D1/D2(mex问题) 第1张图片
例如， last[k] 跳跃了 n 个点，同理对于 2k 可以跳跃\frac{n}{2}个点

Codeforces Round #830 (Div. 2) D1/D2(mex问题) 第2张图片
3k 可以跳跃 \frac{n}{3} 个点。
同理，统共最多跳跃 \sum_{}^{}{\frac{n}{i}} \le nlogn 个。而一共最多只有操作次数个点，也就是 n\le 2*10^5
code
void slove() {
    map<int,int>vis;
    map<int, int>last;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char op; int x;
        cin >> op >> x;
        if (op == '+')vis[x] = 1;
        else {
            if (!last.count(x))last[x] = x;
            while (vis[last[x]])last[x] += x;
            cout << last[x] << endl;
        }
    }
}
Problem - D2 - Codeforces
题意：
你需要实现一个数据结构，至此以下操作

  • + \ \  x  添加x到数据结构中，保证x没有出现过
  • - \ \ x 删除x从数据结构中，保证x出现过
  • ? \ \ k 查询最小未出现的 k 的倍数
操作最多 2*10^5 次。
做法：
我们回想下，之前我们是如何处理查询mex的。
我们用了一个set，初始 set = [0,1,2,3,4,......]
我们添加一个数x，就将其从set中删除，删除就添加回set。
这样mex就等于set的最小值。
可以理解，我们的set是维护未出现的数，然后mex就是找最小
所以这里，我们也可以类比这个做法。
我们开一个
map<int, set<int>>del;
del[x] 表示，对于 x 其未出现的数
然后我们开一个
map<int, vector<int>>change;
change[x] 表示，当我们删除 x 后，后哪些数，其 last 是变了的。
这样，查询的时候，我们跑last的同时维护一下 change
while (vis[last[x]]) {
    change[last[x]].push_back(x);
    last[x] += x;
}
对于添加删除操作，我们同样的操作set即可。
注意，“删除x从数据结构中，保证x出现过”这句话，让我们不需要set = [0,1,2,3,4,.....]这样
code
void slove() {
    map<int, int>vis;
    map<int, int>last;
    map<int, set<int>>del;
    map<int, vector<int>>change;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char op; int x;
        cin >> op >> x;
        if (op == '+') {
            vis[x] = 1;
            for (int y : change[x]) {
                del[y].erase(x);
            }
        }
        else if (op == '-') {
            vis[x] = 0;
            for (int y : change[x]) {
                del[y].insert(x);
            }
        }
        else {
            if (!last.count(x))last[x] = x;
            if (del[x].size()) {
                cout << *del[x].begin() << endl;
            }
            else {
                while (vis[last[x]]) {
                    change[last[x]].push_back(x);
                    last[x] += x;
                }
                cout << last[x] << endl;
            }
        }
    }
}


上一篇：威海旅行，第89篇，名副其实的旅游天堂石岛来啦！
下一篇：呼叫中心中间件助力机场呼叫中心系统智能升级
标签：数据结构非负整数最小的文章严格
@
免
责
声
明
1.西兔生活网 CTLIVES 内容全部来自网络;
2.版权归原网站或原作者所有;
3.内容与本站立场无关;
4.若涉及侵权或有疑义，请点击“举报”按钮，其他联系方式或无法及时处理。
举报

关联主题
回复

使用道具 举报

 

精彩评论9

正序浏览
跳转到指定楼层
沙发
ken321 发表于 2022-11-1 04:49:34 | 只看该作者
 
D2复杂度是啥
回复 支持 反对

使用道具 举报

 
板凳
LoveBaby712 发表于 2022-11-1 04:49:40 | 只看该作者
 
D1的复杂度加个log
回复 支持 反对

使用道具 举报

 
地板
梦水莲 发表于 2022-11-1 04:50:38 | 只看该作者
 
这复杂度咋算的，每次for change[x]那里不会导致n²的复杂度吗
回复 支持 反对

使用道具 举报

 
5#
hy990762 发表于 2022-11-1 04:50:59 | 只看该作者
 
考虑，每个数可以被last遍历到几次
回复 支持 反对

使用道具 举报

 
6#
bin52029 发表于 2022-11-1 04:51:21 | 只看该作者
 
这不对，你得算del被更新的次数
回复 支持 反对

使用道具 举报

 
7#
爸比sete 发表于 2022-11-1 04:51:54 | 只看该作者
 
还是不太清楚怎么算的
回复 支持 反对

使用道具 举报

 
8#
time专业酱油哥 发表于 2022-11-1 04:52:43 | 只看该作者
 
d2也太妙了吧[大哭][大哭]
回复 支持 反对

使用道具 举报

 
9#
卡布基糯i 发表于 2022-11-1 04:53:16 | 只看该作者
 
ygg考虑更E吗     orz
回复 支持 反对

使用道具 举报

 
10#
79376608 发表于 2022-11-1 04:53:27 | 只看该作者
 
这是均摊的，del复杂度均摊和d1差不多，确实是d1复杂度多了一个log(set)
回复 支持 反对

使用道具 举报

 
返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

咖啡妹妹白金会员

0关注

5粉丝

423帖子

热门图文
热门帖子
排行榜
  • 日
  • 周
  • 月
活跃网友
返回顶部快速回复上一主题下一主题返回列表APP下载手机访问
Copyright © 2016-2028 CTLIVES.COM All Rights Reserved.  西兔生活网  小黑屋| GMT+8, 2024-5-6 06:34