2022年CSP-J第二轮C++真题源码解析1.docxVIP

2022年CSP-J第二轮真题源码解析 个人解析，非评分标准答案。 1. T1?[ CSP-J?2022]乘方 【题目描述】 小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 a和 b，求ab的值是多少。 ab即b个a相乘的值，例如23即为3个2相乘，结果为2×2×2=8。 “简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。小文很快意识到，她的程序里的变量都是 int类型的。在大多数机器上，int类型能表示的最大数为231-1，因此只要计算结果超过这个数，她的程序就会出现错误。 由于小文刚刚学会编程，她担心使用int计算会出现问题。因此她希望你在ab的值超过 109时，输出一个-1进行警示，否则就输出正确的ab的值。然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。 【输入格式】 输入共一行，两个正整数a，b。 【输出格式】 输出共一行，如果ab的值不超过109，则输出ab的值，否则输出-1。 【输入输出样例】 输入#1 10 9 输出#1 1000000000 输入#2 23333 66666 输出#2 -1 【说明/提示】 对于10%的数据，保证b=1。 对于30%的数据，保证b≤2。 对于60%的数据，保证b≤30，ab≤1018。 对于100%的数据，保证1≤a,b≤109。 参考源码： #includebits/stdc++.h using?namespace?std; #define?ll?long?long?int const?ll?c?=?1e9; ll?f(ll?a,?ll?b)?{ ????ll?ret?=?1; ????if?(a==1)?return?1; ????for?(ll?i?=?1;?i?=?b;?i++)?{ ????????ret?*=?a; ????????if?(ret??c)?{ ????????????ret?=?-1; ????????????break; ????????} ????} ????return?ret; } int?main()?{ ????ll?a,?b; ????cin??a??b; ????cout??f(a,?b)??endl; ????return?0; } 算法思路： 这道题如何从算法的角度来看，计算ab直接累乘即可：b个a相乘，或者直接用快速幂算法来计算。但是这题要考查的核心不是时间复杂度，而是参数范围和返回值的范围问题（题目中已经提示了）。 先分析一下题目会不会出现TLE(Time Limit Exceeded)问题。ab的值不超过109，int型变量的最大值为231-1（231-1109），也就是说当a≥2，最多循环32次就超过了int型的范围，当然也超过了109范围。所以无需考虑时间复杂度，自然也就不需要采用快速幂算法。 下面讨论越界问题。可以在每次累乘的时间判断结果是否大于109，大于则返回-1，结束循环。这里面有一个问题需要考虑：假设n次累乘的结果小于109，n+1次累乘的结果大概在什么范围内？由于a≤109，n+1次累乘的结果（中间结果）有可能int越界，但是不可能long long int越界(109×109)，所以需要将相关的变量设置为long long int，而不能用int型，防止出现整数上溢出问题。在上面程序中，将(a,b,ret)三个变量设置为long long int，至于为什么要将a和b也设置为long long int（b可以不设置），具体案例可看下面测试代码： #include?iostream using?namespace?std; int?main(){ ????long?long?int?a=1e+9; ????long?long?int?b=1e+9; ????//不溢出 ????couta*bendl; ????int?a1=1e+9; ????int?b1=1e+9; ????//溢出 ????couta1*b1endl; ????long?long?int?a2=1e+9; ????int?b2=1e+9; ????int?ret1=a2*b2; ????long?long?int?ret2=a2*b2; ????//不溢出 ????couta2*b2endl; ????//溢出 ????coutret1endl; ????//不溢出 ????coutret2endl; ????return?0; } 运行截图如下： c=a×b在计算时，先计算后赋值（没有c就不赋值）。左边计算结果的范围取决于a和b的最大范围，例如上例中a为long long int，b为int，则计算结果的最大范围就是long long int；如果计算结果没有溢出，但是