算法竞赛中的数组与字符串处理技巧精讲

1. 数组与字符串算法精要笔记

作为算法竞赛入门阶段的核心内容，数组和字符串的处理技巧直接影响着后续复杂算法的实现能力。本章将系统梳理《算法竞赛入门经典》第3章的关键知识点，通过典型例题解析和实战代码剖析，帮助读者建立扎实的基础编程能力。

1.1 数组基础操作三连

数组是最基础也是最高效的线性存储结构，在算法竞赛中几乎无处不在。我们先看三个经典的基础操作案例：

1.1.1 逆序输出问题

#include <stdio.h> #define maxn 105 int a[maxn]; int main() { int x, n = 0; while (scanf("%d", &x) == 1) a[n++] = x; for (int i = n - 1; i >= 1; i--) printf("%d ", a[i]); printf("%d\n", a[0]); return 0; }

这个简单的程序展示了数组最基本的操作模式：

1. 动态输入数据并记录元素个数
2. 反向遍历数组输出元素

注意点：最后一个元素单独处理是为了避免末尾多余空格，这是算法竞赛中常见的输出格式要求。在实际比赛中，输出格式错误可能导致答案被判为错误。

1.1.2 开灯问题

#include <stdio.h> #include <string.h> #define maxn 1010 int a[maxn]; int main() { int n, k, first = 1; memset(a, 0, sizeof(a)); scanf("%d%d", &n, &k); for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++) if (j % i == 0) a[j] = !a[j]; for (int i = 1; i <= n; i++) if (a[i]) { if (first) first = 0; else printf(" "); printf("%d", i); } printf("\n"); return 0; }

这个程序模拟了经典的开关灯问题：

• 使用整型数组模拟灯的开关状态（0关1开）
• 通过双重循环实现开关操作
• first标志位控制输出格式

算法复杂度分析：外层循环k次，内层循环n次，总复杂度O(kn)。当k和n都≤1000时，这个复杂度完全可以接受。

1.1.3 蛇形填数

#include <stdio.h> #include <string.h> #define maxn 20 int a[maxn][maxn]; int main() { int n, x, y, tot = 0; scanf("%d", &n); memset(a, 0, sizeof(a)); tot = a[x = 0][y = n - 1] = 1; while (tot < n * n) { while (x + 1 < n && !a[x + 1][y]) a[++x][y] = ++tot; while (y - 1 >= 0 && !a[x][y - 1]) a[x][--y] = ++tot; while (x - 1 >= 0 && !a[x - 1][y]) a[--x][y] = ++tot; while (y + 1 < n && !a[x][y + 1]) a[x][++y] = ++tot; } for (x = 0; x < n; x++) { for (y = 0; y < n; y++) printf("%3d", a[x][y]); printf("\n"); } return 0; }

蛇形填数展示了二维数组的典型操作：

1. 定义方向顺序（下、左、上、右）
2. 使用while循环判断边界和已填充位置
3. 通过++tot实现自动递增填数

调试技巧：在复杂的位置移动算法中，可以先用小规模数据（如n=3）手动模拟程序执行过程，验证逻辑正确性。

1.2 字符数组与字符串处理

字符串处理是算法竞赛中的另一大核心内容，C风格的字符串以字符数组形式存储，需要特别注意结束符'\0'的处理。

1.2.1 竖式问题

#include <stdio.h> #include <string.h> int main() { int count = 0; char s[20], buf[99]; scanf("%s", s); for (int abc = 111; abc <= 999; abc++) for (int de = 11; de <= 99; de++) { int x = abc * (de % 10), y = abc * (de / 10), z = abc * de; sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z); int ok = 1; for (int i = 0; i < strlen(buf); i++) if (strchr(s, buf[i]) == NULL) ok = 0; if (ok) { printf("<%d>\n", ++count); printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n", abc, de, x, y, z); } } printf("The number of solutions = %d\n", count); return 0; }

这个程序展示了：

• 使用sprintf将数字转换为字符串
• strchr函数查找字符
• 格式化输出模拟竖式乘法

优化建议：strlen(buf)在循环中重复计算，可以先计算出长度存起来。对于大规模数据，这种优化能显著提升性能。

1.2.2 TeX引号替换

#include<stdio.h> int main() { int c, q = 1; while ((c = getchar()) != EOF) { if (c == '"') { printf("%s", q ? "``" : "''"); q = !q; } else printf("%c", c); } return 0; }

这个简洁的程序展示了：

• 使用getchar逐个读取字符
• 使用标志位q交替替换引号
• 直接处理输入流直到EOF

重要技巧：在需要处理大量输入时，getchar比scanf更高效，特别是当输入规模达到1e5以上时，这种差异会非常明显。

1.2.3 WERTYU键盘映射

#include<stdio.h> char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; int main() { int i, c; while ((c = getchar()) != EOF) { for (i=1; s[i] && s[i]!=c; i++); if (s[i]) putchar(s[i-1]); else putchar(c); } return 0; }

这个程序展示了：

• 使用常量字符串建立映射关系
• 线性查找字符位置
• 处理未映射字符的情况

优化思路：对于更大规模的映射关系，可以考虑使用哈希表提升查找效率。

2. 字符串经典问题解析

字符串处理在算法竞赛中占据重要地位，本节深入分析几个典型问题的解决思路和实现细节。

2.1 回文词判断

#include <stdio.h> #include <string.h> #include <ctype.h> const char *rev = "A 3 HIL JM O 2TUVWXY51SE Z 8 "; const char *msg[] = {"not a palindrome", "a regular palindrome", "a mirrored string", "a mirrored palindrome"}; char r(char ch) { if (isalpha(ch)) return rev[ch - 'A']; return rev[ch - '0' + 25]; } int main() { char s[30]; while (scanf("%s", s) == 1) { int len = strlen(s); int p = 1, m = 1; for (int i = 0; i < (len + 1) / 2; i++) { if (s[i] != s[len - 1 - i]) p = 0; if (r(s[i]) != s[len - 1 - i]) m = 0; } printf("%s -- is %s.\n\n", s, msg[m * 2 + p]); } return 0; }

这个程序实现了：

1. 回文判断（前后对称）
2. 镜像判断（字符映射后对称）
3. 组合判断输出结果

代码亮点：

• 使用常量字符串存储镜像映射关系
• 通过位运算组合判断结果（m*2 + p）
• 函数封装字符映射逻辑

2.2 猜数字游戏提示

#include <stdio.h> #define maxn 1010 int main() { int n, a[maxn], b[maxn]; int kase = 0; while (scanf("%d", &n) == 1 && n) { printf("Game %d:\n", ++kase); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (;;) { int A = 0, B = 0; for (int i = 0; i < n; i++) { scanf("%d", &b[i]); if (a[i] == b[i]) A++; } if (b[0] == 0) break; for (int d = 1; d <= 9; d++) { int c1 = 0, c2 = 0; for (int i = 0; i < n; i++) { if (a[i] == d) c1++; if (b[i] == d) c2++; } if (c1 < c2) B += c1; else B += c2; } printf(" (%d,%d)\n", A, B - A); } } return 0; }

这个程序实现了猜数字游戏的提示功能：

• A表示数字和位置都正确的个数
• B表示数字正确但位置不对的个数
• 通过统计每个数字的出现次数计算B值

算法分析：

• 计算A值的复杂度是O(n)
• 计算B值需要遍历1-9每个数字，复���度O(9n)
• 总体复杂度O(9n)对于n≤1000完全可行

2.3 生成元问题

#include <stdio.h> #include <string.h> #define maxn 100005 int ans[maxn]; int main() { int T, n; memset(ans, 0, sizeof(ans)); for (int m = 1; m < maxn; m++) { int x = m, y = m; while (x > 0) { y += x % 10; x /= 10; } if (ans[y] == 0 || m < ans[y]) ans[y] = m; } scanf("%d", &T); while (T--) { scanf("%d", &n); printf("%d\n", ans[n]); } return 0; }

这个程序展示了预处理技术的应用：

1. 预先计算1-100000所有数字的生成元
2. 查询时直接查表获取结果
3. 确保每个数只保留最小的生成元

优化思路：

• 预处理是空间换时间的典型策略
• 在算法竞赛中，当查询次数远大于预处理时间时，这种策略非常有效
• 预处理的范围需要根据题目要求精确计算

3. 竞赛题目精讲与实战技巧

3.1 环状序列最小表示

#include <stdio.h> #include <string.h> #define maxn 105 int less(const char *s, int p, int q) { int n = strlen(s); for (int i = 0; i < n; i++) if (s[(p + i) % n] != s[(q + i) % n]) return s[(p + i) % n] < s[(q + i) % n]; return 0; } int main() { int T; char s[maxn]; scanf("%d", &T); while (T--) { scanf("%s", s); int ans = 0; int n = strlen(s); for (int i = 1; i < n; i++) if (less(s, i, ans)) ans = i; for (int i = 0; i < n; i++) putchar(s[(i + ans) % n]); putchar('\n'); } return 0; }

这个算法实现了：

• 环状字符串的最小字典序表示
• 通过比较函数减少不必要的比较
• 时间复杂度O(n^2)

优化思路：存在O(n)的最小表示法算法，可以通过指针跳跃优化比较过程。

3.2 分子量计算

#include <stdio.h> #include <ctype.h> double getAtomicMass(char element) { switch (element) { case 'C': return 12.01; case 'H': return 1.008; case 'O': return 16.00; case 'N': return 14.01; default: return 0.0; } } int main() { char formula[90]; double total_mass; char current_element; int atom_count, position; scanf("%s", formula); total_mass = 0.0; position = 0; while (formula[position] != '\0') { current_element = formula[position]; atom_count = 0; position++; while (isdigit(formula[position])) { atom_count = atom_count * 10 + (formula[position] - '0'); position++; } total_mass += getAtomicMass(current_element) * (atom_count ? atom_count : 1); } printf("%.3f\n", total_mass); return 0; }

这个程序展示了：

• 化学分子式的解析技巧
• 数字字符到整数的转换方法
• 使用函数封装原子量查询

常见错误：

• 忘记处理原子数为1的情况（隐式省略）
• 数字转换时未考虑多位数情况
• 未正确处理字符串结束符

3.3 周期串识别

#include<cstdio> #include<cstring> using namespace std; char s[90]; int n; bool judge(int a) { for(int i=0;i<n;++i) if(s[i] != s[(a+i)%n]) return false; return true; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%s", s); n = strlen(s); int i; for(i=1;i<n;++i) { if(n%i == 0 && judge(i)) break; } printf("%d\n", i); if(T) puts(""); } return 0; }

这个算法实现了：

• 周期串的最小周期检测
• 通过模运算验证周期性
• 提前终止优化（找到最小周期立即退出）

算法优化：

• 先检查长度是否能整除候选周期
• 只检查可能的周期长度（n的约数）
• 复杂度从O(n^2)降到O(n√n)

4. 高级技巧与优化策略

4.1 预处理与记忆化

生成元问题的解法展示了预处理技术的威力。在实际比赛中，预处理常用于以下场景：

• 素数筛法
• 组合数计算
• 各种数论函数计算
• 字符串匹配预处理

预处理的基本原则：

1. 确定预处理的范围和内容
2. 设计高效的预处理算法
3. 确保预处理结果可以快速查询

4.2 输入输出优化

对于大规模数据（通常n>1e5），标准输入输出可能成为性能瓶颈。优化方法包括：

1. 使用更快的输入函数：

inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }

2. 减少输出次数：

• 使用缓冲区积累输出
• 避免频繁的printf调用

3. 关闭同步（C++）：

ios::sync_with_stdio(false); cin.tie(0);

4.3 空间优化技巧

当内存受限时（如多维数组），可以考虑：

1. 使用位压缩（bitset）
2. 动态分配内存
3. 复用数组空间
4. 使用更紧凑的数据结构

例如，在处理01矩阵时，可以用一个int表示32个bool，空间节省32倍。

4.4 调试与测试技巧

1. 小数据测试：先用小规模数据验证逻辑
2. 边界测试：测试空输入、极值等情况
3. 对拍：用暴力算法生成测试用例
4. 输出中间结果：在关键步骤打印变量值
5. 使用assert：验证假设条件

#define DEBUG #ifdef DEBUG #define debug(...) printf(__VA_ARGS__) #else #define debug(...) #endif

通过定义DEBUG宏，可以方便地开关调试输出。

5. 常见问题与解决方案

5.1 数组越界问题

症状：程序运行时出现段错误或输出乱码 解决方法：

1. 检查数组声明大小是否足够
2. 确认循环边界条件
3. 使用memset初始化数组
4. 在访问前检查下标有效性

5.2 字符串终止符问题

症状：字符串操作出现意外结果 解决方法：

1. 确保字符数组足够大（包括'\0'）
2. 使用strncpy代替strcpy
3. 手动添加'\0'终止符
4. 使用安全的字符串函数

5.3 浮点数精度问题

症状：浮点数比较出现误差 解决方法：

1. 使用相对误差比较：

const double eps = 1e-8; int dcmp(double x) { if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1; }

2. 尽量避免直接比较浮点数相等
3. 使用更高精度的数据类型（long double）
4. 考虑使用整数运算替代

5.4 多组数据输入问题

症状：程序处理完一组数据后异常 解决方法：

1. 确保每组数据完全读取
2. 重置全局变量和状态
3. 检查输入终止条件
4. 使用清晰的输入框架：

while(scanf("%d", &n) == 1 && n) { // 处理逻辑 }

5.5 时间复杂度估算

在比赛中快速估算算法复杂度：

1. 现代计算机通常1秒可执行1e8次操作

2. 根据数据规模选择合适的算法：

   • n≤20：O(2^n)或O(n!)
   • n≤100：O(n^3)
   • n≤1e4：O(n^2)
   • n≤1e6：O(nlogn)
   • n≤1e8：O(n)

3. 考虑常数因子：同样的复杂度，不同实现可能有10倍性能差异

6. 实战练习建议

1. 按专题练习：集中攻克某一类问题
2. 从简单题开始：建立信心和手感
3. 反复练习经典题目：如排序、查找、DP基础等
4. 参加虚拟比赛：模拟真实比赛环境
5. 学习他人代码：在OJ上查看优秀解答

推荐练习顺序：

1. 数组基本操作
2. 字符串处理
3. 排序与查找
4. 简单数学问题
5. 基础动态规划

对于每个题目，建议：

1. 先独立思考解法
2. 编写代码并测试
3. 对比优秀解答
4. 总结优化方法
5. 记录解题心得

7. 学习资源推荐

1. 书籍：

   • 《算法竞赛入门经典》（第2版）
   • 《算法竞赛进阶指南》
   • 《挑战程序设计竞赛》

2. 在线评测平台：

   • LeetCode
   • Codeforces
   • AtCoder
   • 洛谷

3. 学习网站：

   • CP-Algorithms
   • GeeksforGeeks
   • OI Wiki

4. 社区论坛：

   • Codeforces讨论区
   • Stack Overflow
   • 各类算法竞赛QQ群

8. 个人经验分享

在算法竞赛训练中，数组和字符串处理是最基础也是最重要的技能。根据我的参赛经验，以下几点特别值得注意：

1. 养成良好编码习惯：

   • 统一的代码风格
   • 有意义的变量命名
   • 适当的注释
   • 模块化设计

2. 掌握调试技巧：

   • 分段注释法定位问题
   • 打印关键变量
   • 使用assert验证假设
   • 编写测试用例

3. 重视基础算法：

   • 虽然高级算法很吸引人，但比赛中大部分题目还是基于基础算法的灵活运用
   • 基础算法的熟练度直接影响解题速度

4. 建立个人代码库：

   • 收集整理常用代码模板
   • 分类管理（如数学、图论、字符串等）
   • 定期复习和更新

5. 时间管理：

   • 比赛时合理分配时间
   • 先解决有把握的题目
   • 留出足够时间检查输入输出格式

对于初学者，我建议从《算法竞赛入门经典》的例题开始，每道题都亲自实现，并尝试不同的解法。通过大量练习，逐步培养算法思维和编码能力。记住，算法竞赛是一场马拉松，持之以恒的训练比短期的突击更有效。