当前位置:网站首页>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');
}
边栏推荐
- opencv学习笔记八--答题卡识别
- 智能终端设备加密防护的意义和措施
- [CF Gym101196-I] Waif Until Dark 网络最大流
- Google可能在春节后回归中国市场。
- word删除括号里内容
- OpenJudge NOI 2.1 1661:Bomb Game
- 杰理之AD 系列 MIDI 功能说明【篇】
- C intercept string
- 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
- Emo diary 1
猜你喜欢
Twelve rules for naming variables
杰理之AD 系列 MIDI 功能说明【篇】
TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比
TS 类型体操 之 循环中的键值判断,as 关键字使用
octomap averageNodeColor函数说明
Ali's redis interview question is too difficult, isn't it? I was pressed on the ground and rubbed
opencv学习笔记九--背景建模+光流估计
Generator Foundation
杰理之BLE【篇】
Opencv learning notes 9 -- background modeling + optical flow estimation
随机推荐
Bit operation XOR
Memory error during variable parameter overload
Introduction to the basics of network security
Supervisor usage document
TypeScript void 基础类型
Three no resumes in the software testing industry. What does the enterprise use to recruit you? Shichendahai's resume
jmeter性能测试步骤实战教程
Apache middleware vulnerability recurrence
Summary of Digital IC design written examination questions (I)
Cf1036c class numbers solution
opencv学习笔记八--答题卡识别
In the era of digital economy, how to ensure security?
js對象獲取屬性的方法(.和[]方式)
杰理之BLE【篇】
Word setting directory
SSM learning
杰理之AD 系列 MIDI 功能说明【篇】
JDBC learning notes
How can word delete English only and keep Chinese or delete Chinese and keep English
Twelve rules for naming variables