当前位置:网站首页>Mex related learning
Mex related learning
2022-07-06 07:42:00 【eva_ can(not)survive】
MEX Is the smallest positive integer that does not appear in an interval .
Therefore, adding a number to the interval is only for those who join the interval mex Value can be increased ;
Let's look at two topics
Problem - C - Codeforceshttps://codeforces.com/contest/1699/problem/C First of all, we can think about an interval 【L,R】 Of mex yes x, explain 【0,x-1】 It must have happened , So if x If the position of is inside the interval, it can be at any unused position in the interval , If you are not in this range, you can only stay in that position , because x Once moved, the sequence Column mex The value will definitely be affected .
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);
}
Then there is this question We need to find the largest lexicographic sequence we can get , So we b The element obtained in the sequence must be the largest one that can be selected mex, So we can maintain a prefix mex And suffixes mex, When our prefix mex This is equal to the maximum mex The answer array can be added when , Then start directly from the next point mex Replace value with suffix mex Value
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');
}
边栏推荐
- Google may return to the Chinese market after the Spring Festival.
- Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
- 49. Sound card driven article collection
- Ble of Jerry [chapter]
- If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
- word中把帶有某個符號的行全部選中,更改為標題
- Significance and measures of encryption protection for intelligent terminal equipment
- Type of data in energy dashboard
- 洛谷P4127 [AHOI2009]同类分布 题解
- 位运算异或
猜你喜欢
Basics of reptile - Scratch reptile
Leecode-c language implementation -15 Sum of three ----- ideas to be improved
DataX self check error /datax/plugin/reader/_ drdsreader/plugin. Json] does not exist
Excel的相关操作
Force buckle day31
datax自检报错 /datax/plugin/reader/._drdsreader/plugin.json]不存在
Typescript interface and the use of generics
Do you really think binary search is easy
[非线性控制理论]9_非线性控制理论串讲
珠海金山面试复盘
随机推荐
HTTP cache, forced cache, negotiated cache
链表面试题(图文详解)
Type of data in energy dashboard
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
Related operations of Excel
Nc204382 medium sequence
MEX有关的学习
jmeter性能测试步骤实战教程
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
Force buckle day31
Generator Foundation
[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
Bit operation XOR
PHP Coding Standard
Relevant introduction of clip image
Description of octomap averagenodecolor function
Solution: intelligent site intelligent inspection scheme video monitoring system
Typescript variable scope
Google可能在春节后回归中国市场。
edge浏览器 路径获得