2022年CSP-J第二轮C++真题源码解析1
2022年CSP-J第二轮真题源码解析个人解析，非评分标准答案。1. T1CSP-J2022乘方【题目描述】小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数a和 b，求ab的值是多少。ab即b个a相乘的值，例如23即为3个2相乘，结果为222=8。“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。小文很快意识到，她的程序里的变量都是 int类型的。在大多数机器上，int类型能表示的最大数为231-1，因此只要计算结果超过这个数，她的程序就会出现错误。由于小文刚刚学会编程，她担心使用int计算会出现问题。因此她希望你在ab的值超过 109时，输出一个-1进行警示，否则就输出正确的ab的值。然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。【输入格式】输入共一行，两个正整数a，b。【输出格式】输出共一行，如果ab的值不超过109，则输出ab的值，否则输出-1。【输入输出样例】输入#110 9输出#11000000000输入#223333 66666输出#2-1【说明/提示】对于10%的数据，保证b=1。对于30%的数据，保证b2。对于60%的数据，保证b30，ab1018。对于100%的数据，保证1a,b109。参考源码：1. #include2. usingnamespacestd;3. #definelllonglongint4. constllc=1e9;5. llf(lla,llb)6. llret=1;7. if(a=1)return1;8. for(lli=1;ic)11. ret=-1;12. break;13. 14. 15. returnret;16. 17. intmain()18. lla,b;19. cinab;20. coutf(a,b)109），也就是说当a2，最多循环32次就超过了int型的范围，当然也超过了109范围。所以无需考虑时间复杂度，自然也就不需要采用快速幂算法。下面讨论越界问题。可以在每次累乘的时间判断结果是否大于109，大于则返回-1，结束循环。这里面有一个问题需要考虑：假设n次累乘的结果小于109，n+1次累乘的结果大概在什么范围内？由于a109，n+1次累乘的结果（中间结果）有可能int越界，但是不可能long long int越界(109109)，所以需要将相关的变量设置为long long int，而不能用int型，防止出现整数上溢出问题。在上面程序中，将(a,b,ret)三个变量设置为long long int，至于为什么要将a和b也设置为long long int（b可以不设置），具体案例可看下面测试代码：1. #include2. usingnamespacestd;3. intmain()4. longlonginta=1e+9;5. longlongintb=1e+9;6. /不溢出7. couta*bendl;8. inta1=1e+9;9. intb1=1e+9;10. /溢出11. couta1*b1endl;12. longlonginta2=1e+9;13. intb2=1e+9;14. intret1=a2*b2;15. longlongintret2=a2*b2;16. /不溢出17. couta2*b2endl;18. /溢出19. coutret1endl;20. /不溢出21. coutret2endl;22. return0;23. 运行截图如下： c=ab在计算时，先计算后赋值（没有c就不赋值）。左边计算结果的范围取决于a和b的最大范围，例如上例中a为long long int，b为int，则计算结果的最大范围就是long long int；如果计算结果没有溢出，但是计算结果不在c的范围之内，也可能溢出，例如上例中ret1为int。一个误区就是计算结果不存储就不会溢出，上面例子已经给出（cout直接输出或者直接判断大小等）。在本题中a=1需要单独枚举来计算，直接返回1；本题中的b的范围实际上不需要考虑。运行截图：测试用例1测试用例2测试用例3测试用例42. T2CSP-J 2022 解密【题目描述】给定一个正整数k，有k次询问，每次给定三个正整数ni、ei、di，求两个正整数pi、qi，使ni=piqi、eidi=(pi - 1)(qi - 1) + 1。【输入格式】第一行一个正整数k，表示有k次询问。接下来k行，第i行三个正整数ni、ei、di。【输出格式】输出k行，每行两个正整数pi，qi表示答案。为使输出统一，你应当保证pi=qi。如果无解，请输出NO。【输入输出样例】输入#110770 77 5633 1 211545 1 499683 3 227858 3 257723 37 13572 26 11867 17 17829 3 263528 4 109输出#12 385NONONO11 783 2412 286NONO6 88【数据范围】以下记m=n-ed+2。保证对于100%的数据，1k105，对于任意的1ik，1ni1018，1eidi1018，1m109。参考源码1：1. #include2. #include3. usingnamespacestd;4. #definelllonglongint5. intmain()6. llk,n,e,d,m;7. llp,q;8. lltemp1,temp2,root;9. cink;10. for(lli=1;ined;12. m=n-e*d+2;13. temp1=m*m-4*n;14. root=sqrt(temp1);15. if(root*root!=temp1)16. coutNOendl;17. continue;18. 19. temp2=m-root;20. if(temp2%2=0)21. p=temp2/2;22. 23. q=m-p;24. coutpqendl;25. 26. return0;27. 算法思路1：直接计算出p和q的计算公式，一次计算的时间复杂度为o(1)，整体复杂度为o(k)。由p+q=m,pq=n可以推到出p=m-m2-4n2,q=m-p。题目要求是p=q。在计算p的公式中，m2-4n0，在程序中不需要进行判断。在程序中需要判断两个点：（1）m2-4n能否有完全平方根；（2）m-m2-4n能否被2整除。运行截图1：测试用例1测试用例2参考源码2：1. #include2. usingnamespacestd;3. #definelllonglongint4. intmain()5. llk,n,e,d,m;6. llp,q;7. cink;8. for(lli=1;ined;10. m=n-e*d+2;11. llbegin=1,end=m/2;12. llarea;13. while(begin=end)14. p=(begin+end)/2;15. q=m-p;16. area=p*q;17. if(arean)20. end=p-1;21. else22. coutpqend)27. coutNOendl;28. 29. 30. return0;算法思路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. #include2. usingnamespacestd;3. #definelllon
收藏
编号：347739571
类型：共享资源
大小：190.32KB
格式：DOCX
上传时间：2023-03-20
15
金贝
- 关 键 词：
-
CSP-J
2022年
真题
源码
分析
- 资源描述：
-
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展开阅读全文
金锄头文库所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
