首页
搜索资源
资源分类
资源描述
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号