2026年【江苏“信息与未来”编程思维】真题及题解T4折纸题目描述Dr. X 拿出了一张正方形纸将其划分成2 n × 2 n 2^n \times 2^n2n×2n个大小相等的小格子。纸有正、反两面初始时纸正面朝上。Dr. X 将会按照指定的顺序折叠这张纸每次折叠都沿中线将纸对折共分四种方向如图所示D (Down)上半部分向下折盖在下半部分上。U (Up)下半部分向上折盖在上半部分上。R (Right)左半部分向右折盖在右半部分上。L (Left)右半部分向左折盖在左半部分上。对折时被翻折的部分会整体翻转被翻折的部分正面和反面互换且原本在最底层的格子折叠后会翻到最上层翻转后的部分作为一个整体叠加到另一半的上方。经过2 n 2n2n次折叠后纸最终被折成一个1 × 1 1 \times 11×1的方块由2 2 n 2^{2n}22n层格子叠成。Dr. X 想知道初始时位于左上角( 1 , 1 ) (1, 1)(1,1)的那个格子最终在方块中的第几层从上往下数最上面一层为第1 11层以及它的正面是朝上还是朝下。输入格式输入共两行。第一行一个正整数n nn表示纸张的边长为2 n 2^n2n。第二行一个由 D、U、R、L 组成的字符串长度为2 n 2n2n描述折叠的顺序。保证其中恰好包含n nn个纵向折叠D 或 U和n nn个横向折叠R 或 L。输出格式输出两个值用空格分隔第一个是一个整数表示左上角格子从上往下数所在的层数第二个是一个字符U 表示正面朝上D 表示正面朝下。输入输出样例 1输入 11 DR输出 12 U输入输出样例 2输入 22 DRUR输出 211 D说明/提示样例 1 解释初始纸张为2 × 2 2 \times 22×2。四个格子分别为( 1 , 1 ) (1,1)(1,1)、( 1 , 2 ) (1,2)(1,2)、( 2 , 1 ) (2,1)(2,1)、( 2 , 2 ) (2,2)(2,2)全部正面朝上。第1 11次 D上半部分( 1 , 1 ) (1,1)(1,1)和( 1 , 2 ) (1,2)(1,2)向下折盖在下半部分上。折叠后纸变为1 × 2 1 \times 21×2两层左列从上到下( 1 , 1 ) (1,1)(1,1)朝下、( 2 , 1 ) (2,1)(2,1)朝上。右列从上到下( 1 , 2 ) (1,2)(1,2)朝下、( 2 , 2 ) (2,2)(2,2)朝上。第2 22次 R左列向右折盖在右列上每层翻转。折叠后纸变为1 × 1 1 \times 11×1共4 44层从上到下依次为( 2 , 1 ) (2,1)(2,1)朝下、( 1 , 1 ) (1,1)(1,1)朝上、( 1 , 2 ) (1,2)(1,2)朝下、( 2 , 2 ) (2,2)(2,2)朝上。数据规模对于40 % 40\%40%的数据满足n ≤ 8 n \le 8n≤8。对于100 % 100\%100%的数据满足1 ≤ n ≤ 15 1 \le n \le 151≤n≤15。思路分析当前纸有r行c列小方格初始r c 2 n r c 2^nrc2n。每个小方格处叠了t层纸初始t 1。只跟踪初始左上角格子(x, y)它在当前纸中的位置p它在所在堆叠中从上到下的层数f它正面是否朝上。每次折叠时被翻折的一半称为 A固定的一半称为 B。若目标在 AA 整体翻转层序反转p t - p 1正面/反面互换f !f坐标对称映射到 B 的位置并归一化。若目标在 BA 的t层压在它上面p t p朝向不变坐标只需在 B 内部归一化。然后总层数翻倍t * 2相应行数或列数减半。最终输出p和朝向。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn;string s;cinns;intr1n,c1n;//当前行数、列数intx1,y1;//目标格子位置longlongt1,p1;//当前总层数、目标格子的层号boolf1;//1正面朝上,0正面朝下for(charch:s){if(chD||chU){//纵向折叠inthr/2;//一半行数if(chD){//上半向下折盖在下半上if(xh){//目标在被翻折的上半pt-p1;//层号反转f!f;//朝向翻转xh-x1;//对称映射}else{//目标在固定的下半ptp;//上方压入翻折层xx-h;//归一化}}else{//U下半向上折盖在上半上if(xh){//目标在被翻折的下半pt-p1;//层号反转f!f;//朝向翻转xr-x1;//对称映射}else{//目标在固定的上半ptp;//上方压入翻折层// x 不变}}rh;//行数减半}else{//横向折叠inthc/2;//一半列数if(chR){//左半向右折盖在右半上if(yh){//目标在被翻折的左半pt-p1;//层号反转f!f;//朝向翻转yh-y1;//对称映射}else{//目标在固定的右半ptp;//上方压入翻折层yy-h;//归一化}}else{//L右半向左折盖在左半上if(yh){//目标在被翻折的右半pt-p1;//层号反转f!f;//朝向翻转yc-y1;//对称映射}else{//目标在固定的左半ptp;//上方压入翻折层// y 不变}}ch;//列数减半}t*2;//总层数翻倍}coutp (f?U:D)\n;return0;}功能分析程序只跟踪初始左上角格子不模拟全部格子。每次折叠时根据方向判断该格子属于被翻折部分还是固定部分更新它的层号、朝向和位置同时更新总层数和纸张尺寸。时间复杂度为O(2n) O(n)空间复杂度为O(1)。更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}