首页 > 牛牛的mex
开通博客写题解
头像 RainAir
发表于 2020-08-28 22:13:47
A 注意条件 且 互不相同，所以一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数。预处理前缀后缀最小值就好了。代码链接 B 发现当 时答案必为 。 于是我们只需要预处理 的答案就好了。可以推式子或者前缀和处理。代码链接 C 我们考虑单组询问 怎么做：实际上就是把所有 的所 展开全文
去ta的博客 赞 (11) 回复(2) 收起
头像 段三园的小迷弟
发表于 2020-08-29 17:18:17
A，展开即可正常查看 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; #define fi first #define se seco 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Dear㉿You
发表于 2020-08-29 09:55:18
前言 有时候题解不仅仅是题解 关于莫队 现在只说普通莫队 离线处理区间问题,可以发现某些题的条件是必须由上一个答案转移过来，就是因为出题人害怕被莫队暴虐(fake,反正我都要被虐) 他有许多神奇操作:询问的分块排序，以及区间的伸缩 莫队的分块排序 这是精髓 为什么不考虑普通排序呢？ 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 zqy1018_
发表于 2020-08-28 22:00:47
A 牛牛的mex 题意：给一个 到 的长为 的排列 ，多次询问，每次给出 ，问 。 做一个前缀最小值和后缀最小值，每次询问比一下即可。 #include <bits/stdc++.h> using namespace std; int read(){ int f = 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 tin_t
发表于 2020-08-29 12:19:04
链接：https://ac.nowcoder.com/acm/contest/7079/A 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld 题目描述 牛牛现在有一个长度为 n 的序列a。现在牛牛有 q 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunsetcolors
发表于 2020-08-28 23:15:44
B 牛牛的算术 题目地址： https://ac.nowcoder.com/acm/contest/7079/B 基本思路： 我们发现这个是连乘的形式,那么如果,那么必然会取模成0,所以我们考虑的部分怎么算,我们将式子拆分一下： ,最后一部分很明显是一个前缀和,然后第二个部分也是一个前缀和, 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 W.A.R
发表于 2020-08-30 02:47:40
牛客练习赛68 A-牛牛的Mex 传送门 题意 给一个0~n-1的排列，q个询问，询问区间的Mex。 Mex定义为最小未出现的自然数。 题解 我们队三个人看到这题第一反应上莫队，jhlp哈哈哈哈 然后掏出莫队板子火速A了 我是赛后再来回顾的，发现由于这题数组比较特殊是有更符合这道题背景的做法的。 莫 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 肖先生~
发表于 2020-09-11 08:28:11
题目分析：题目说要求未出现的最小自然数，并且题目有条件，那就是元素值都小于n并且互不相等，那么我们可以维护一个前缀和最小值和一个后缀和最小值，最后未出现的最小自然数就在区间旁边取一个最小值就行。 #include <bits/stdc++.h> using namespace std; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Scarlet_Hypoc
发表于 2020-08-28 23:21:08
推一下柿子就好了： 令 ，代入得： 可以发现，当 时答案肯定为 ，所以只需要考虑 的情况。那么这个东西也像上面预处理出来就可以 回答询问了，代码如下： #include <cstdio> #include <cstring> #include <algorit 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”