织梦网站后台密码忘记了怎么做中山 网站制作

织梦网站后台密码忘记了怎么做,中山 网站制作,舆情分析网站,西安seo优化培训机构题目描述 某航空公司有两班几乎同时从 ICPCity\texttt{ICPCity}ICPCity 起飞的航班#xff0c;分别飞往城市 AAA 和城市 BBB 。航空公司有 nnn 个柜台供乘客托运行李。每个柜台有一对相同的行李箱#xff0c;一个用于城市 AAA #xff0c;一个用于城市 BBB 。 在航班起飞前分别飞往城市AAA和城市BBB。航空公司有nnn个柜台供乘客托运行李。每个柜台有一对相同的行李箱一个用于城市AAA一个用于城市BBB。在航班起飞前每对行李箱被一台电动推车移动到分拣区。推车一次总是移动两个箱子一个AAA市箱一个BBB市箱。所有箱子移动后它们在分拣区排成一行B A B A B A … B AB\ A\ B\ A\ B\ A\ \ldots\ B\ ABABABA…BA也就是说有2n2n2n个行李箱排成一排从BBB市箱开始然后是AAA市箱依此类推。现在的任务是将它们重新排序使所有AAA市箱都排在所有BBB市箱之前。重新排序是通过移动相邻的一对行李箱不一定是BBB后接AAA完成的同样使用电动推车。为了保持平衡推车必须总是装载两个箱子或一个箱子加一个空位。一对箱子必须总是被移动到一个至少有两个空位的空位上。在第一个箱子的左侧有一些空位可以在重新排序过程中按需使用。给定nnn找到一个最短的移动序列能将箱子重新排序使所有AAA箱位于所有BBB箱的左侧。输入格式输入包含多个测试用例每个用例独占一行包含一个整数nnn(3≤n≤100)(3 \leq n \leq 100)(3≤n≤100)。输出格式对每个测试用例输出一个能正确重新排序箱子的最短移动序列。每次移动的形式为“ffftottt”其中fff和ttt是整数表示将位置fff和f1f1f1的箱子移动到位置ttt和t1t1t1。如果有多个解输出任意一个即可。两个连续用例的输出之间用一个空行分隔。解题思路问题分析这是一个典型的构造性递归问题。关键观察如下初始状态位置111到2n2n2n的排列为B A B A … B AB\ A\ B\ A\ \ldots\ B\ ABABA…BA。目标状态所有AAA箱在左所有BBB箱在右即A A … A B B … BA\ A\ \ldots\ A\ B\ B\ \ldots\ BAA…ABB…B。移动规则每次移动相邻的两个位置可能包含空位到至少两格宽的空位。最优性至少需要nnn次移动因为初始有nnn个B AB\ ABA逆序对每次移动最多修正一个逆序。递归构造算法通过分析问题结构我们可以发现一个递归解法1. 基本思路对于长度为2n2n2n的序列位置lll到rrr我们可以通过以下步骤将其排序前两步固定移动将最右边的一对移到左边空位然后将左边的一对移到上一步腾出的空位。递归处理中间部分[l4,r−4][l4, r-4][l4,r−4]形成了一个规模更小n−4n-4n−4的相同问题。最后两步固定移动完成剩余的对齐工作。2. 算法正确性证明定理对于所有n≥3n \geq 3n≥3上述递归算法能生成合法的nnn步移动序列将B A B A …B\ A\ B\ A\ \ldotsBABA…转换为A … A B … BA\ \ldots\ A\ B\ \ldots\ BA…AB…B。证明数学归纳法基础情况n3,5,6,7n 3, 5, 6, 7n3,5,6,7时算法使用硬编码的移动序列可以通过直接验证证明正确性。归纳假设假设对于所有knk nkn算法能正确生成移动序列。归纳步骤对于n≥8n \geq 8n≥8执行前两步固定移动后左边[l,l3][l, l3][l,l3]和右边[r−3,r][r-3, r][r−3,r]已经部分有序。中间部分[l4,r−4][l4, r-4][l4,r−4]仍然保持原始的B A B A …B\ A\ B\ A\ \ldotsBABA…模式但长度减少了888即规模减少444。根据归纳假设递归调用能正确排序中间部分。最后两步固定移动将左右部分对齐完成整个序列的排序。移动次数2(n−4)2n2 (n-4) 2 n2(n−4)2n次恰好是最优的。3. 边界情况处理对于较小的nnn我们直接使用最优移动序列n3n 3n3333步移动n5n 5n5555步移动n6n 6n6666步移动n7n 7n7777步移动这些序列是通过穷举或手工构造得到的最优解。时间复杂度算法的时间复杂度为O(n)O(n)O(n)因为每个测试用例恰好输出nnn行移动指令。递归深度为O(n)O(n)O(n)但实际递归调用次数有限。空间复杂度空间复杂度为O(1)O(1)O(1)除了递归调用栈外只使用了常数空间。代码实现// Baggage// UVa ID: 1697// Verdict: Accepted// Submission Date: 2025-12-18// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 打印移动指令voidprint(intx,inty){coutx to yendl;}// 递归处理函数// l: 当前处理区间左边界// r: 当前处理区间右边界voiddfs(intl,intr){intlenr-l1;// 当前区间长度// 长度小于等于2不需要处理if(len2)return;// 处理基本情况if(len10){// n 5print(r-2,l-2);print(l2,r-2);print(r-4,l2);print(l-1,r-4);print(r-1,l-1);return;}if(len12){// n 6print(r-2,l-2);print(r-5,r-2);print(l1,r-5);print(r-6,l1);print(l-1,r-6);print(r-1,l-1);return;}if(len14){// n 7print(l7,l-2);print(l4,l7);print(l11,l4);print(l2,l11);print(l8,l2);print(l-1,l8);print(l12,l-1);return;}// 通用递归情况长度 16 (n 8)// 前两步右边一对移到左边空位左边一对移到上一步的空位print(r-2,l-2);print(l2,r-2);// 递归处理中间部分规模减少4dfs(l4,r-4);// 最后两步完成排序print(l-1,r-5);print(r-1,l-1);}intmain(){intn;boolfirsttrue;while(cinn){// 测试用例之间用空行分隔if(!first)coutendl;firstfalse;// n 3 的特殊情况if(n3){print(2,-1);print(5,2);print(3,-3);}else{// 递归处理一般情况dfs(1,2*n);}}return0;}总结本题展示了如何通过递归构造解决排列重组问题。关键点在于发现递归结构通过固定模式的前后处理将大问题转化为小问题。证明正确性使用数学归纳法证明算法的正确性和最优性。处理边界情况小规模问题直接使用最优解。这种分而治之的递归构造方法是解决许多构造性问题的有效技巧。通过精心设计的前后处理步骤我们可以将复杂问题分解为更小的同类子问题从而实现高效求解。