ACM初赛常见试题及精准答案

ACM初赛常见试题及精准答案考试时间：______分钟总分：______分姓名：______一、问题1：排序与查找编写一个函数，该函数接收一个整数数组`arr`和一个整数`target`，首先使用冒泡排序对数组`arr`进行升序排序，然后使用二分查找算法在排序后的数组中查找`target`的位置（如果存在，返回其索引；如果不存在，返回-1）。二、问题2：递归与数学斐波那契数列定义为F(0)=0,F(1)=1,且对于n>=2,F(n)=F(n-1)+F(n-2)。编写一个递归函数，计算斐波那契数列的第`n`项的值。注意：对于较大的`n`，直接递归会导致栈溢出和低效。三、问题3：数据结构——栈编写一个函数，判断一个给定的只包含`'('`,`')'`,`'{'`,`'}'`,`'['`,`']'`的字符串`s`是否是有效的括号字符串。有效的括号字符串需要满足：左括号必须用相同类型的右括号闭合，左右括号必须正确嵌套，并且必须从字符串开头到结尾正确匹配。四、问题4：数学——模运算给定两个正整数`a`和`b`，以及一个正整数`mod`。计算`a`的`b`次方对`mod`取模的结果，即`(a^b)%mod`。要求在`b`很大的情况下也能高效计算。五、问题5：字符串处理编写一个函数，接收一个只包含小写字母的字符串`s`。函数需要找到字符串中第一个不重复的字符，并返回该字符。如果所有字符都重复，则返回一个空字符`''`。六、问题6：贪心算法假设你有一些面值为1元、3元和5元的硬币。给定一个整数`amount`，计算组成该金额所需的最少硬币数量。如果无法组成该金额，返回-1。七、问题7：数学——组合给定两个整数`n`和`k`（其中0<=k<=n<=100）。计算组合数C(n,k)，即从`n`个不同元素中取出`k`个元素的组合方式的总数。由于结果可能很大，请返回结果对1000000007取模的值。八、问题8：数据结构——数组操作一个长度为`n`的整数数组`arr`非递减排列。现在需要将数组中的元素向右旋转`k`次，其中`k`是非负整数。旋转后的数组元素顺序会发生改变，但数组中的每个元素都会出现在旋转后的新位置上。编写一个函数实现这个旋转操作。九、问题9：数论——最大公约数编写一个函数，接收两个正整数`x`和`y`，返回它们的最大公约数（GCD）。可以使用辗转相除法（欧几里得算法）实现。试卷答案一、问题1：排序与查找```c++#include<vector>usingnamespacestd;intbubbleSortAndBinarySearch(vector<int>&arr,inttarget){intn=arr.size();//冒泡排序for(inti=0;i<n-1;++i){for(intj=0;j<n-i-1;++j){if(arr[j]>arr[j+1]){swap(arr[j],arr[j+1]);}}}//二分查找intleft=0,right=n-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target){returnmid;}elseif(arr[mid]<target){left=mid+1;}else{right=mid-1;}}return-1;}```解析思路：1.冒泡排序实现：使用两层嵌套循环，外层循环控制排序趟数，内层循环进行相邻元素比较和交换，将最大元素逐趟“冒泡”到数组末尾，实现升序排列。时间复杂度为O(n^2)。2.二分查找实现：在已排序的数组中，初始化`left`和`right`指针。通过计算中间位置`mid`，比较`arr[mid]`与`target`。如果相等，返回`mid`；如果`arr[mid]`小于`target`，则将`left`移动到`mid+1`；否则将`right`移动到`mid-1`。重复此过程，直到`left`大于`right`时说明未找到，返回-1。时间复杂度为O(logn)。二、问题2：递归与数学```c++#include<vector>usingnamespacestd;//递归解法（效率较低，仅作演示）intfibonacciRecursive(intn){if(n<=0)return0;if(n==1)return1;returnfibonacciRecursive(n-1)+fibonacciRecursive(n-2);}//优化递归解法（使用记忆化搜索）intfibonacciMemo(intn,vector<int>&memo){if(n<=0)return0;if(n==1)return1;if(memo[n]!=-1)returnmemo[n];memo[n]=fibonacciMemo(n-1,memo)+fibonacciMemo(n-2,memo);returnmemo[n];}intfibonacci(intn){//使用动态规划数组存储中间结果vector<int>memo(n+1,-1);returnfibonacciMemo(n,memo);}```解析思路：1.直接递归：根据斐波那契数列定义直接编写递归函数。然而，这种解法有大量重复计算（如F(4)=F(3)+F(2)，F(3)=F(2)+F(1)），导致时间复杂度指数级增长（O(2^n)），对于较大的`n`效率极低且会栈溢出。2.优化递归（记忆化搜索）：在递归解法的基础上，使用一个数组`memo`来存储已经计算过的斐波那契数。在计算F(n)之前，先检查`memo[n]`是否已存储结果。如果已存储，则直接返回；否则，按正常递归计算，并将结果存入`memo`。这样，每个斐波那契数最多只计算一次，时间复杂度降低到O(n)。三、问题3：数据结构——栈```c++#include<stack>#include<string>usingnamespacestd;boolisValidParentheses(strings){stack<char>st;//遍历字符串中的每个字符for(charc:s){//如果是左括号，入栈if(c=='('||c=='{'||c=='['){st.push(c);}//如果是右括号elseif(c==')'||c=='}'||c==']'){//如果栈为空，或者栈顶元素与当前右括号不匹配，返回falseif(st.empty())returnfalse;chartop=st.top();st.pop();if((c==')'&&top!='(')||(c=='}'&&top!='{')||(c==']'&&top!='[')){returnfalse;}}}//如果栈不为空，说明有未匹配的左括号，返回falsereturnst.empty();}```解析思路：1.使用栈：括号匹配问题是典型的栈应用场景。遇到左括号时，将其入栈；遇到右括号时，检查栈是否为空。如果不为空，则弹出栈顶元素，判断其是否与当前右括号类型匹配（'('与')'，'{'与'}'，'['与']'）。如果匹配，继续；如果不匹配或栈为空时遇到右括号，则返回false。2.最终判断：遍历完整个字符串后，如果栈为空，说明所有左括号都找到了匹配的右括号，且顺序正确，返回true；如果栈不为空，说明有左括号没有匹配，返回false。四、问题4：数学——模运算```c++#include<vector>usingnamespacestd;typedeflonglongll;//使用longlong防止溢出llmodPow(lla,llb,llmod){llres=1;a=a%mod;//处理a>=mod的情况while(b>0){//如果b是奇数，乘上当前的aif(b%2==1){res=(res*a)%mod;}//a自乘，b右移一位a=(a*a)%mod;b/=2;}returnres;}```解析思路：1.快速幂算法（迭代版）：为了高效计算`a^b`，尤其是在`b`很大的情况下，使用快速幂算法。其核心思想是利用指数的二进制表示进行迭代计算。2.迭代过程：*初始化结果`res`为1，基数`a`先对`mod`取模。*当指数`b`大于0时，循环执行：*如果`b`是奇数，说明当前最低位是1，需要将`res`乘上当前的`a`，并对`mod`取模。*基数`a`自身平方，并对`mod`取模（准备计算更高位的贡献）。*指数`b`右移一位（整除2）。3.返回结果：循环结束后，`res`即为`(a^b)%mod`的结果。五、问题5：字符串处理```c++#include<string>usingnamespacestd;charfirstUniqChar(strings){//假设输入只包含小写字母a-zintcount[26]={0};//存储每个字母出现的次数intn=s.length();//遍历字符串，统计每个字母的出现次数for(inti=0;i<n;++i){count[s[i]-'a']++;}//再次遍历字符串，查找第一个出现次数为1的字母for(inti=0;i<n;++i){if(count[s[i]-'a']==1){returns[i];}}//如果所有字母都重复，返回空字符return'';}```解析思路：1.统计频率：使用一个长度为26的整数数组`count`来统计字符串中每个小写字母（'a'到'z'）出现的次数。遍历字符串一次，对每个字符`s[i]`，将其对应的计数器`count[s[i]-'a']`加1。2.查找第一个唯一字符：再次遍历字符串，对于每个字符`s[i]`，检查其对应的计数器`count[s[i]-'a']`的值。第一个该值为1的字符`s[i]`即为第一个不重复的字符，直接返回它。3.处理无唯一字符情况：如果遍历完整个字符串后没有找到计数为1的字符，则返回空字符`''`。六、问题6：贪心算法```c++#include<vector>#include<algorithm>usingnamespacestd;intminCoins(vector<int>&coins,intamount){if(amount==0)return0;//从大到小排序硬币面值sort(coins.begin(),coins.end(),greater<int>());intcount=0;for(intcoin:coins){if(coin>amount)continue;//如果当前硬币面值大于剩余金额，跳过//使用尽可能多的当前面值硬币count+=amount/coin;amount%=coin;if(amount==0)break;//如果金额已减至0，返回结果}//如果最终金额不为0，说明无法组成该金额returnamount==0?count:-1;}```解析思路：1.贪心选择：贪心算法在每一步选择当前看起来最优（通常是最大面值）的选项，期望通过局部最优达到全局最优。在这个问题中，优先使用面值最大的硬币。2.排序：将硬币面值数组`coins`按从大到小的顺序排序。3.贪心执行：初始化计数器`count`为0。遍历排序后的硬币数组：*对于当前硬币`coin`，如果`coin`大于剩余`amount`，则无法使用，跳过。*否则，计算当前硬币最多可以使用多少枚：`amount/coin`，将这个数量加到`count`上。*更新剩余金额：`amount%=coin`。*如果更新后的`amount`为0，说明已经成功凑出目标金额，返回`count`。4.无法凑出情况：遍历结束后，如果`amount`不为0，说明无法用给定的硬币面值组合出目标金额，返回-1。七、问题7：数学——组合```c++#include<vector>usingnamespacestd;typedeflonglongll;constintMOD=1000000007;llcombination(intn,intk){if(k>n)return0;if(k==0||k==n)return1;//使用动态规划或直接计算C(n,k)=n!/(k!*(n-k)!)//注意大数计算和取模llnumerator=1;lldenominator=1;for(inti=1;i<=k;++i){numerator=(numerator*(n-i+1))%MOD;//计算n*(n-1)*...*(n-k+1)denominator=(denominator*i)%MOD;//计算k!}//使用快速幂计算denominator的(MOD-2)次方，即denominator^(-1)modMODllinvDenominator=modPow(denominator,MOD-2,MOD);//计算结果并返回return(numerator*invDenominator)%MOD;}//快速幂函数（同问题4）llmodPow(lla,llb,llmod){llres=1;a=a%mod;while(b>0){if(b%2==1){res=(res*a)%mod;}a=(a*a)%mod;b/=2;}returnres;}```解析思路：1.组合数定义：组合数C(n,k)表示从n个不同元素中取出k个元素的组合方式的总数，计算公式为C(n,k)=n!/(k!*(n-k)!).2.直接计算（可能溢出）：直接使用公式计算会涉及阶乘，对于较大的n和k，阶乘数值会非常大，导致整数溢出。3.优化计算与取模：*按比例计算：为了避免直接计算大阶乘，可以按比例计算C(n,k)=n*(n-1)*...*(n-k+1)/(k*(k-1)*...*1)。这样分子和分母可以同时消去一些因子，减少乘法操作的次数和结果的大小。*模运算：由于题目要求对1000000007取模，所有计算（乘法、除法）都在模MOD下进行。*模逆元：在模运算下，除法可以通过乘以模的逆元来实现。计算分母部分`k!`的模逆元`invDenominator`，然后计算`(numerator*invDenominator)%MOD`即为所求。*快速幂求逆元：分母的模逆元`invDenominator`可以通过快速幂算法计算`denominator^(MOD-2)modMOD`得到，根据费马小定理，当MOD为质数时，`a^(MOD-1)≡1(modMOD)`，因此`a^(MOD-2)≡a^(-1)(modMOD)`。八、问题8：数据结构——数组操作```c++#include<vector>usingnamespacestd;voidrotate(vector<int>&nums,intk){intn=nums.size();if(n==0||k<=0||k%n==0)return;//无需旋转或旋转周期等于数组长度k=k%n;//计算实际需要旋转的步数//方法一：反转法//1.反转整个数组reverse(nums.begin(),nums.end());//2.反转前k个元素reverse(nums.begin(),nums.begin()+k);//3.反转剩下的元素reverse(nums.begin()+k,nums.end());//方法二：直接模拟（将nums[i]移动到(i+k)%n的位置）/*vector<int>rotated(n);for(inti=0;i<n;++i){rotated[(i+k)%n]=nums[i];}nums=rotated;//如果题目允许修改原数组，可以直接替换*/}```解析思路：1.旋转定义：将数组`nums`的元素向右旋转`k`次，意味着每个元素都移动`k`个位置，超出数组末尾的元素从数组开头继续。2.旋转步数优化：如果`k`大于数组长度`n`，则实际旋转效果等同于`k%n`次。如果`k`是`n`的倍数，则旋转后数组与原数组相同，无需操作。3.反转法（推荐）：这是更高效的O(n)解法。*步骤1：反转整个数组。例如`[1,2,3,4,5,6]`->`[6,5,4,3,2,1]`。*步骤2：反转数组前`k`个元素。例如`[6,5,4,3,2,1]`->`[4,5,6,3,2,1]`。*步骤3：反转数组剩下的元素。例如`[4,5,6,