Pinely Round 2 (Div. 1 + Div. 2)C题题解

C - MEX Repetition

C - MEX Repetition 题解

由于初始数组是由 $n$ 个互不相同的 $0\sim n$ 的整数组成，所以每次替换的数 $Mex(a_1,a_2,a_3,···a_n)=\frac{n*(n+1)}{2}-sum$ 。答案看起来没什么规律，打表出来发现循环节为 $n+1$ ，故先 $k=k%(n+1)$ 。而每次的 $nums$ 每位依次向后移一位， $add$ 放到第一位，最后一位弹出

找到规律：答案数组 $ans$ 分为两部分

  • $ans$ 的前k位为每次 $add$ 的数（倒序）
  • $ans$ 的后 $n\sim k$ 位是初始数组 $nums$ 的前 $k$ 位，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstring>
using namespace std;//注意，是0~n中不同的数

typedef long long ll;
const int N=1e5+10;
int nums[N];
int ans[N];
ll n,k;
ll sum;//存现在数组和

void mex_all()
{
	ll right=n-1;
	for(int i=0;i<k;i++)
	{
		ll add=n*(n+1)/2-sum;
		sum-=nums[right--];
		sum+=add;

		ans[k-i-1]=add;
	}

	for(int i=k;i<n;i++)
	{
		ans[i]=nums[i-k];
	}
}

int main()
{
	int _;
	cin>>_;
	while (_--)
	{
		cin>>n>>k;
		sum=0;
		for(int i=0;i<n;i++)
		{
			cin>>nums[i];
			sum+=nums[i];
		}

		k=k%(n+1);

		mex_all();

		for(int i=0;i<n;i++)
		{
			cout<<ans[i]<<' ';
		}
		cout<<endl;
		
		// cout<<endl;					//打表找规律及循环节：n+1
		// for(int i=0;i<35;i++)
		// {
		// 	for(int i=0;i<n;i++)
		// 	{
		// 		int add=n*(n+1)/2-sum;
		// 		sum-=nums[i];
		// 		sum+=add;
		// 		nums[i]=add;
		// 	}
		// 	for(int i=0;i<n;i++)
		// 	{
		// 		cout<<nums[i]<<' ';
		// 	}
		// 	cout<<endl;
		// }
	}
	return 0;
}