P10369 「LAOI-4」Mex Tower (Easy ver.)题目背景本题与 Hard Version 的区别为本题需给出一个合法的方案。题目描述定义mex⁡(x,y)\operatorname{mex}(x, y)mex(x,y)表示在集合{x,y}\{x, y\}{x,y}中最小的未出现的自然数。例如mex⁡(1,5)0\operatorname{mex}(1, 5) 0mex(1,5)0mex⁡(3,0)1\operatorname{mex}(3, 0) 1mex(3,0)1。继而我们定义对自然数序列a1…ana_1\dots a_na1​…an​的一次操作是将序列aaa替换为长度为n−1\bm{n - 1}n−1的序列b1…bn−1b_1\dots b_{n-1}b1​…bn−1​其中bimex⁡(ai,ai1)b_i \operatorname{mex}(a_i, a_{i1})bi​mex(ai​,ai1​)。你需要构造一个长度为nnn的自然数序列a1…ana_1\dots a_na1​…an​满足0≤ai≤1090 \leq a_i \leq 10^90≤ai​≤109然后对它进行n−1n - 1n−1次操作。显然最终序列aaa只会剩下一个数你需要最大化这个数的值。如果有多种可能的数列可以输出任何一种合法方案。输入格式本题有多组数据。第一行一个正整数TTT表示数据组数。对于每组数据仅一行一个正整数nnn。输出格式对于每组数据输出一行nnn个整数表示你构造的a1…ana_1\dots a_na1​…an​。输入输出样例 #1输入 #13 2 5 7输出 #10 1 3 1 5 0 1 0 7 9 4 0 0 4说明/提示样例解释对于n2n 2n2我们对[0,1][0, 1][0,1]进行操作后显然会得到[2][2][2]。可以证明这是我们能得到的最大的答案。其它合法的输出如[1,0][1, 0][1,0]等也可以通过。对于n5n 5n5和n7n 7n7暂时不能给你一个明确的答复。数据规模与约定「本题采用捆绑测试」Subtask\text{Subtask}Subtask∑n≤\sum n \le∑n≤特殊性质总分值111101010无55522210510^5105A\text{A}A15151533310510^5105B\text{B}B151515444505050n≤25n\le 25n≤2510101055510310^3103无20202066610610^6106无353535特殊性质A\text{A}A保证n≡3(mod4)n\equiv 3\pmod 4n≡3(mod4)。特殊性质B\text{B}B保证n≡2(mod4)n\equiv 2\pmod 4n≡2(mod4)。对于所有数据保证1≤T≤1041 \leq T \leq 10^41≤T≤104n1n 1n1∑n≤106\sum n \leq 10^6∑n≤106。C实现#includebits/stdc.husingnamespacestd;intt,n;dequeintq;//双端队列维护头和尾的添加voidPush(intx,inty){q.push_front(x),q.push_back(y);}//添加操作intmain(){scanf(%d,t);while(t--){scanf(%d,n);while(!q.empty())q.pop_back();if(n1){//奇数行q.push_back(2);intsn/2;for(inti1;is;i){if(i%31)Push(0,2);elseif(i%32)Push(2,0);elsePush(2,2);}}else{//偶数行Push(1,0);intsn/2-1;for(inti1;is;i){if(i%31)Push(1,1);elseif(i%32)Push(0,1);elsePush(1,0);}}while(!q.empty()){printf(%d ,q.front()),q.pop_front();}putchar(\n);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容