当前位置:网站首页>MEX有关的学习
MEX有关的学习
2022-07-06 07:35:00 【eva_can(not)survive】
MEX是一段区间内未出现的最小正整数。
所以向该区间加一个数只有加入该区间的mex值时才能增加;
我们来看两个题目
Problem - C - Codeforceshttps://codeforces.com/contest/1699/problem/C首先我们可以思考一个区间【L,R】的mex是x,说明【0,x-1】肯定都出现过了,所以如果x的位置在该区间内部则可以在区间内任意一个未被使用的位置,如果不在该区间内就只能在那个位置不动了,因为x一旦动那么该序列的mex值肯定会受到影响。
int a[MAXN];
int pos[MAXN];
const int mod = 1e9 + 7;
void solve() {
int n;
ll ans = 1;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
pos[a[i]] = i;
}
int mx = -INF, mn = INF;
for (int i = 0; i < n; i++) {
if (pos[i] > mn && pos[i] < mx) {
ans *= (mx - mn + 1 - i);
ans %= mod;
}
mn = min(mn, pos[i]);
mx = max(mx, pos[i]);
}
printf("%lld\n", ans);
}
然后是这一题 需要求我们能得出得最大字典序序列,所以我们b序列中得到得元素肯定是能选到得最大得mex,所以我们可以维护一个前缀mex和后缀mex,当我们的前缀mex此时等于最大的mex时候就可以加入答案数组,然后直接从下一点开始把mex值替换成后缀mex的值
struct MEX {
int cot[MAXN];
vector<int> res;
int id = 0;
void add(int x) {
cot[x]++;
res.push_back(x);
}
int mex() {
while (cot[id])
id++;
return id;
}
void clear() {
for (int v : res) {
cot[v]--;
}
id = 0;
res.clear();
}
};
MEX now, t;
int a[MAXN];
int last[MAXN];
void solve() {
now.clear();
t.clear();
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
for (int i = n; i >= 1; i--) {
t.add(a[i]);
last[i] = t.mex();
}
vector<int> ans;
int mx = last[1];
for (int i = 1; i <= n; i++) {
now.add(a[i]);
if (mx == now.mex()) {
ans.push_back(mx);
mx = last[i + 1];
now.clear();
}
}
printf("%d\n", ans.size());
for (int v : ans) {
printf("%d ", v);
}
putchar('\n');
}
边栏推荐
- 成为优秀的TS体操高手 之 TS 类型体操前置知识储备
- Simple and understandable high-precision addition in C language
- 合规、高效,加快药企数字化转型,全新打造药企文档资源中心
- Do you really think binary search is easy
- leecode-C語言實現-15. 三數之和------思路待改進版
- [CF Gym101196-I] Waif Until Dark 网络最大流
- 上线APS系统,破除物料采购计划与生产实际脱钩的难题
- Select all the lines with a symbol in word and change them to titles
- TypeScript 变量作用域
- Luogu p4127 [ahoi2009] similar distribution problem solution
猜你喜欢
[MySQL learning notes 32] mvcc
jmeter性能测试步骤实战教程
杰理之BLE【篇】
Seriously recommend several machine learning official account
Redis builds clusters
Generator Foundation
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
In the era of digital economy, how to ensure security?
Related operations of Excel
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
随机推荐
How can word delete English only and keep Chinese or delete Chinese and keep English
合规、高效,加快药企数字化转型,全新打造药企文档资源中心
Simulation of Michelson interferometer based on MATLAB
[MySQL learning notes 30] lock (non tutorial)
杰理之AD 系列 MIDI 功能说明【篇】
[computer skills]
How Navicat imports MySQL scripts
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
Set picture annotation in markdown
Typescript void base type
杰理之BLE【篇】
Iterator Foundation
杰理之需要修改 gatt 的 profile 定义【篇】
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
OpenJudge NOI 2.1 1661:Bomb Game
C # display the list control, select the file to obtain the file path and filter the file extension, and RichTextBox displays the data
Excel的相关操作
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
http缓存,强制缓存,协商缓存