当前位置:首页 » 《随便一记》 » 正文

CF1375D Replace by MEX 题解

4 人参与  2024年10月14日 17:20  分类 : 《随便一记》  评论

点击全文阅读


题目传送门

题目大意

令 m e x mex mex 为序列中最小的没有出现的数。

给你一个长度为 n n n 的序列 a a a,你可以进行不超过 2 × n 2\times n 2×n 次操作,使得序列 a a a 单调不降。每次操作你可以选定一个位置 p p p,并将 a p a_p ap​ 赋值为 m e x mex mex。请你输出总共的操作次数与每次操作的位置。

解题思路

题目说了, ∀ x ∈ a , 0 ≤ x ≤ n \forall x \in a,0\le x\leq n ∀x∈a,0≤x≤n。所以,我们考虑将 a a a 变为 0 , 1 , ⋯   , n − 1 0,1,\cdots,n-1 0,1,⋯,n−1。

我们在进行操作时,需分成两种情况讨论。

若 m e x ≠ n mex \neq n mex=n,由于最后的序列要满足 a i = i − 1 a_i=i-1 ai​=i−1,所以我们这里就将 a m e x + 1 a_{mex+1} amex+1​ 赋值为 m e x mex mex。若 m e x = n mex = n mex=n,那我们就找到序列中任意一个满足 a i ≠ i − 1 a_i \neq i - 1 ai​=i−1 的数,然后将其赋值为 m e x mex mex。如果没有找到,说明现在的序列已经满足题意,不需要再进行操作了。

大概思路就是这样。瞟了一眼数据范围,发现 n n n 比较小,于是我们在求 m e x mex mex 的值时可以暴力求解。

CODE:

#include <bits/stdc++.h>using namespace std;#define int long longint a[1010], b[2010], vis[1010];signed main() {ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);int t, n;cin >> t;while (t--) {memset(vis, 0, sizeof vis);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];vis[a[i]]++; }int ans = 0;   //总共的操作次数/*最后a[i] = i - 1 */while (1) {int mex = 0;for (int i = 0; i <= n; i++) {  //查找 mexif (!vis[i]) {mex = i;break;}}if (mex != n) {vis[a[mex + 1]]--;b[++ans] = mex + 1;a[mex + 1] = mex;vis[mex]++;} else {                bool f = 0;for (int i = 1; i <= n; i++) {if (a[i] != i - 1) {                        f = 1;vis[a[i]]--;a[i] = mex;vis[mex]++;b[++ans] = i;break;}}                if (!f)  //序列合法,不需要再进行操作了                    break;}}cout << ans << endl;for (int i = 1; i <= ans; i++)cout << b[i] << ' ';cout << endl;}return 0;}

总了个结

这题非常水,建议评绿。简单构造,建议尝试。

∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ ∈ \tiny\color{white}{\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum_{\sum_{\sum}^{\sum}\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in}} ∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑​∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈​


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/171801.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 独家周屿,林小柔,江宇城小说小说大结局(重生后,我冷眼看未婚夫小秘书给甲方爸爸送盗版labubu)全篇在线下载阅读
  • 重生后,我送渣男下地狱见阎罗王续集_苏景琛笑笑老太太听书_小说后续在线阅读_无删减免费完结_
  • 一百,解释,油漆小说(高考过后,我给擦边男主播刷了一百万)TXT无套路在线+无广告结局
  • 掏空我后,全家逼我卖婚房未删减_妹妹宝马老公番茄热门_小说后续在线阅读_无删减免费完结_
  • 纪君范,亓霏霏小说完本章节前文+全篇阅读(被小三的反击战)连载中
  • 陈春花,池言(重生后,摆脱吸血鬼老公一家)前文+全本完整阅读预售作品抢先看
  • 错认皇太女后,三个皇夫悔疯了后续结局_春桃长青魏昭看点十足_小说后续在线阅读_无删减免费完结_
  • (重生后,恶毒女配拿稳白月光剧本)江朝华燕景最终篇章(江朝华燕景)全书在线无广告高口碑小说
  • 女儿遇险命悬一线,我却见死不救后续+完结_小姑娘雷达安静读者推荐_小说后续在线阅读_无删减免费完结_
  • 黎夏林意深:结局+番外新上热文新章速递京港缠绵,他独宠娇梅:结局+番外评价五颗星
  • 陈春花,池言小说全文免费阅读(重生后,摆脱吸血鬼老公一家)全文免费阅读无弹窗_陈春花,池言小说全文免费阅读_笔趣阁
  • 女帝采补八百年:出世无敌怎么了?隐藏剧情_苏玄沐禹竹最新阅读_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1