P8453 「SWTR-8」美元巨大题目背景输出不允许有前导零。原题目名称为「美元巨大二的二的二的二的二」。小 A 喜欢用形如2 2 2 2 2 \Huge 2 ^ {2 ^ {2 ^ {2 ^ {2}}}}22222的幂塔把小 T 的博客炸掉。题目描述小 A 有n nn个2 22的幂a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_na1​,a2​,⋯,an​。他要在这些数之间插入x xx个异或运算符和y yy个或运算符组成一个表达式。保证x y n − 1 x y n - 1xyn−1。表达式越大越有可能炸掉小 T 的博客。小 A 希望从左往右计算表达式时它的值最大。他想知道表达式最大可能的取值是多少用二进制表示。他还希望你构造出这样的表达式因为他懒得自己构造了。若存在多组构造方案输出任意一组。多组测试数据。输入格式第一行一个整数S SS表示该测试点的编号。第二行一个整数T TT表示数据组数。接下来T TT组测试数据每组数据形如第一行三个整数n , x , y n, x, yn,x,y。第二行n nn个整数b i b_ibi​表示a i 2 b i a_i 2 ^ {b_i}ai​2bi​。输出格式对于每组测试数据第一行输出一个二进制数表示答案。不允许有前导零除非答案为0 00。第二行输出一个长为n − 1 n - 1n−1的由^和|组成的字符串其中s i ˆ s_i \texttt{\,\,\^{}\,\,}si​ˆ表示a i a_iai​与a i 1 a_{i 1}ai1​之间的运算符为异或s i | s_i \texttt |si​|表示该运算符为或。你需要保证^的个数为x xx|的个数为y yy。输入输出样例 #1输入 #10 4 4 0 3 1 0 6 4 8 5 2 1 5 5 7 1 5 5 7 1 0 0 15 4 3 0 65535 65535 57 57输出 #11010011 ||| 10100000 ^|^^^^| 1000000000000000 0 ^^^说明/提示「评分方式」对于每组测试数据若你输出的第一行比标准答案劣得 0 分。若你输出的第一行比标准答案优则 checker 将检查你的构造方案是否正确。若正确则返回_fail表现为测试点 UKE否则得 0 分。否则你输出的第一行和标准答案一样。若构造方案不正确得 0.6 分否则得 1 分。每个测试点的得分为测试点内所有测试数据的得分的最小值乘以该测试点的分值。注意checker 能检测出你的答案比标准答案优的前提是输出完全符合格式。一旦输出不符合格式得 0 分。格式限制包括但不限于第一行不得输出除0和1以外的字符。第二行不得输出除^和|以外的字符且字符串长度恰为n − 1 n - 1n−1。^的个数恰为x xx|的个数恰为y yy。「数据范围与约定」测试点 #110 points所有b i b_ibi​互不相等。测试点 #220 points所有b i b_ibi​相等。测试点 #330 pointsn ≤ 8 n \leq 8n≤8。测试点 #425 pointsn ≤ 10 3 n \leq 10 ^ 3n≤103。测试点 #515 points无特殊限制。对于100 % 100\%100%的数据1 ≤ T ≤ 20 1\leq T\leq 201≤T≤20。1 ≤ n ≤ 2.5 × 10 4 1 \leq n \leq 2.5 \times 10 ^ 41≤n≤2.5×104。0 ≤ x , y n 0 \leq x, y n0≤x,ynx y n − 1 x y n - 1xyn−1。1 ≤ a i 2 2 2 2 2 1\leq a_i 2 ^ {2 ^ {2 ^ {2 ^ 2}}}1≤ai​22222即0 ≤ b i 65536 0\leq b_i 655360≤bi​65536。「帮助与提示」关于 位运算。请注意 IO 优化。「题目来源」Sweet Round 8 BIdea SolutionAlex_Wei。Testerchenxia25。C实现#includebits/stdc.husingnamespacestd;boolMbe;constexprintN2.5e45;constexprintW116;intn,x,y,a[N],op[N];intbuc[W],ans[W],lst[W];boolMed;intmain(){intS,T;cinST;while(T--){memset(op,0,sizeof(op));memset(buc,0,sizeof(buc));memset(ans,0,sizeof(ans));cinnxy;for(inti1;in;i)cina[i],buc[a[i]],lst[a[i]]i;for(intiW-1;~i;i--)if(buc[i]1)ans[i]1;elseif(ybuc[i])ans[i]op[lst[i]]1,y--;for(intin;y;i--)if(!op[i])op[i]1,y--;boolflag0;for(intiW-1;~i;i--)if(ans[i]||flag)coutans[i],flag1;if(!flag)cout0;cout\n;for(inti2;in;i)cout(op[i]?|:^);cout\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容