PAT乙级考后杂谈

大家好，又见面了，我是你们的朋友全栈君。

上周末去隔壁大学参加了PAT乙级的考试，结果没想到第一次考试就出了点小问题…

本来考试是在1.30全国各个考点都同时开始（因为要排名），结果快到1.30的时候机房连不上网络，最后我们这个考点直接移后到将近2.30才开始考试，虽然结束时间也移后了，不过这多年不遇的突发情况直接让我遇到也太真实了。。。

小插曲过后，再说下考试内容，乙级确实难度不大，三小时五道题，前两道题基本是送分题，虽然作者本人比较菜花了四五十分钟，但基本也在可接受范围内。

接下来主要说下这个第三题，这题真的坑我不浅，简单说下题目：输入两个数n，m（0<=n<m<=25000)，在此范围内找到一个数a使得它与另外一个（0，25000）范围得数b满足如下关系:a^3 – (a-1)^3=( b^2+ (b-1)^2) ^2(原题不是这样给的，这是换算完的结果），然后满足此关系的数对a,b按照a的大小顺序输出在屏幕上，如果找不到则输出No Solution

简单分析下这题，显然暴力使用双重循环遍历一定会超时，所以在外层循环确定了a时，内层查找b时使用二分的办法就不会超时了。

我当时的第一思路就是如此，但是在写第二层的二分查找时，出现了一个问题：对于给定的m，n只能找出一组答案，第二次进入循环时，L和R（左右端点）的值不会改变，所以导致只能找到一组解。当时百思不得其解，花了一个多小时在上面也没能成功找出问题。考试结束后我根据回忆重新写了这道题（基本与我考试写的一模一样），试图找出问题所在，结果程序运行结果竟然正确。。。下贴出代码：（考试和我本机都是使用DEVC++，只不过考试时的版本稍老一些）

//0<n<m<25000,(a^3-(a-1)^3)=(b^2+(b-1)^2)^2 
#include <iostream>
using namespace std;
long long a3(long long a)
{
	return (a*a*a-(a-1)*(a-1)*(a-1));
}
long long b2(long long b)
{
	return (b*b+(b-1)*(b-1))*(b*b+(b-1)*(b-1));
}
int main()
{
	int n,m;
	long long l=1,r=25000;
	long long mid;
	cin >> n >> m;
	for(int i=n;i<=m;i++)
	{
		l=1;
		r=25000;
		while(l<=r)
		{
			mid=(r-l)/2+l;
			if(a3(i)==b2(mid))
			{
				cout << i << ' ' << mid << endl;
				break;
			}
			else if(a3(i)>b2(mid))
			{
				l=mid+1;
			}
			else
			{
				r=mid-1;
			}
		}
		
	}
	return 0;
}

真的很怪。。因为我坚信我的思路没错，在那里debug一个多小时，导致后面的题（第四题和这道题差不多，第五题涉及到链表，稍微麻烦一些）没什么时间做。。难顶

不过上述代码确实也不是完美的，有什么缺陷希望有大佬可以指教一下，也许能启发我想到考试中我到底这道题出了什么问题

总体来说乙级不是很难，基本不涉及什么算法和数据结构，虽然出了点小插曲不过拿来练手还是不错的，明年甲级倒是要好好考一下