1. 杭电OJ算法题解系列2036~2045作为一名计算机专业的学生刷OJ题是提升编程能力的必经之路。最近我在杭电OJ上完成了2036~2045这组题目发现其中涉及不少经典的算法思想和编程技巧。下面我将分享这些题目的解题思路和实现细节希望能帮助到正在刷题的你。1.1 题目概览这组题目涵盖了多个算法知识点贪心算法2037几何基础2039数论2040动态规划/递推2041,2044,2045字符串处理2043简单数学2042每个题目都有其独特的解题思路和实现技巧下面我将挑选几个典型题目进行详细解析。2. 贪心算法经典应用今年暑假不AC20372.1 问题分析题目大意给定多个电视节目的开始和结束时间如何安排观看才能看到最多的完整节目这是一个典型的区间调度问题可以使用贪心算法解决。贪心算法的核心思想是每一步都做出在当前看来最优的选择希望这样能得到全局最优解。2.2 解题思路排序阶段将所有节目按照结束时间从早到晚排序选择阶段选择第一个结束的节目之后每次都选择第一个不与已选节目冲突的节目这种策略之所以有效是因为早结束的节目给后续留下了更多选择空间。2.3 代码实现#include stdio.h void swap(int *a,int *b){ int t*a; *a*b; *bt; } int main(){ int n,i,j,count; int a[100][2]; while(scanf(%d,n)!EOF){ if(n0) break; for(i0;in;i){ scanf(%d %d,a[i][0],a[i][1]); } // 冒泡排序按结束时间升序 for(in-1;i0;i--){ int flag0; for(j0;ji;j){ if(a[j][1]a[j1][1]){ swap(a[j][1],a[j1][1]); swap(a[j][0],a[j1][0]); flag1; } } if(flag0) break; } // 贪心选择 j0; count1; for(i1;in;i){ if(a[j][1]a[i][0]){ ji; count; } } printf(%d\n,count); } return 0; }2.4 注意事项排序算法选择题目数据量不大n≤100使用冒泡排序足够。如果数据量大建议改用快速排序。边界情况当n0时需要直接退出循环。时间复杂度排序O(n²)选择O(n)总体O(n²)。3. 几何基础三角形判断20393.1 问题分析题目要求判断三条边是否能构成三角形。根据三角形不等式任意两边之和大于第三边任意两边之差小于第三边3.2 优化思路实际上只需要验证最大边是否小于其他两边之和即可。因为如果最大边满足条件其他两边自然满足。3.3 代码实现#include stdio.h #includestdlib.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(n0) 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[401]; dp[1]1; dp[2]1; for(int i3; im1; i) { dp[i]dp[i-1]dp[i-2]; } printf(%d,dp[m]); if(n0) 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 i2;i50;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)3f(2)f(3)6f(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 i4; i50; 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 sum10,sum20; // 计算a的真约数和 for(int i1;ia;i){ if(a%i0) sum1i; } // 计算b的真约数和 for(int j1;jb;j){ if(b%j0) sum2j; } if(sum1bsum2a) printf(YES); else printf(NO); if(m0) 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 lenstrlen(s); if(len8len16) { for(int i0; ilen; 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 suma[0]a[1]a[2]a[3]; printf(sum3?YES:NO); } else{ printf(NO); } if(m0) printf(\n); } return 0; }注意事项使用ctype.h中的字符判断函数更规范。特殊符号判断可以用strchr函数。6. 刷题经验分享在完成这组题目后我总结了一些刷题经验理解题意是关键比如2039题一开始没注意数据类型导致WA后来发现要用double。寻找问题本质很多题目看似不同实则相同。如2041、2044都是斐波那契数列问题。预处理优化效率对于多组输入预处理结果数组可以大大提高效率。边界条件测试特别注意n0、n1等边界情况。使用标准库函数如qsort、isupper等既高效又减少错误。数据类型选择根据题目要求选择合适的数据类型如2044要用long long。递推关系分析对于动态规划问题仔细分析递推关系是关键。刷题是一个循序渐进的过程建议从简单题开始逐步提升难度。每做完一题要总结解题思路和可以改进的地方。杭电OJ是一个很好的练习平台题目类型丰富适合各个阶段的编程学习者。
1. 杭电OJ算法题解系列2036~2045作为一名计算机专业的学生刷OJ题是提升编程能力的必经之路。最近我在杭电OJ上完成了2036~2045这组题目发现其中涉及不少经典的算法思想和编程技巧。下面我将分享这些题目的解题思路和实现细节希望能帮助到正在刷题的你。1.1 题目概览这组题目涵盖了多个算法知识点贪心算法2037几何基础2039数论2040动态规划/递推2041,2044,2045字符串处理2043简单数学2042每个题目都有其独特的解题思路和实现技巧下面我将挑选几个典型题目进行详细解析。2. 贪心算法经典应用今年暑假不AC20372.1 问题分析题目大意给定多个电视节目的开始和结束时间如何安排观看才能看到最多的完整节目这是一个典型的区间调度问题可以使用贪心算法解决。贪心算法的核心思想是每一步都做出在当前看来最优的选择希望这样能得到全局最优解。2.2 解题思路排序阶段将所有节目按照结束时间从早到晚排序选择阶段选择第一个结束的节目之后每次都选择第一个不与已选节目冲突的节目这种策略之所以有效是因为早结束的节目给后续留下了更多选择空间。2.3 代码实现#include stdio.h void swap(int *a,int *b){ int t*a; *a*b; *bt; } int main(){ int n,i,j,count; int a[100][2]; while(scanf(%d,n)!EOF){ if(n0) break; for(i0;in;i){ scanf(%d %d,a[i][0],a[i][1]); } // 冒泡排序按结束时间升序 for(in-1;i0;i--){ int flag0; for(j0;ji;j){ if(a[j][1]a[j1][1]){ swap(a[j][1],a[j1][1]); swap(a[j][0],a[j1][0]); flag1; } } if(flag0) break; } // 贪心选择 j0; count1; for(i1;in;i){ if(a[j][1]a[i][0]){ ji; count; } } printf(%d\n,count); } return 0; }2.4 注意事项排序算法选择题目数据量不大n≤100使用冒泡排序足够。如果数据量大建议改用快速排序。边界情况当n0时需要直接退出循环。时间复杂度排序O(n²)选择O(n)总体O(n²)。3. 几何基础三角形判断20393.1 问题分析题目要求判断三条边是否能构成三角形。根据三角形不等式任意两边之和大于第三边任意两边之差小于第三边3.2 优化思路实际上只需要验证最大边是否小于其他两边之和即可。因为如果最大边满足条件其他两边自然满足。3.3 代码实现#include stdio.h #includestdlib.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(n0) 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[401]; dp[1]1; dp[2]1; for(int i3; im1; i) { dp[i]dp[i-1]dp[i-2]; } printf(%d,dp[m]); if(n0) 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 i2;i50;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)3f(2)f(3)6f(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 i4; i50; 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 sum10,sum20; // 计算a的真约数和 for(int i1;ia;i){ if(a%i0) sum1i; } // 计算b的真约数和 for(int j1;jb;j){ if(b%j0) sum2j; } if(sum1bsum2a) printf(YES); else printf(NO); if(m0) 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 lenstrlen(s); if(len8len16) { for(int i0; ilen; 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 suma[0]a[1]a[2]a[3]; printf(sum3?YES:NO); } else{ printf(NO); } if(m0) printf(\n); } return 0; }注意事项使用ctype.h中的字符判断函数更规范。特殊符号判断可以用strchr函数。6. 刷题经验分享在完成这组题目后我总结了一些刷题经验理解题意是关键比如2039题一开始没注意数据类型导致WA后来发现要用double。寻找问题本质很多题目看似不同实则相同。如2041、2044都是斐波那契数列问题。预处理优化效率对于多组输入预处理结果数组可以大大提高效率。边界条件测试特别注意n0、n1等边界情况。使用标准库函数如qsort、isupper等既高效又减少错误。数据类型选择根据题目要求选择合适的数据类型如2044要用long long。递推关系分析对于动态规划问题仔细分析递推关系是关键。刷题是一个循序渐进的过程建议从简单题开始逐步提升难度。每做完一题要总结解题思路和可以改进的地方。杭电OJ是一个很好的练习平台题目类型丰富适合各个阶段的编程学习者。
