P9202 「GMOI R2-T2」猫耳小加强版题目背景本题与 原题 的区别在于数据范围和输出格式。在这一版本中n ≤ 10 6 n\le 10^6n≤106值域为10 9 10^9109你需要给出构造。题目描述小 R 是一个可爱的猫耳女孩子她喜欢研究数列的mex * \operatorname{mex}\text{*}mex*。现在她有一个长度为n nn的数列a aa。她讨厌整数k kk因此她希望修改数列a aa的若干个元素为任意自然数使得a aa的任意连续非空子串的mex \operatorname{mex}mex都不等于k kk。请你求出最少需要修改多少个元素并给出方案。* \text{*}*本题中数列的mex \operatorname{mex}mex被定义为数列中最小未出现的自然数例如mex { 1 , 2 , 3 } 0 \operatorname{mex}\{1,2,3\}0mex{1,2,3}0因为0 00是自然数。mex { 0 , 1 , 3 } 2 \operatorname{mex}\{0,1,3\}2mex{0,1,3}2。mex { 0 , 1 , 2 } 3 \operatorname{mex}\{0,1,2\}3mex{0,1,2}3。输入格式第一行两个整数n , k n,kn,k表示数列长度和小 R 讨厌的数。第二行n nn个整数第i ii个整数为a i a_iai表示这个数列的第i ii项。输出格式第一行一个整数表示最少需要修改的元素个数。第二行n nn个整数表示修改后的数列。你需要保证修改后的数列的每个数在[ 0 , 10 9 ] ∩ Z [0,10^9]\cap\Z[0,109]∩Z的范围内。输入输出样例 #1输入 #15 2 1 0 1 3 0输出 #12 1 1 1 3 2说明/提示样例解释一种方案是将{ 1 , 0 , 1 , 3 , 0 } \{1,0,1,3,0\}{1,0,1,3,0}改为{ 1 , 1 , 1 , 3 , 2 } \{1,1,1,3,2\}{1,1,1,3,2}共改动两个元素。可以证明不存在更优的方案。评分方式本题采用自定义校验器Special Judge进行评测。对于每个测试点如果你的最小步数正确可以得到30 % 30\%30%的分数。在此基础上如果方案也正确可以得到满分。请注意即使你不会给出方案也请按照输出格式在第二行输出n nn个整数。本题采用捆绑测试数据无梯度。对于100 % 100\%100%的数据1 ≤ n ≤ 10 6 1\le n\le 10^61≤n≤1060 ≤ k , a i ≤ 10 9 0\le k,a_i\le 10^90≤k,ai≤109。本题读写量较大建议使用效率较高的读写方式。C实现#includebits/stdc.husingnamespacestd;#definegcgetchar#definepcputchar#defineWwhile#defineIinline#defineintlonglongnamespaceSlowIO{Iintread(){intx0,f1;charchgc();W(ch0||ch9){if(ch-)f-f;chgc();}W(ch0ch9)xx*10(ch^48),chgc();returnx*f;}IvoidRead(intx){xread();}Ivoidwrite(intx){if(x0)pc(-),x-x;if(x9)write(x/10);pc(x%100);}IvoidWrite(intx){write(x);pc( );}}usingnamespaceSlowIO;constintN1000010;intn,k;inta[N],cnt[N];setintst;signedmain(){cinnk;intans0;for(inti1;in;i)Read(a[i]);for(inti1;in;i){if(a[i]k){st.clear();continue;}if(a[i]k)st.insert(a[i]);if(st.size()k){ans;a[i]k;st.clear();}}coutansendl;for(inti1;in;i)Write(a[i]);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
