1. 项目概述从一道蓝桥杯ALGO题看序列问题的核心最近在整理蓝桥杯的历年练习题翻到了ALGO-934这道关于“序列”的题目。很多刚开始接触算法竞赛的同学一看到“序列”两个字可能就有点发怵觉得这背后是不是藏着特别复杂的数学公式或者高深的数据结构。其实不然序列问题可以说是算法竞赛中最经典、也最“接地气”的一类问题它考察的往往是你对基础逻辑的掌控能力和将问题抽象化的基本功。这道ALGO-934就是一个非常典型的入门级序列处理题它不要求你掌握动态规划求最长子序列也不涉及复杂的字符串匹配核心就是考察你如何用程序语言比如C语言清晰、高效地描述并解决一个关于序列操作的规则。简单来说这类题目会给你一个序列可能是一串数字也可能是一串字符然后定义一些操作规则比如交换特定位置的元素、按某种规律重新排列、或者计算序列的某种特征值。你的任务就是读懂规则并用代码精确地实现它。这听起来像是简单的模拟题但其中对数组下标的控制、对边界条件的判断、以及对执行效率的初步考量恰恰是编程能力最直接的体现。我之所以选择拆解这道题是因为它完美地串联起了从问题理解、逻辑梳理到代码实现的全过程非常适合用来巩固C语言基础和训练计算思维。无论你是正在备战蓝桥杯还是单纯想提升自己的编程解题能力吃透这类题目都会大有裨益。2. 题目核心逻辑与需求拆解拿到任何一道算法题第一步永远不是急着写代码而是彻底读懂题目并用自己的话把需求拆解清楚。我们假设ALGO-934的题意大致如下注由于原题描述可能较长此处根据“序列”和常见训练题风格进行合理重构给定一个长度为N的整数序列A并定义一种操作你可以选择序列中相邻的两个元素如果它们的和为奇数则可以交换它们的位置。题目询问在经过任意次可以是零次这样的操作后该序列能否被排列成非递减即从小到大的顺序。2.1 问题本质的转化初看之下这个“交换相邻且和为奇数的元素”的操作规则有点绕。我们需要透过现象看本质。关键点在于“和为奇数”。两个整数的和为奇数意味着什么在数论中一个简单的性质是奇数 偶数 奇数。也就是说只有当一个数是奇数另一个数是偶数时它们的和才可能是奇数。两个奇数相加得偶数两个偶数相加也得偶数。因此这个操作规则实际上允许我们交换任意一个奇数和一个偶数只要它们在序列中是相邻的。一旦我们理解了这一点整个问题就从一个具体的“交换操作”抽象成了一个更宏观的“元素分类与移动”问题。序列中的所有元素被天然地分成了两类奇数类和偶数类。操作允许我们在相邻位置上交换一个奇数和一个偶数。2.2 可达性分析什么情况下可以排序成功我们的目标是能否将序列排成非递减序。既然操作只允许在奇偶性不同的相邻元素间交换那么一个直接的推论是在排序后的目标序列中所有奇数的相对顺序必须与原始序列中所有奇数的相对顺序保持一致同样所有偶数的相对顺序也必须与原始序列中偶数的相对顺序保持一致。为什么想象一下如果我们想把某个奇数A移动到更前面的位置它需要一路和前面的元素交换。如果它前面是一个偶数那么可以交换奇数A就前移了一位。如果它前面是另一个奇数B那么根据规则它们不能直接交换因为奇奇偶。为了越过奇数B奇数A必须等待一个“契机”——即一个偶数出现在它们之间通过和这个偶数交换间接地调整位置。但是无论中间经过多少轮与偶数的交换奇数A和奇数B在序列中的前后关系谁在左谁在右是无法改变的。因为每一次有效的交换都发生在奇偶之间不会改变奇数与奇数之间的相对位置。同理偶数之间也是如此。所以这个问题的解就变得非常清晰我们分别从原始序列和目标序列即排序后的序列中按顺序提取出所有的奇数和所有的偶数形成两个子序列。如果原始序列的奇数子序列与目标序列的奇数子序列完全相同元素值及顺序并且原始序列的偶数子序列与目标序列的偶数子序列也完全相同那么通过有限次操作一定可以将原序列转化为目标序列。否则则不能。注意这里有一个非常重要的隐含条件就是序列中的元素值可能有重复。我们的判断是基于“稳定排序”的概念即对于值相同的元素需要保持它们原始的相对顺序吗在这个问题中由于我们只关心奇偶性类别内部的顺序而相同值的元素其奇偶性必然相同。因此如果目标序列中两个相同值的奇数顺序与原序列不同也意味着无法达成。所以我们的“完全相同”判断必须是严格的顺序一致。2.3 输入输出与数据规模考量在动手编码前我们还需要明确题目的技术性要求这通常隐藏在输入输出格式和数据范围中。输入格式第一行是一个整数N表示序列长度。第二行是N个用空格隔开的整数表示序列A。输出格式输出一行如果可以通过所述操作排成非递减序则输出“Yes”否则输出“No”。数据范围这是决定我们算法复杂度的关键。对于蓝桥杯的ALGO练习题N通常在10^5以内。这意味着我们的算法时间复杂度必须控制在O(N log N)或更好O(N^2)的暴力排序或模拟交换肯定会超时。基于上述分析我们的算法核心步骤已经浮现读入原始序列origin。生成原始序列的副本并排序得到目标序列target。分别从origin和target中按顺序提取出所有奇数存入数组odd_origin和odd_target。分别从origin和target中按顺序提取出所有偶数存入数组even_origin和even_target。比较odd_origin与odd_target是否完全一致以及even_origin与even_target是否完全一致。如果两个比较都通过输出“Yes”否则输出“No”。这个算法的时间复杂度主要消耗在排序步骤即O(N log N)以及一次O(N)的遍历提取和比较完全可以在规定时间内完成。3. 核心算法实现与C语言代码精讲理论分析清楚了接下来就是落地到代码。我们用C语言来实现因为它足够底层能很好地体现对内存和过程的控制。我会逐块解释代码并分享一些编码时的细节和技巧。3.1 数据结构设计与输入处理首先我们需要存储序列。根据数据范围假设N最大为100000我们可以在栈上分配一个大小固定的数组但更通用的做法是使用动态内存分配。#include stdio.h #include stdlib.h #include stdbool.h // 使用bool类型更清晰 // 假设最大数据范围或者动态分配 #define MAX_N 100000 int main() { int n; scanf(%d, n); int* origin (int*)malloc(n * sizeof(int)); int* target (int*)malloc(n * sizeof(int)); int* odd_origin (int*)malloc(n * sizeof(int)); int* odd_target (int*)malloc(n * sizeof(int)); int* even_origin (int*)malloc(n * sizeof(int)); int* even_target (int*)malloc(n * sizeof(int)); if (!origin || !target || !odd_origin || !odd_target || !even_origin || !even_target) { // 内存分配失败处理竞赛中可简单返回但好习惯是判断 return -1; } for (int i 0; i n; i) { scanf(%d, origin[i]); target[i] origin[i]; // 复制一份用于排序 }实操心得在竞赛中如果题目明确给出了N的最大值且不大比如10^5直接定义全局数组int arr[MAX_N]是更简单且安全的选择避免了动态内存分配的麻烦和潜在失败。这里使用malloc是为了展示更通用的写法。务必记得malloc后应在程序末尾free。3.2 排序与奇偶子序列提取接下来我们对target数组进行排序并同时遍历origin和target分离奇偶。// 1. 对目标序列排序 (使用C标准库的qsort) int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); } qsort(target, n, sizeof(int), compare); // 2. 提取奇偶子序列 int odd_o_idx 0, even_o_idx 0; int odd_t_idx 0, even_t_idx 0; for (int i 0; i n; i) { // 提取原序列的奇偶 if (origin[i] % 2 ! 0) { // 奇数 odd_origin[odd_o_idx] origin[i]; } else { // 偶数 even_origin[even_o_idx] origin[i]; } // 提取目标序列的奇偶 if (target[i] % 2 ! 0) { odd_target[odd_t_idx] target[i]; } else { even_target[even_t_idx] target[i]; } }关键点解析排序函数我们使用了C标准库的qsort。需要自己定义一个比较函数compare。这里return (*(int*)a - *(int*)b);实现的是升序排序。这是竞赛中最常用的快速排序实现效率为O(N log N)。奇偶判断使用% 2取模运算。注意在C语言中对负数取模的结果可能是负数。但在这个问题中通常序列元素是非负整数或题目保证是正整数所以用% 2 ! 0判断奇数没问题。如果题目可能包含负数更稳妥的判断奇偶的方法是(x 1) ! 0或(x % 2 ! 0)结合对负数的处理例如((x % 2) 2) % 2 1但绝大多数竞赛题会避开这个坑。索引管理我们用了四个独立的索引odd_o_idx,even_o_idx等来记录各自数组当前填充到的位置。这是一种清晰且高效的数据组织方式。3.3 序列比较与结果输出最后比较两个奇数子序列和两个偶数子序列是否完全相同。// 3. 比较奇偶子序列 bool can_sort true; // 首先检查长度是否一致理论上应该一致因为奇偶数总数不变 if (odd_o_idx ! odd_t_idx || even_o_idx ! even_t_idx) { can_sort false; } else { // 逐个比较奇数序列 for (int i 0; i odd_o_idx; i) { if (odd_origin[i] ! odd_target[i]) { can_sort false; break; } } // 如果奇数序列已通过再比较偶数序列 if (can_sort) { for (int i 0; i even_o_idx; i) { if (even_origin[i] ! even_target[i]) { can_sort false; break; } } } } // 4. 输出结果 if (can_sort) { printf(Yes\n); } else { printf(No\n); } // 5. 释放动态分配的内存 free(origin); free(target); free(odd_origin); free(odd_target); free(even_origin); free(even_target); return 0; }注意事项提前退出在比较循环中一旦发现不匹配立即设置can_sort false并break可以避免不必要的后续比较。内存释放虽然对于竞赛单次运行的程序操作系统会回收内存但养成malloc/free配对的好习惯对长期编程至关重要。输出格式务必严格按照题目要求输出“Yes”和“No”注意大小写。很多选手在这里因为拼写或大小写错误丢分非常可惜。3.4 算法正确性证明与复杂度分析正确性证明我们的算法基于一个核心观察操作不改变同类奇数与奇数、偶数与偶数元素的相对顺序。因此最终排好序的序列其奇数部分必然是原序列奇数部分排序后的结果偶数部分亦然。我们通过分别提取并比较排序前后奇偶子序列是否一致验证了该必要条件是否满足。同时这个条件也是充分的如果子序列一致我们可以通过一系列“冒泡”式的交换将每个元素移动到其目标位置。具体地可以分别对奇数序列和偶数序列进行模拟由于同类内部顺序已正确只需处理异类间的相邻交换这总是可以完成的。复杂度分析时间复杂度O(N log N)。主导因素是qsort的排序时间。后续的提取和比较操作都是O(N)的线性扫描。空间复杂度O(N)。我们额外分配了最多6个大小为N的数组原始、目标、两个奇数数组、两个偶数数组。在实际优化中可以只分配2个原始和目标然后通过原地比较来节省空间但代码会稍复杂。对于N10^5这个空间消耗约6 * 10^5 * 4字节 ≈ 2.4MB在竞赛允许的内存限制通常128MB或256MB内是完全可以接受的。4. 优化思路与代码精简技巧上面的代码为了清晰将步骤完全拆开。在实际竞赛中我们可以在保证可读性的前提下进行一些精简和优化。4.1 空间优化减少数组使用我们其实不需要显式地存储四个子序列数组。可以在排序后同时遍历原序列和排序后的序列并实时比较奇偶类别和顺序。思路使用两个指针i和j分别遍历原序列和排序后的序列。同时维护两个“队列”或直接用索引模拟分别用于存放当前待匹配的奇数和偶数。 但更简单的方法是在遍历排序后序列时我们分别从原序列中按顺序“消耗”奇数和偶数。具体实现先对原序列排序得到目标序列。初始化两个指针odd_ptr 0,even_ptr 0它们不是指向数组而是指向原序列中下一个待匹配的奇数或偶数的“位置”。但我们需要知道原序列中奇数和偶数的顺序。所以我们先遍历一遍原序列将奇数和偶数的值分别按顺序存储到两个数组odd_orig和even_orig中。这步无法省略。然后遍历排序后的目标序列。对于目标序列中的每个数target[k]如果它是奇数则检查它是否等于odd_orig[odd_ptr]。如果是odd_ptr否则输出“No”并结束。如果它是偶数则检查它是否等于even_orig[even_ptr]。如果是even_ptr否则输出“No”并结束。如果遍历完整个目标序列都没有失败则输出“Yes”。这个优化版本将存储从6个数组减少到3个原序列、目标序列、奇数原序列、偶数原序列但后两个可以合并为两个列表并且比较过程在一次遍历中完成逻辑更紧凑。4.2 使用C STL简化代码如果语言选择允许虽然题目要求可能是C语言但蓝桥杯也允许使用C。如果使用C代码可以大幅简化利用vector和algorithm库。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint a(n), odd_orig, even_orig; for (int i 0; i n; i) { cin a[i]; if (a[i] 1) odd_orig.push_back(a[i]); else even_orig.push_back(a[i]); } vectorint b a; sort(b.begin(), b.end()); int odd_idx 0, even_idx 0; for (int x : b) { if (x 1) { if (odd_idx odd_orig.size() || odd_orig[odd_idx] ! x) { cout No endl; return 0; } odd_idx; } else { if (even_idx even_orig.size() || even_orig[even_idx] ! x) { cout No endl; return 0; } even_idx; } } cout Yes endl; return 0; }C版本利用了vector的动态扩容省去了手动管理内存和索引的麻烦sort函数也更简洁。(x 1)是判断奇偶的位运算方法效率略高于取模。4.3 边界条件与测试用例设计在实现算法后必须用多种测试用例验证其正确性。基础用例输入3\n1 2 3 排序后1 2 3奇数序列[1, 3]偶数序列[2]与目标一致输出Yes。输入3\n1 3 2 排序后1 2 3奇数序列[1, 3]偶数序列[2]与目标一致输出Yes。虽然原序列无序但奇偶内部顺序正确否定用例输入3\n2 1 4 排序后1 2 4原奇数序列[1]原偶数序列[2, 4]目标奇数序列[1]目标偶数序列[2, 4]。看起来一致等等原序列是[2(偶), 1(奇), 4(偶)]排序后是[1(奇), 2(偶), 4(偶)]。原偶数序列顺序是[2, 4]目标偶数序列顺序也是[2, 4]因为排序后偶数部分2和4本身有序。这个例子其实是Yes。我们需要一个更典型的No案例。输入3\n2 4 1 排序后1 2 4。原奇数序列[1]原偶数序列[2, 4]目标奇数序列[1]目标偶数序列[2, 4]。还是Yes。关键在于偶数内部的顺序[2,4]无论在原序列还是目标序列中都是升序所以不变。构造一个No的用例需要让同类元素内部的顺序在排序前后发生变化。例如3\n3 1 2排序后1 2 3。原奇数序列[3, 1]目标奇数序列[1, 3]。顺序不同输出No。完美。特殊用例全奇数序列3\n5 3 1- 排序后1 3 5奇数序列顺序改变输出No。全偶数序列3\n4 2 6- 排序后2 4 6偶数序列顺序改变输出No。单个元素1\n7- 输出Yes。包含重复元素4\n2 2 1 1- 排序后1 1 2 2。原奇数序列[1, 1]原偶数序列[2, 2]目标序列相同输出Yes。4\n2 1 2 1- 排序后1 1 2 2。原奇数序列[1, 1]原偶数序列[2, 2]输出Yes。4\n1 2 2 1- 排序后1 1 2 2。原奇数序列[1, 1]顺序是第一个1最后一个1目标奇数序列[1, 1]输出Yes。这里重复元素不影响因为值相同。包含负数和零需确认题目定义。通常零被视为偶数。负数取模判断奇偶需谨慎。踩坑记录我最开始思考时曾陷入一个误区试图去模拟交换过程或者去计算每个奇数和偶数需要移动的“距离”是否可行。这会使问题复杂化。后来才醒悟关键在于抓住“相对顺序不变”这一本质特性。这道题给我的最大启发就是对于这类带有约束条件的操作问题首先要分析该约束下哪些“不变量”是保持不变的。找到不变量问题往往就迎刃而解。5. 从ALGO-934延伸的序列问题通用解题框架通过深入剖析ALGO-934我们可以提炼出一套解决类似序列操作问题的通用思考框架。这对于备战蓝桥杯或任何算法竞赛都非常有用。5.1 问题分类与识别序列问题在竞赛中大致可分为几类模拟类题目直接给出操作步骤要求模拟过程得到结果。关键在于准确实现规则注意边界和效率。贪心类要求通过一系列操作使序列满足某种条件每次操作有特定规则。需要证明贪心策略的最优性。动态规划类通常求最长上升子序列、最大子序列和等。状态设计是关键。数学/性质分析类ALGO-934就属于这类。操作背后隐藏着数学规律或不变性。解题核心是发现规律而非暴力模拟。5.2 四步解题法第一步彻底理解规则与目标仔细阅读题目明确初始序列、允许的操作、以及最终要达到的目标。用简单的例子手动模拟感受操作的过程和限制。第二步寻找不变量与规律这是解决分析类序列问题的核心。问自己在允许的操作下序列的哪些属性是始终保持不变的元素总和乘积某些元素的奇偶性、位置奇偶性特定类别元素如奇数、偶数、质数的相对顺序序列的某种“势能”或“逆序对”数量变化的规律在ALGO-934中不变量就是“奇数间的相对顺序”和“偶数间的相对顺序”。第三步转化问题并设计算法利用发现的不变量将原问题转化为一个更简单、更容易判断的问题。在ALGO-934中问题转化为比较排序前后奇偶子序列是否一致。根据转化后的问题设计高效的算法排序、遍历、匹配等。评估算法的时间复杂度和空间复杂度确保在数据范围内可行。第四步实现、测试与优化编写清晰、结构化的代码。设计全面的测试用例包括最小规模用例如N1。边界用例如全奇数、全偶数、已排序、逆序。包含重复元素的用例。自己构造的、能触发算法分支的用例。检查输入输出格式确保完全符合题目要求。5.3 举一反三类似题目思路点拨掌握了这个框架再看一些类似的题目就会觉得思路清晰很多题目变体1如果操作变成“可以交换任意两个和为奇数的元素不一定相邻”结果会怎样分析操作范围扩大了。现在任何奇数和偶数都可以直接交换。这意味着所有奇数可以自由地移动到任何偶数位置反之亦然。那么只要序列中奇数的个数和偶数的个数与排序后序列中对应位置的奇偶分布兼容本质上就是排序后原来奇数位置上的数现在是否可以是奇数就有可能实现。更进一步的结论是只要序列中奇数的数量和排序后序列前k项中奇数的数量对所有k都满足某种关系类似于括号匹配就可以实现。这通常可以通过计数和比较来解决。题目变体2如果操作是“可以循环左移序列若干位”问能否得到目标序列。分析不变量是序列的循环同构性。经典解法是将原序列复制一份接在后面然后看目标序列是否是它的子串用KMP算法匹配。题目变体3给定一个01序列每次操作可以翻转一个长度为K的连续子段0变11变0问能否全变成0。分析这是经典的“开关问题”。一个关键技巧是从左到右贪心地处理固定一个顺序例如从左到右如果当前位置是1就必须翻转以该位置开始的长度为K的子段。因为前面的位置已经处理好了不能再被改变。这样扫描一遍即可。不变量是处理过程的单向性。5.4 调试与查错技巧在实现过程中如果结果不对可以按以下步骤排查小数据手工模拟用题目给的样例或自己构造的小例子N3,4在纸上一步步走一遍你的算法流程对比程序输出。打印中间变量在代码的关键步骤如排序后、提取子序列后、比较前打印出相关数组的内容看是否符合预期。检查边界条件循环的起止索引是否正确if条件是否涵盖了所有情况对于空数组如全偶数序列时奇数数组为空的处理是否安全检查输入输出是否误用了int和long longscanf/printf的格式符是否正确输出是否有多余的空格或换行复杂度再评估如果遇到大数据超时检查是否在循环内嵌套了高复杂度操作如不必要的排序、线性查找等。这道ALGO-934虽然只是一道练习阶段的题目但它蕴含的“分析不变量”的思想是解决许多中高难度竞赛题目的钥匙。在无序的练习阶段多花时间消化这类题目的本质远比盲目刷题更有价值。下次当你遇到一个关于序列操作的陌生题目时不妨先停下来想想在这个操作下到底有什么东西是永远不会改变的找到它你就找到了解题的突破口。