东华OJ进阶题第7题 Sine之舞是我刷OJ时印象很深的一道字符串构造题。C 解法看起来就十几行但第一次做的时候我在括号和符号上反复试错后来把规律理清楚才发现其实很简单。这道题同时出现在蓝桥杯基础练习里非常适合刚学完函数递归、想找点练习题的人。题目不会直接考你数学里的正弦函数而是给你一个自定义的字符串嵌套规则让你按规则输出一个很长的表达式。你不需要真的去算sin只需要把括号、数字、加减号按规律拼出来输出和样例一致就能AC。很多新手卡在这道题不是因为代码难写而是因为看不懂题目描述里的“点儿点儿点儿”。An和Sn的定义都用省略号表示看起来一脸懵。实际上只要你把前几项手动展开规律就会非常明显。下面我把拆解过程、两种实现思路、完整可AC的C代码以及我踩过的坑都写出来希望你能一次过。1. 题目到底在说什么An和Sn的拆解1.1 先看An嵌套的sin与交替的符号题目里An的定义是这样的A1 sin(1) A2 sin(1 - sin(2)) A3 sin(1 - sin(2 sin(3))) A4 sin(1 - sin(2 sin(3 - sin(4))))看到规律了吗An是由n层sin嵌套组成的。最外层是sin(1第二层是sin(2第三层是sin(3……一直到最内层sin(n)。每一层括号里的数字从1到n递增相邻两层之间用一个运算符连接。关键在于这个运算符是交替的数字1后面是减号数字2后面是加号数字3后面又是减号数字4后面又是加号。也就是说奇数位置后面跟减号偶数位置后面跟加号最后一项sin(n)后面什么都不跟直接补右括号。这个规律用一句话就能概括从1到n每个sin(i)后面如果i不是最后一项就根据i的奇偶决定跟减号还是加号最后统一在结尾补上n个右括号。你可以自己动手验证一下A4的字符串结构就是sin(1减号sin(2加号sin(3减号sin(4))))符号位分别是1后面减号、2后面加号、3后面减号完全符合“奇数减、偶数加”的规律。1.2 再看Sn括号往左堆数字往右递减Sn的定义比An要绕一点。先看前几项长什么样S1 sin(1)1 S2 (sin(1)2)sin(1-sin(2))1 S3 ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1Sn的拼接规则是先在开头输出n-1个左括号然后从i1到n依次输出A(i)每次输出完A(i)后如果i不等于n就在后面输出一个加号和一个数字数字从n递减到2最后再单独输出一个加号和1。换句话说A(i)后面跟的数字是n-i1也就是n、n-1、n-2、……、2最后一项A(n)后面直接跟1。这个拼接过程用代码写出来更直白输出n-1个(然后循环i从1到n输出makeA(i)如果i n就追加数字)循环结束后追加1。注意这里的数字是递减的第一次循环跟的是n第二次是n-1最后一次是2。这就是题目里省略号表达的意思。提示Sn这个字符串不完全是普通数学表达式中间某些位置没有加号这是题目自定义的字符串规则。别用正常数学公式的思维去套它老老实实按字符串拼接来就行。1.3 数据规模与复杂度预期东华OJ这道题没有特别大的数据范围常见的测试点n一般不会超过100。你可以算一下A(n)的字符串长度大约是3n个字符左右Sn把所有A(i)拼起来总长度大概是3乘以1到n的累加也就是O(n²)级别。n100时整个输出字符串长度也就一万多字符直接cout和字符串拼接都完全扛得住。所以这道题不需要做什么性能优化重点是把拼接规则写对。复杂度是O(n²)空间上如果用string存储整个结果也是O(n²)对于这个数据量来说非常宽裕。你需要担心的不是性能而是别把某个右括号漏了或者把符号的奇偶判断搞反。2. 两种构造A(n)的实现思路2.1 循环拼接把每个sin(i)当作一块积木第一种写法最直观就是用一个循环把A(n)的字符串一段一段拼出来。我习惯把生成A(n)的函数单独拎出来这样主函数里每次调用就非常干净。string makeA(int n) { string res; for (int i 1; i n; i) { res sin( to_string(i); if (i n) { res (i % 2 1) ? - : ; } } for (int i 1; i n; i) { res ); } return res; }这个函数的逻辑很清晰第一段循环负责输出n个sin(i每输出一个就判断后面要不要跟符号。如果i是奇数就补减号偶数就补加号但最后一项i等于n时不补符号。第二段循环负责一次性补上n个右括号。为什么符号判断用i % 2 1因为观察展开式里1后面是减号2后面是加号3后面是减号这个交替模式刚好对应奇数减、偶数加。如果你写反了输出就会变成sin(1sin(2-sin(3...)))和题目要求完全对不上。这种循环写法还有一个优点不会递归爆栈逻辑也足够直白。哪怕你完全没写过递归也能理解。大多数通过这道题的人用的都是这种写法我推荐新手优先掌握它。2.2 递归生成更贴近题目定义如果你刚学完递归想练一练那可以用递归的方式来构造A(n)。其实A(n)可以看成一个从某个位置k开始的嵌套子问题k等于n时直接返回sin(n)否则返回sin(k加上一个符号再接上从k1开始的子问题最后补一个右括号。string makeA(int n, int k) { if (k n) { return sin( to_string(k) ); } char op (k % 2 1) ? - : ; return sin( to_string(k) op makeA(n, k 1) ); }调用的时候是makeA(i, 1)表示从数字1开始生成A(i)。比如makeA(4, 1)递归过程会一路展开成sin(1 - sin(2 sin(3 - sin(4))))这个递归写法非常贴近题目给的递推定义代码也更短。但递归版本对新手有一个门槛你要能想象出每一层返回的字符串是怎么嵌套的还要搞清楚k这个参数在递归过程中扮演的角色。如果你觉得递归绕就用2.1的循环版本效果完全一样。注意递归中和循环中用的符号规则完全一致都是k % 2 1时输出减号。千万不要因为递归看起来高级就把符号判断写反。2.3 这道题考的是字符串规律不是真的三角函数我见过有同学拿到这道题第一反应是去调用sin()数学函数试图算出一个数值来。这思路从一开始就跑偏了。题目里的sin只是一个字符串外壳真正要你做的是按照给定规则拼接字符然后把拼接好的字符串原样输出。OJ比对的是输出文本不是数学计算结果所以你完全不需要include任何数学库。理解这一点特别重要。OJ里的很多字符串构造题都是这个套路比如竖式输出、图形打印、魔方字符串旋转等等。它们不看你“算了什么”只看你“输出了什么”。碰到这种题最快的方法永远是先在纸上把n1、2、3的展开式写出来找到肉眼可见的规律再动手写代码。3. Sn怎么拼主函数完整实现与验证3.1 完整可AC代码推荐版把前面的makeA和Sn的拼接规则组合起来就是一份可以直接提交的完整代码#include iostream #include string using namespace std; string makeA(int n) { string res; for (int i 1; i n; i) { res sin( to_string(i); if (i n) { res (i % 2 1) ? - : ; } } for (int i 1; i n; i) { res ); } return res; } int main() { int n; cin n; for (int i 1; i n; i) { cout (; } for (int i 1; i n; i) { cout makeA(i); if (i n) { cout (n - i 1) ); } } cout 1 endl; return 0; }主函数的逻辑分三段。第一段输出n-1个左括号这是Sn最外层的骨架。第二段是一个循环从i1到n依次输出makeA(i)每输出一项后如果后面还有项就输出加号、递减数字和一个右括号。第三段在循环结束后输出最后的1和一个换行。如果n等于1第一段循环不会执行第二段循环只执行一次直接输出sin(1)第三段输出1结果为sin(1)1和预期完全一致。如果n等于3输出结果就是((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1这正是蓝桥杯原题的样例输出。3.2 把结果改成string返回的写法有些场景下你不想边算边输出而是希望把整个Sn构造成一个字符串拿到手里再统一处理。比如你想对比结果、二次处理、或者输出到别的地方。这时候可以把主循环里的拼接逻辑也封装成一个函数string makeS(int n) { string res; for (int i 1; i n; i) { res (; } for (int i 1; i n; i) { res makeA(i); if (i n) { res to_string(n - i 1) ); } } res 1; return res; } int main() { int n; cin n; cout makeS(n) endl; return 0; }这段代码的结构和前面完全一样只是把所有输出操作变成了字符串追加。好处是你可以很方便地在函数外面做调试比如打印字符串长度、定位某个位置的字符等等。坏处是字符串拼接会多一倍的拷贝开销但前面说过n很小完全不用担心。如果你的OJ编译器比较老不支持to_string也可以用sprintf或者先判断数字大小再手动转成字符。不过现在绝大多数OJ都支持C11to_string直接用就行。3.3 本地验证样例n1到n3我建议你在本地把n1、2、3都跑一遍和下面核对n1: sin(1)1 n2: (sin(1)2)sin(1-sin(2))1 n3: ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1这三个结果可以帮你快速验证代码对不对。n1是最简单的边界如果它都错说明基本结构有问题。n2可以帮助你检查左括号个数和数字递减逻辑。n3是最接近题目样例的数据输出和样例一致基本就稳了。实践里我都是用一个命令行参数或者直接改cin的输入把几个测试数据一次性跑完。比如在VS Code里配好C环境后把输入重定向到一个input.txt文件直接在终端里跑可执行文件比每次手动敲数字要舒服得多。3.4 换行和输出格式的小问题这道题对输出的要求比较宽松只要你打印的字符串连续且中间没有多余空格末尾换不换行一般都能过。我习惯在最后加一个endl既能让终端显示更清爽也不影响OJ判定。要注意的是千万别在字符串中间不小心输出空格或者换行。常见的情况是复制代码时把某个字符串字面量写成了两行导致编译器报错或者输出内容带空白。如果你用的是VS Code开编译输出时如果出现字符串里莫名其妙的空格优先检查代码里有没有被编辑器自动换行截断的字符串。还有一个小坑makeA(i)和后面的数字)之间不要再额外输出任何符号。我第一次写的时候习惯性地在i n的分支里写了区结果输出变成了sin(1)3)sin(1-sin(2))2)...和正确结果差了一个加号WA到怀疑人生。后来对比样例才发现Sn的定义里A(i)和数字之间只有一个加号数字后面才是右括号。4. 刷题过程中的常见问题与排查技巧4.1 右括号数量不对最容易翻车的地方这道题出错率最高的位置就是右括号数量。A(n)本身有n个右括号Sn每一层还要额外补一个右括号。很多人在写的时候会漏掉A(n)自己的右括号或者把Sn的右括号和A(n)的右括号混在一起算。我推荐一个自查方法把n4的完整输出在纸上写出来逐个数左括号和右括号数量。A(4)是sin(1-sin(2sin(3-sin(4))))里面有4个左括号和4个右括号。Sn前面有3个额外的左括号循环里每项后面有3个额外的右括号。左括号总数是7个右括号总数也是7个配对才能完全闭合。一旦你数出来两边不等就直接定位到漏括号的位置。实际写代码时最容易漏的是makeA函数里第二段循环的n个右括号。如果你忘了这个循环A(n)会变成sin(1-sin(2sin(3-sin(4))这样半截括号整段输出直接错乱。我见过很多初学者的报错输出都是左边堆了一堆左括号右边稀稀拉拉没闭合就是这个原因。4.2 加减号写反了奇数位是减号第二个高频错误是符号反了。A(n)里数字1后面是减号数字2后面是加号数字3后面是减号规律是“奇减偶加”。但是人的直觉经常觉得1后面应该是加号因为看起来像是在做加法一顺手就写成了i % 2 0。判断自己有没有写反最简单的方法是看A(2)的输出。正确的A(2)是sin(1-sin(2))中间是减号。如果你输出的是sin(1sin(2))那就是符号判断反了。由于n2的字符串很短每次改完代码先在本地跑一下n2能快速过滤掉这个错误。另外注意Sn里的加号和A(n)里的加号不是一回事。Sn里每一项后面跟的数字是固定的不会像A(n)那样奇偶切换。你在写主函数时不用在这个位置判断奇偶直接输出加号和数字就行。4.3 循环边界写错in时别再加符号makeA里有两个循环边界容易写错。第一个是符号输出的边界if (i n)才输出符号i等于n时不能再输出。第二个是补右括号的循环for (int i 1; i n; i)要循环n次不是n-1次。如果符号输出的边界写成了i n最后一项后面就会多出一个运算符比如sin(3)变成sin(3-)整个字符串直接报废。如果你补右括号的循环写成了i n那A(n)就少了最后一个右括号同样过不了样例。这两个边界问题在逻辑上都很小但在输出上非常显眼。我通常会在写完代码后把n2和n3各跑一遍对着题目样例逐字符比对。如果样例都对那说明边界基本没问题。主函数里的另一个边界也要留意for (int i 1; i n; i)输出左括号这个循环是n-1次不要写成n次。如果多输出一个左括号整体括号配对就全乱了。4.4 OJ上WA了怎么查先自己构造小数据如果你提交之后WA不要急着反复提交浪费次数先在本地把n1、2、3全部跑一遍。这三组数据能覆盖绝大多数边界问题。如果本地输出和上面列出的完全一致但OJ还是WA那就要考虑平台差异了。比如有些东华OJ的题面可能把Sn的定义改成了带加号的版本输出样例和我这里的版本不完全一样。这时候要以你正在刷的OJ题目原文和样例为准检查Sn拼接时是不是每个A(i)后面都要多加一个加号。这道题在网上流传的版本比较多蓝桥和东华OJ可能略有差异我建议你提交前先复制题目样例到本地逐字符比对最终输出。还有一个调试技巧在代码里临时把cout改成输出到字符串然后打印字符串的每个字符的ASCII码看看有没有意外空格或换行。这个方法虽然笨但对付“看起来一样其实字符不同”的问题特别有效。尤其是中文括号和英文括号混入的情况肉眼很难发现但OJ一眼就能比对出差。5. 从这道题能带走的通用套路5.1 字符串构造题先手推前几项再动手Sine之舞这类题给我的最大启发是拿到一个带省略号的字符串规则不要直接开写代码。先在纸上手推n1、n2、n3把结果完整写出来再盯着这些展开式找规律。A(n)的交替符号、Sn的递减数字如果不是看到展开式很多人根本想不出来。手推的过程其实是一个很好的“翻译”过程。题目描述里的sin(1–sin(2sin(3–...sin(n))...是在告诉你嵌套关系但你真正要写的是具体的字符串。把省略号展开后你才能知道循环的起点、终点、符号变化规律。我后来刷其他字符串题也保持着这个习惯先展开三步再抽象规律再写代码。别嫌麻烦这一步比调试省下来的时间多得多。5.2 递归题先找最小子问题如果把这道题当递归练习看它其实在教你一个通用思维找到规模最小的子问题再找到递推关系。A(n)的最小子问题是n等于1时返回sin(1)递推关系是sin(k)加上运算符再接上A(k1...n)的结果。只要这两个点想清楚递归代码自然就出来了。很多初学者觉得递归难是因为总想立刻把所有层都想清楚。其实不用递归只需要关注当前这一层和下一层的关系最内层的边界条件单独处理就好。Sine之舞里的makeA(n, k)正好是一个很好的练习k等于n是边界k小于n就继续递归每一层只负责包一个sin(k)和对应的符号。5.3 我踩坑之后的几点体会最后说几句个人经验。第一次做这道题时我在makeA里忘了补右括号输出一直是半截括号愣是看了十分钟才发现。第二次是符号写反样例输出怎么都对不上。后来我养成一个习惯任何字符串构造题先把n的最小值和样例值各跑一遍再提交。这个习惯帮我省了很多次无谓的WA。另外用VS Code写这类代码时我建议把输出窗口的换行缓冲去掉或者干脆加一个#include string后多用string操作少用裸char数组。虽然这道题用char和printf也能写但string的操作符非常适合这种字符串拼积木的场景可读性好太多了。如果你刷完了这道题可以试着改一改规则比如把符号变成“奇加偶减”或者把Sn的数字从递增变成递减再写一遍。你会发现只要掌握了“先展开、再拼接”的思路不管题目怎么变都能很快写出代码。我个人觉得这种小练习比盲刷十道同类型题更能巩固递归和字符串处理的理解。