ACM竞赛解题攻略：10年12月题库解析

"大学生acm竞赛——10年12月竞赛题库，包含五道编程题目，涉及灯泡开关问题、蛇形矩阵填充、最长回文子串查找、素数判断以及质因数分解等算法" 在这份大学生acm竞赛题库中，我们可以看到五道具有代表性的编程题目，每道题目都包含了程序分析和源代码，旨在测试参赛者的算法设计和编程能力。 第一题是关于灯泡开关的问题。给定n盏灯和k个人，每个人按照编号依次操作灯的开关。题目要求找出最后哪些灯是开着的。解决方案是通过模拟每个人的操作，利用一个数组a[]记录灯的状态，初始所有灯都是开的，之后按编号进行开关操作。例如，对于输入73和k=1，最终开着的灯编号为1567。 第二题涉及到在n*n的方阵中填充1到n*n，形成蛇形排列。可以通过二维数组实现，从左上角开始，逐行或逐列填充，根据当前行数判断是行填充还是列填充。对于n=4的情况，填充的方阵如下所示：10.11121，9.16132，8.15143，7654。 第三题要求找出给定字符串中最长的回文子串，同时处理标点符号、空格和大小写。可以使用中心扩散法或Manacher's Algorithm来解决，首先去除标点和空格，再进行回文判断。样例输入"Confuciusssay:Madam,I’mAdam."，输出为"Madam,I’mAdam"。 第四题需要计算101到200之间素数的数量，并输出所有素数。可以采用遍历和素数筛选的方法，对于每个数i，从2到sqrt(i)检查是否有因子，如果没有，则i是素数。例如，101到200之间的素数有25个，分别是101, 103, 107, ..., 197, 199。 最后一题要求将一个正整数n分解成质因数的乘积。可以使用循环和判断质因数的逻辑，找到最小的质数k，然后不断用k去除n，直到n变成1。例如，输入90，输出结果应为"90=2*3*3*5"。 这五道题目涵盖了基础的算法设计，包括模拟、矩阵操作、字符串处理、数论以及因数分解，对于提升大学生的算法思维和编程实践能力具有很好的训练价值。