D小灯做题

D题#小灯做题

题目描述

Tomori在做一个题目，这个题目初始有四个非负整数 a,b,c,k 。

每次Tomori可以对 a,b,c 进行操作：选择其中两个数 x,y，然后将剩下一个数改成 mex(x,y)。

Tomori想知道她最少操作多少次，能让 a,b,c 中的一个数变成 k。若无解，则输出−1。

mex(x,y) 表示最小的非负整数 p ，满足 p≠x 且 p≠y ，例如 mex(1,2)=0,mex(0,2)=1

分析

作为一名蒟蒻，想不出高大上的解法，只能阴暗地打表解决这题

这题的数据范围其实很小，首先判断一开始给的a,b,c有没有直接和k相同的，有就输出0； 如果没有，那么k>=3就不需要再判断，直接输出-1即可，因为题目给出abc3个数，通过mex最多只能创造出0-2（n-1）里的数

接下来就是对k==0,k==1,k==2这三种可能进行分类打表，在打表过程要注意考虑的是a,b,c可能会是重复的数，还有k==2时考虑的情况要分的多一些

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll k,a[3];

void solve() {
	cin>>a[0]>>a[1]>>a[2]>>k;//三个数输入到数组进行排序处理，方便打表
	sort(a,a+3);
	if (a[0]==k or a[1]==k or a[2]==k) { //输入的三个数已经有和k相同的情况
		cout<<0<<'\n';
		return;
	}
	if (k>=3) {//由于没有和k相同的数，那么k>=3直接输出-1
		cout<<-1<<'\n';
		return;
	} else {
		if (k==0) {
			cout<<1<<'\n';//任意两个不为0的数进行mex结果都是0
			return;
		}
		if (k==1) {
			if (a[0]==0) cout<<1<<'\n';//至少有一个0的情况，那么一次就能得到1
			else cout<<2<<'\n';//没有0就得先进行一次mex得到0
			return;
		}
		if (k==2) {
			if (a[2]==0) cout<<2<<'\n';//三个数全为0
			else if (a[2]==1 and a[0]==0) cout<<1<<'\n';//三数有1也有0
			else if (a[0]==1 and a[2]==1) cout<<2<<'\n';//三数全为1
			else if (a[0]>2) cout<<3<<'\n';//三个数全部比2大
			else if (a[1]>2) cout<<2<<'\n';//两个数比2大，那么比2小的数一定是0或者1，所以只需要2次
			else if (a[2]>2 and a[0]!=a[1]) cout<<1<<'\n';//有一个数比2大，另外两数不同（只可能分别是0和1）
			else if (a[2]>2 and a[0]==a[1]) cout<<2<<'\n';//有一个数比2大，另外两数相同（只可能同为0或者同为1）
			return;
		}
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}