1. 杭电OJ算法题解系列（2036~2045）
作为一名计算机专业的学生，刷OJ题是提升编程能力的必经之路。最近我在杭电OJ上完成了2036~2045这组题目，发现其中涉及不少经典的算法思想和编程技巧。下面我将分享这些题目的解题思路和实现细节，希望能帮助到正在刷题的你。
1.1 题目概览
这组题目涵盖了多个算法知识点：
- 贪心算法（2037）
- 几何基础（2039）
- 数论（2040）
- 动态规划/递推（2041,2044,2045）
- 字符串处理（2043）
- 简单数学（2042）
每个题目都有其独特的解题思路和实现技巧，下面我将挑选几个典型题目进行详细解析。
2. 贪心算法经典应用：今年暑假不AC（2037）
2.1 问题分析
题目大意：给定多个电视节目的开始和结束时间，如何安排观看才能看到最多的完整节目？
这是一个典型的区间调度问题，可以使用贪心算法解决。贪心算法的核心思想是：每一步都做出在当前看来最优的选择，希望这样能得到全局最优解。
2.2 解题思路
- 排序阶段：将所有节目按照结束时间从早到晚排序
- 选择阶段：
- 选择第一个结束的节目
- 之后每次都选择第一个不与已选节目冲突的节目
这种策略之所以有效，是因为早结束的节目给后续留下了更多选择空间。
2.3 代码实现
#include <stdio.h> void swap(int *a,int *b){ int t=*a; *a=*b; *b=t; } int main(){ int n,i,j,count; int a[100][2]; while(scanf("%d",&n)!=EOF){ if(n==0) break; for(i=0;i<n;i++){ scanf("%d %d",&a[i][0],&a[i][1]); } // 冒泡排序：按结束时间升序 for(i=n-1;i>0;i--){ int flag=0; for(j=0;j<i;j++){ if(a[j][1]>a[j+1][1]){ swap(&a[j][1],&a[j+1][1]); swap(&a[j][0],&a[j+1][0]); flag=1; } } if(flag==0) break; } // 贪心选择 j=0; count=1; for(i=1;i<n;i++){ if(a[j][1]<=a[i][0]){ j=i; count++; } } printf("%d\n",count); } return 0; }2.4 注意事项
- 排序算法选择：题目数据量不大（n≤100），使用冒泡排序足够。如果数据量大，建议改用快速排序。
- 边界情况：当n=0时需要直接退出循环。
- 时间复杂度：排序O(n²)+选择O(n)，总体O(n²)。
3. 几何基础：三角形判断（2039）
3.1 问题分析
题目要求判断三条边是否能构成三角形。根据三角形不等式：
- 任意两边之和大于第三边
- 任意两边之差小于第三边
3.2 优化思路
实际上，只需要验证最大边是否小于其他两边之和即可。因为如果最大边满足条件，其他两边自然满足。
3.3 代码实现
#include <stdio.h> #include<stdlib.h> int cmp(const void *a, const void *b) { double da = *(const double *)a; double db = *(const double *)b; if (da < db) return -1; if (da > db) return 1; return 0; } int main(){ int n; double a[3]; scanf("%d",&n); while(n--){ scanf("%lf %lf %lf",&a[0],&a[1],&a[2]); // 对三条边排序 qsort(a,3,sizeof(double),cmp); // 判断最大边是否小于其他两边之和 if(a[2]<(a[0]+a[1])){ printf("YES"); } else{ printf("NO"); } if(n>0) printf("\n"); } return 0; }3.4 注意事项
- 数据类型：题目只说边是正数，没说一定是整数，所以要用double类型。
- 排序：使用标准库的qsort函数更高效。
- 输出格式：注意最后一行不要有多余换行。
4. 动态规划专题
4.1 超级楼梯（2041）
问题分析
楼梯有M级，每次可以走1级或2级，问有多少种走法。这实际上是斐波那契数列问题。
代码实现
#include <stdio.h> int main() { int n,m; scanf("%d",&n); while(n--) { scanf("%d",&m); int dp[40+1]; dp[1]=1; dp[2]=1; for(int i=3; i<m+1; i++) { dp[i]=dp[i-1]+dp[i-2]; } printf("%d",dp[m]); if(n>0) printf("\n"); } return 0; }注意事项
- 使用迭代而非递归，避免重复计算。
- 注意dp数组大小要足够（M≤40）。
4.2 一只小蜜蜂（2044）
问题分析
蜜蜂从a爬到b，每次只能向右移动1或2格，问有多少种路径。这也是斐波那契数列问题。
代码实现
#include <stdio.h> int main() { int n,a,b; scanf("%d",&n); long long d[50]; d[0]=1,d[1]=1; for(int i=2;i<50;i++){ d[i]=d[i-1]+d[i-2]; } while(n--) { scanf("%d %d",&a,&b); printf("%lld\n",d[b-a]); } return 0; }注意事项
- 结果可能很大，要用long long类型。
- 预处理斐波那契数列更高效。
4.3 RPG问题（2045）
问题分析
用三种颜色给一条直线上的n个方格染色，要求相邻和首尾不同色。这是一个递推问题。
递推关系：
- f(1)=3
- f(2)=f(3)=6
- f(n)=f(n-1)+2*f(n-2) (n≥4)
代码实现
#include <stdio.h> int main() { int n; long long f[51]; f[1]=3,f[2]=f[3]=6; for(int i=4; i<=50; i++) { f[i]=f[i-1]+f[i-2]*2; } while(scanf("%d",&n)!=EOF) { printf("%lld\n",f[n]); } return 0; }注意事项
- 注意递推公式的推导。
- 预处理结果数组更高效。
5. 其他题目精解
5.1 亲和数（2040）
问题分析
判断两个数是否互为对方的真约数和。需要计算一个数的所有真约数的和。
代码实现
#include <stdio.h> int main(){ int m,a,b; scanf("%d",&m); while(m--){ scanf("%d %d",&a,&b); int sum1=0,sum2=0; // 计算a的真约数和 for(int i=1;i<a;i++){ if(a%i==0) sum1+=i; } // 计算b的真约数和 for(int j=1;j<b;j++){ if(b%j==0) sum2+=j; } if(sum1==b&&sum2==a) printf("YES"); else printf("NO"); if(m>0) printf("\n"); } return 0; }优化建议
- 约数计算可以优化到sqrt(n)复杂度。
- 可以预处理一些数的约数和。
5.2 密码验证（2043）
问题分析
验证密码是否满足：
- 长度8-16
- 包含至少三类字符（大写、小写、数字、特殊符号）
代码实现
#include <stdio.h> #include <ctype.h> #include <string.h> int main() { int m; scanf("%d",&m); while(m--) { char s[50]; int a[4]={0}; // 分别记录四类字符是否存在 scanf("%s",s); int len=strlen(s); if(len>=8&&len<=16) { for(int i=0; i<len; i++) { if(isupper(s[i])) a[0]=1; else if(islower(s[i])) a[1]=1; else if(isdigit(s[i])) a[2]=1; else if(strchr("~!@#$%^",s[i])) a[3]=1; } int sum=a[0]+a[1]+a[2]+a[3]; printf(sum>=3?"YES":"NO"); } else{ printf("NO"); } if(m>0) printf("\n"); } return 0; }注意事项
- 使用ctype.h中的字符判断函数更规范。
- 特殊符号判断可以用strchr函数。
6. 刷题经验分享
在完成这组题目后，我总结了一些刷题经验：
理解题意是关键：比如2039题，一开始没注意数据类型导致WA，后来发现要用double。
寻找问题本质：很多题目看似不同，实则相同。如2041、2044都是斐波那契数列问题。
预处理优化效率：对于多组输入，预处理结果数组可以大大提高效率。
边界条件测试：特别注意n=0、n=1等边界情况。
使用标准库函数：如qsort、isupper等，既高效又减少错误。
数据类型选择：根据题目要求选择合适的数据类型，如2044要用long long。
递推关系分析：对于动态规划问题，仔细分析递推关系是关键。
刷题是一个循序渐进的过程，建议从简单题开始，逐步提升难度。每做完一题要总结解题思路和可以改进的地方。杭电OJ是一个很好的练习平台，题目类型丰富，适合各个阶段的编程学习者。
