首页 > 其他分享 >CF1375D Replace by MEX 题解

CF1375D Replace by MEX 题解

时间:2024-07-01 16:59:23浏览次数:21  
标签:cin int 题解 ++ mex vis 序列 CF1375D MEX

题目大意

令 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 long
int 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++) {  //查找 mex
				if (!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;
}

总了个结

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

标签:cin,int,题解,++,mex,vis,序列,CF1375D,MEX
From: https://blog.csdn.net/2301_76224755/article/details/140105090

相关文章

  • GESP 202406 四级认证 T1 题解
    大意:一个只包含000和111的矩形,边长为......
  • ## BZOJ2720 [Violet 5] 列队春游 题解
    Problem对于一个数列\(S\),\(S_0=\infty\),设对于\(S_i\),\(S_{a_i}\)是\(S_i\)之前第一个大于等于\(S_i\)的数。给定\(S\)中的元素,求\(\sum_{i=1}^{n}(i-a_i)\)的期望。Solution我们考虑对于每一种身高的学生,分别统计期望。显然,对于身高为\(h\)的学生,只有身高为\(......
  • ata1.00: exception Emask 0x0 SAct 0x8000000 SErr 0x0 action 0x6 frozen 问题解析
    ata1.00:exceptionEmask0x0SAct0x8000000SErr0x0action0x6frozen硬盘问题测试发现嵌入式linuxvfat文件系统的sata固态硬盘偶然启动时出现异常打印如下:ata1.00:exceptionEmask0x0SAct0x8000000SErr0x0action0x6frozenata1.00:failedcommand:READFPD......
  • 第24节 习题解析
    第24节习题解析24.1-数据类型、控制结构、函数1、数据类型与表达式1.类型修饰符不能修饰_____ A.charB.intC.longintD.float2.下列选项中,合法的整型常量的是_____A.60 B.01a C.986,012 D.2e53.字符串"\t\v\\\0which\n"的长度是_____A......
  • 通信原理练习题解析(详细版)
    文章目录说明选择填空简答分析计算说明部分内容,仅为个人观点,如有错误之处,欢迎交流!选择属于数字信号的是(A)​A:PCM信号B:PAM信号C:PDM信号D:PPM信号PCM信号(PulseCodeModulation,脉冲编码调制):P将模拟信号转换为数字信号的方法PDM信号(PulseDensityModula......
  • Public Round #13 题解
    旋转序列来源:IzbornePripreme2022(CroatianIOI/CEOITeamSelection)Day1,ProblemBhttps://qoj.ac/contest/956/problem/4326两个串之间\(1\)匹配的次数总和为\(k\timesl\),并且共有\(n\)次匹配。于是答案的上界为\(k\timesl\)个球放进\(n\)个盒子,最小化......
  • C++基础语法——《循环结构》题解
    循环结构参考资料:https://blog.csdn.net/m0_56945138/article/details/118929416需要掌握:1.for循环用法2.while循环用法3.continue跳过和break终止题号题目名称题解链接3067输出范围内的整数https://www.cnblogs.com/jyssh/p/182740551206简单的累加https://www......
  • [JLU] 数据结构与算法上机题解思路分享-第一次上机
    前言首先,请务必自己尽全力尝试实现题目,直接看成品代码,思维就被拘束了,也很容易被查重。这里只是思路解析的博客,代码仓库是JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A调皮的哈利分数30作者朱允刚单位吉林大学贝蒂是个打字高手,打字时有不看屏幕的习......
  • abc360_G Suitable Edit for LIS 题解
    题目链接:Atcoder或者洛谷来讲讲纯降智做法,不需要任何智商的做法,顺带整活:对于一个\(LIS\)可以拆成\(preLIS+sufLIS\),而我们现在至多可以修改一个点,那么如果\(preLIS\)的末尾元素为\(x\),\(sufLIS\)的末尾元素为\(y\),那么如果有\(y-x\ge2\),那么我们可以至少找到一个元......
  • C语言 | Leetcode C语言题解之第188题买卖股票的最佳时机IV
    题目:题解:intmaxProfit(intk,int*prices,intpricesSize){intn=pricesSize;if(n==0){return0;}k=fmin(k,n/2);intbuy[k+1],sell[k+1];memset(buy,0,sizeof(buy));memset(sell,0,sizeof(sell));......