资源描述
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。 参考源码: 1. #include 2. using namespace std; 3. #define ll long long int 4. const ll c = 1e9; 5. ll f(ll a, ll b) { 6.     ll ret = 1; 7.     if (a==1) return 1; 8.     for (ll i = 1; i <= b; i++) { 9.         ret *= a; 10.         if (ret > c) { 11.             ret = -1; 12.             break; 13.         } 14.     } 15.     return ret; 16. } 17. int main() { 18.     ll a, b; 19.     cin >> a >> b; 20.     cout << f(a, b) << endl; 21.     return 0; 22. } 算法思路: 这道题如何从算法的角度来看,计算ab直接累乘即可:b个a相乘,或者直接用快速幂算法来计算。但是这题要考查的核心不是时间复杂度,而是参数范围和返回值的范围问题(题目中已经提示了)。 先分析一下题目会不会出现TLE(Time Limit Exceeded)问题。ab的值不超过109,int型变量的最大值为231-1(231-1>109),也就是说当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可以不设置),具体案例可看下面测试代码: 1. #include  2. using namespace std; 3. int main(){ 4.     long long int a=1e+9; 5.     long long int b=1e+9; 6.     //不溢出 7.     cout< 2. #include  3. using namespace std; 4. #define ll long long int 5. int main() { 6.    ll k,n,e,d,m; 7.    ll p,q; 8.    ll temp1,temp2,root; 9.    cin>>k; 10.    for(ll i=1;i<=k;i++){ 11.        cin>>n>>e>>d; 12.        m=n-e*d+2; 13.      temp1=m*m-4*n; 14.      root=sqrt(temp1); 15.      if (root*root!=temp1){ 16.          cout<<"NO"< 2. using namespace std; 3. #define ll long long int 4. int main() { 5.     ll k, n, e, d, m; 6.     ll p, q; 7.     cin >> k; 8.     for (ll i = 1; i <= k; i++) { 9.         cin >> n >> e >> d; 10.         m = n - e * d + 2; 11.         ll begin = 1, end = m / 2; 12.         ll area; 13.         while (begin <= end) { 14.             p = (begin + end) / 2; 15.             q = m - p; 16.             area = p * q; 17.             if (area < n) { 18.                 begin = p + 1; 19.             } else if (area > n) { 20.                 end = p - 1; 21.             } else { 22.                 cout << p << " " << q << endl; 23.                 break; 24.             } 25.         } 26.         if (begin > end) { 27.             cout << "NO" << endl; 28.         } 29.     } 30.     return 0; 算法思路2: 二分法。由于p<=q,p的二分区间是1,m2,判断条件是pq是否大于、等于或者小于n。能采用二分法的原因是:根据p+q=m,pq=n,可以推导出-p-m22+m24=n,n与p是之间的关系是单调递减。 上述算法一次计算的时间复杂度是olog2m2=olog2m-1。可以简单估最大计算次数,由于m的最大值为109,32位2进制最多能表示232个数,232大于109,因此最大计算次数是不会超过31次。 下面分析暴力算法存在的问题。由于pq=n,因此可以将暴力算法的枚举次数优化为n,用p+q=m对每次枚举进行判断。n的最大值为1018,所以一次计算的最大次数为109,这就会出现TLE问题。暴力算法的源码如下: 1. #include 2. using namespace std; 3. #define ll lon
点击显示更多内容>>
收藏
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号