上海计算机学会2026年月7月赛C++丙组T2 翻转字符

翻转字符题目描述有一个字符串记为TTTTTT一开始是空串。TTT可以接受新字符每当TTT收到一个新字符时它会把新字符安置在最后一个位置然后把自己整体翻转一下第一个字符变最后一个字符最后一字符变第一个字符其他字符以此类推。给定一长串字符序列SSS表示TTT所获得的字符序列。请将SSS中的字符逐一添加到TTT输出TTT最后的形态。输入格式一串字符表示给定的字符序列。输出格式TTT最后的形态为一个字符串。数据范围记∣S∣|S|∣S∣表示给定的字符串长度对于50%50\%50%的数据1≤∣S∣≤1,0001 \leq |S| \leq 1,0001≤∣S∣≤1,000对于100%100\%100%的数据1≤∣S∣≤500,0001 \leq |S| \leq 500,0001≤∣S∣≤500,000保证输入的字符串由可见字符构成。样例样例1输入:abc输出:cab说明:a--ba--cab题目来源: 改编自 ARC077A题解拿到这道题我首先按照题目描述手动模拟了若干小例子试图找到规律。设输入字符串为s长度为n下标从 0 开始。当n1T s0n2初始空加s0→s0翻转不变加s1→s0 s1翻转 →s1 s0n3s2 s0 s1n4s3 s1 s0 s2n5s4 s2 s0 s1 s3观察输出序列的下标顺序n5→4, 2, 0, 1, 3n4→3, 1, 0, 2n3→2, 0, 1n2→1, 0很容易看出规律最终结果 先逆序输出所有与n-1同奇偶的下标从大到小再顺序输出所有与n-1异奇偶的下标从小到大。等价地第一部分是n-1, n-3, n-5, ...直到 0第二部分是n%2, n%22, n%24, ...直到 n。为什么会这样每次操作相当于把新字符放到末尾然后整体翻转这个过程等价于把新字符“插入”到最终序列的头部或者说每次新字符都会跑到最终序列的最前面但后续的翻转会让它的位置不断变化。通过推导可以发现每个字符最终的位置只取决于它的原始下标和n的奇偶性最终排列正是按奇偶分组分别反向和正向输出。于是我的算法就不需要真的去模拟翻转操作只需要根据上述规律直接构造答案。代码非常简单第一个循环从最后一个下标开始每次递减 2输出对应的字符这部分对应的是与n-1同奇偶的下标逆序第二个循环从n%2即 0 或 1开始每次递增 2输出对应的字符这部分对应另一组下标顺序。这样时间复杂度 O(n)空间复杂度 O(1)不算输入存储完美满足 5e5 的数据规模。下面是带注释的完整代码#includebits/stdc.husingnamespacestd;intmain(){string s;cins;// 读入原始字符序列intns.size();// 字符串长度// 第一部分输出所有与 (n-1) 同奇偶的下标逆序// 即从最后一个开始每次跳 2 个位置for(intin-1;i0;i-2){couts[i];}// 第二部分输出所有与 (n-1) 异奇偶的下标顺序// 起始下标为 n%2当 n 为奇数时从 1 开始偶数时从 0 开始// 每次加 2直到超出范围for(inti(n%2);in;i2){couts[i];}return0;}