传送门 https://codeforces.com/contest/1496/problem/B
题目
5 4 1 0 1 3 4 3 1 0 1 4 3 0 0 1 4 3 2 0 1 2 3 2 1 2 3
4 4 3 5 3
In the first test case, S={0,1,3,4}S={0,1,3,4}, a=mex(S)=2a=mex(S)=2, b=max(S)=4b=max(S)=4, ⌈a+b2⌉=3⌈a+b2⌉=3. So 33 is added into SS, and SS becomes {0,1,3,3,4}{0,1,3,3,4}. The answer is 44.
In the second test case, S={0,1,4}S={0,1,4}, a=mex(S)=2a=mex(S)=2, b=max(S)=4b=max(S)=4, ⌈a+b2⌉=3⌈a+b2⌉=3. So 33 is added into SS, and SS becomes {0,1,3,4}{0,1,3,4}. The answer is 44.
前言(写给自己的话)
最近cf做得越来越不好了, 出了A后, B就不怎么出了, 这样不行啊, 说是晚上困, 那困之前怎么不出B题? 这道题就是简单的模拟, 只有三种情况, 不应该不出, 往思维上想, 思维! 思维!
For each test case, print the number of distinct elements in S after k operations will be done. 输出有几种数, 我理解成输出出现一次的数的个数了
解析
先对数组排序,求出mex。如果操作后得到的数在数列出现过,
那么直接输出n(因为再操作也还是得到这个数),如果没在
数列出现过则输出n + 1,因为这并不会改变mex和max,再操
作还是得到这个数。如果原数列已经被填满,即mex == n,
那么就输出n + k(可以自己模拟一下)。
三种情况:
1. mex==n, 也就是说0~n-1都有, 那么每次把d=(mex + max + 1)/2加入进去, 不重合的数就+1, 重复加k次
2. 所求d在n个数里出现过, 那输出n
3. 所求d在n个数里没出现过, 那输出n+1, 因为再怎么进行, 得到的都是这一个数
代码
#include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 10; int a[N], n ; bool find(int x) { for(int i = 0; i < n; i ++) if(a[i ] == x) return 1; return 0; } int main() { int t; cin >> t; while(t --) { int k; cin >> n >> k; int maxn = 0, mex = n; for(int i = 0; i < n; i ++)//最大值永远是最大值 { scanf("%d", &a[i]); maxn = max(maxn, a[i]); } sort(a, n + a); for(int i = 0; i < n; i ++)//排序后找mex if(i != a[i] && mex == n) mex = i; if( k == 0 || find((maxn + mex + 1) / 2)) printf("%d ", n); else if(mex == n) printf("%d ", n + k); else printf("%d ", n+1); } return 0; }