PAT甲级刷题笔记（2）

PAT甲级刷题笔记（2）

26. 毕业生录取（1080）

这题的难点在于正确地录取学生到正确学校。开始我理解错了，以为志愿没有优先级，从学校的角度出发，遍历有报名本校的学生，择优录取，但这样发现一个学生可能会先被第二志愿录取，但他实际更愿意去第一志愿，若也可以录取的话，就会出错，而且这样做要遍历m（学校个数)遍学生列表，时间复杂度很大。

实际上，可以仅遍历按成绩排名的学生列表一遍。对每个学生，遍历他的志愿，只有当该学校名额已达到限值，且本学生不与该校上一个录取的名次相同时，才会落选，其它情况一定可以入选。因此我们只需要增加两个额外数组分别存储各个学习当前的录取人数和上一个录取学生名次就可以实现该功能。

本题还有一个注意点是，输出录取情况要按序号输出，因此我又对录取结果每行做了行排序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;struct Students{int ID;int Ge,Gi,avg;int choices[5];int Rank;//int Ad=0;//表示改名学生是否已被录取
}stu[40010];int school[110];
int admis[110]={0},Lrank[110];//各学校实际录取人数，和录取上一名的志排名
int num[110][40010];//存储录取学生序号bool cmp(Students &x,Students &y){if(x.avg!=y.avg) return x.avg>y.avg;else return x.Ge>y.Ge;
}int main(){int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=0;i<m;i++){scanf("%d",&school[i]);}for(int i=0;i<n;i++){scanf("%d%d",&stu[i].Ge,&stu[i].Gi);stu[i].avg=(stu[i].Ge+stu[i].Gi)/2;stu[i].ID=i;for(int j=0;j<k;j++){scanf("%d",&stu[i].choices[j]);}                 }sort(stu,stu+n,cmp);stu[0].Rank=1;                     for(int i=1;i<n;i++){if(stu[i-1].avg==stu[i].avg && stu[i-1].Ge==stu[i].Ge){stu[i].Rank = stu[i-1].Rank;}else {stu[i].Rank=i+1;}    }fill(Lrank,Lrank+m,m);//初始化Lrank数组for(int i=0;i<n;i++){for(int j=0;j<k;j++){int t = stu[i].choices[j];//当前目标学校if(admis[t]>=school[t] && stu[i].Rank>Lrank[t]){//当前目标学校已达到录取名额，且排名不并列，无法录取continue;}else{//能够被录取,录取后break避免重复录取                                Lrank[t]= stu[i].Rank;num[t][admis[t]]=stu[i].ID;admis[t]++;break;}}}for(int i=0;i<m;i++){sort(num[i],num[i]+admis[i]);//默认升序排列for(int j=0;j<admis[i];j++){if(j!=0) printf(" ");printf("%d",num[i][j]);}printf("n");}                    return 0;
}

语法：（1）对二维数组按行排序：sort(num[i],num[i]+admis[i]);不指明比较函数默认升序排列；

（2）小技巧：按平均分排名时，由于成绩个数一样，可以直接比较总分，可以避免平均值带来的误差。

27. 校园停车（1095）

这题整体上还是比较复杂，参考解答后大致完成了。其任务主要有二：

（1）查询任意时刻的停车数量，由于是升序查找，很自然想到把停车记录按时间升序排列。这个问题主要难点在于如何排出无效记录的干扰，因此我们可以先按车牌号排序，筛选出有效的停车记录，保存到另一个备份数组valid中，再对其进行升序查找即可。

（2）输出停车总时间最长的车号码，且可能有多个结果。这个问题要从一个int数据映射到车牌号这一string，因此可以考虑用map建立这一映射关系，在筛选有效停车记录的同时，完成停车时长的计算。

但不知道为什么，按照答案思路做的，第4个测试点老是无法通过，找了几遍也没发现错误原因o(╥﹏╥)o

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=10010;
struct cars{char id[8];    int time;//按秒存储，便于比较也减少内存使用char status[4];//存储in/out状态
}all[maxn],valid[maxn];map<string,int>Packtime;//建立从车牌到总停车时间的映射bool cmp1(cars x,cars y){//按车牌号、时间的优先级排列if(strcmp(x.id,y.id)!=0) return strcmp(x.id,y.id)<0;else return x.time<y.time;
}bool cmp2(cars x,cars y){//按时间的优先级排列return x.time<y.time;
}int main(){int n,k;scanf("%d%d",&n,&k);int hh,mm,ss;for(int i=0;i<n;i++){scanf("%s%d:%d:%d%s",all[i].id,&hh,&mm,&ss,all[i].status);all[i].time=3600*hh+60*mm+ss;}//先按车牌排列，便于选出有效的停车状态sort(all,all+n,cmp1);int num=0,maxtime=-1;//有效记录数，最大总停留时间for(int i=0;i<n-1;i++){//选出有效的停车记录if(strcmp(all[i].id,all[i].id)==0 && strcmp(all[i].status,"in")==0 && strcmp(all[i+1].status,"out")==0){valid[num++] = all[i];valid[num++] = all[i+1];int temp=all[i+1].time-all[i].time;//本次停车时间unt(all[i].id)==0){//count用于判断map是否存在该键值，第一次生成时停留时间置零Packtime[all[i].id] = 0;}Packtime[all[i].id]+=temp;maxtime=max(maxtime,Packtime[all[i].id]);}}//对有效记录按停车时间排序，便于升序查找sort(valid,valid+num,cmp2);int sum=0,Ti;//当前停车数量,T本次查找时刻int now=0;//由于是升序查找，用now表示当前查询到的位置for(int i=0;i<k;i++){//查询scanf("%d:%d:%d",&hh,&mm,&ss);Ti=3600*hh+mm*60+ss;       while(valid[now].time<=Ti && now<num){if(strcmp(valid[now].status,"in")==0) sum++;else sum--;now++;}//已经查询到了本时刻之后的记录，查询完成，可以输出printf("%dn",sum);}//遍历车牌号，找到等于最长停车总时间的车牌号map<string,int>::iterator it;//使用迭代器it遍历访问for(it=Packtime.begin();it!&#d();it++){if(it->second == maxtime){//it->first是当前映射的键，it->second是当前映射的值printf("%s ",it->first.c_str());//c_str返回当前字符串的首字符地址，//printf输出字符串也是根据其首地址（数组名即为其首地址）}}printf("%02d:%02d:%02dn",maxtime/3600,maxtime%3600/60,maxtime%60);return 0;
}

语法：（1）map的用法，如map,count，迭代器访问等方法等，注意头文件map；

(2) max函数的用法。

散列

以下5题为散列专题，核心思想是用空间换时间，主要是采用直接定址法，将输入内容直接保存到相应数组下标内，从而减少了查询比较的时间。

28. 旧键盘

用双指针分别遍历两个字符串，找到无法匹配的项即是键盘坏掉的键。关键在于避免重复输出和大小写不区分。可以建立辅助数组，根据其值确定该字符是否已被输出过。

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;int num[37]={0};//37个字符对应图中37个数组元素
bool hashFunc(char a){//order变量用于记录出现次序int t;    if(a>='A'&&a<='Z'){t=a-'A';if(num[t]==0) {num[t]=1; //第一次发现坏键return false;}}else if(a>='a'&&a<='z'){t=a-'a';if(num[t]==0) {num[t]=1; //第一次发现坏键return false;}}else if(a>='0'&&a<='9'){t=a-'0'+26;if(num[t]==0) {num[t]=1; //第一次发现坏键return false;}}else{if(num[36]==0){num[36]=1; //第一次发现坏键return false;}}return true;
}int main(){string s1,s2;cin>>s1>>s2;int i=0,j=0;while(s1[i]!=''||s2[j]!=''){if(s1[i]!=s2[j]){if(hashFunc(s1[i])==false){//第一次发现坏键//printf("%c",&s1[i]);if(s1[i]>='a'&&s1[i]<='z')s1[i]-=32;cout<<s1[i];}i++;}else{i++;j++;}}    return 0;
}

29. 买或不买（1039）

问题本质是比较两个字符串多出的字符个数或相应字符缺失的个数。我们可以先建立两个辅助数组存储两个字符串中每个字符出现频率，在遍历比较两个数组，计算其缺失或多余个数。

#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;const int maxn=1010;
//分别存储两条字符串的各个字符数量
int bead1[128]={0}, bead2[128]={0};
char s1[maxn],s2[maxn];int main(){scanf("%s%s",s1,s2);int len1=strlen(s1),len2=strlen(s2);for(int i=0;i<len1;i++){bead1[s1[i]]++;}for(int i=0;i<len2;i++){bead2[s2[i]]++;}int extra=0,miss=0;//分别表示多买的和缺少的珠子数量for(int i=0;i<128;i++){int temp=bead1[i]-bead2[i];if(temp>0){extra+=temp;}else{miss+=temp*(-1);}}if(miss>0){printf("No %d",miss);}else{printf("Yes %d",extra);}return 0;
}

30. 独一无二（1041）

简单题，找到输入数组中第一个不重复元素。我们可以建立两个数组，一个用于保存输入数据，一个用于保存数据的出现个数。在读入完成后，对输入数据顺序遍历，找到第一个个数为1的元素即可。

#include<iostream>
#include<cstdio>
using namespace std;int num[10010]={0};
int inPut[100010];int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&inPut[i]);num[inPut[i]]++;}int flag=0;for(int i=0;i<n;i++){if(num[inPut[i]]==1){printf("%d",inPut[i]);flag=1;break;}}if(flag==0) printf("None");return 0;
}

31. 字符串减法（1050）

简单题，从第一个字符串中减去第2个字符串中出现的所有字符并输出。方法是先遍历s2，得到它所有的字符，在对s1做遍历检测是否输出。

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int maxn=10010;
char s1[maxn],s2[maxn];
bool num[128]={false};int main(){scanf( "%[^n]", s1 );getchar();//用getcahr吸收换行scanf( "%[^n]", s2 );//printf("%s",s2);int i=0,j=0;while(s2[i]!=''){//printf("%d",s2[j]);num[s2[i]]=true;i++;}while(s1[j]!=''){if(num[s1[j]]==false){printf("%c",s1[j]);}j++;}return 0;
}

语法：（1）带空格的字符串如何读入，由于gets()不允许用了，查阅后改用scanf( "%[^n]", s1 );成功读入.scanf("%[^n]",str)这句话的作用是碰见了回车就退出然后把缓冲区里面的内容按字符串格式输入str中，然后回车还留在缓冲区里。所以当使用for循环对string进行赋值时必须加入getchar()吃掉上一个回车，不然就会出错。

除此之外，也可用line()读入；

32. 找硬币（1048）

这题是从硬币中找出和为目标值的两个硬币面额输出。特别注意要统计硬币个数，因为两个7块钱支付14元的情况是允许的。筛选方法是看i面额对应的m-i是否存在，注意避免辅助数组越界。

这题我为了输出小的结果，保存了输入数据并进行sort。其实这没有必要，因为输入数据已经有序表示在辅助数组中（那些数值>=1的下标），所以仅需线性时间即可，不过这题比较简单，排序也不会超时。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int coins[1010]={0};
int num[100010];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&num[i]);coins[num[i]]++;}sort(num,num+n);int flag=0;for(int i=0;i<n;i++){int t=m-num[i];//要注意到面额可能大于总金额的情况，此时已经不可能支付了if (t<0) break;if((coins[t]>0&&t!=num[i]) ||(coins[t]>1&&t==num[i])){//两个硬币面额相同时，数量要大于等于2printf("%d %d",num[i],t);flag=1;break;}}if(flag==0) printf("No Solution");return 0;
}

贪心

33. 月饼

为了使总利润最大，应该循环优先选择当前单价最高的月饼，注意需求量大于月饼总数的情况。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;struct Moon{double weight,prices;double unitPrice;
}moo[1010];bool cmp(Moon x, Moon y){//按单位利润排序return x.unitPrice>y.unitPrice;
}int main(){int n,d;scanf("%d%d",&n,&d);for(int i=0;i<n;i++){scanf("%lf",&moo[i].weight);             }for(int i=0;i<n;i++){scanf("%lf",&moo[i].prices);moo[i].unitPrice=moo[i].prices/moo[i].weight;}sort(moo,moo+n,cmp);/*for(int i=0;i<n;i++){printf("%.4f ",moo[i].unitPrice);}*/double profit=0;int j=0;while(d>=moo[j].weight && j<n){//注意考虑全部库存也不能满足需求时，可能发生越界profit+=moo[j].prices;d-=moo[j].weight;j++;}if(j<n){profit +=moo[j].prices*d/moo[j].weight;}printf("%.2f",profit);return 0;
}

34.  加不加油（1033）

这题有一定繁琐，要注意理清逻辑。本题的贪心策略在于优先加满最便宜的油。基本思路是：从出发点出发遍历所有的加油站，分以下情况讨论：

（1）下一站距离大于续航范围时，则无法抵达目的地

（2）续航范围内有加油站时，分以下两种情形：

① 范围内有比当前站点单价更低的加油站，则只需补充能抵达该加油站的油即可，抵达后油量清0；

② 范围内没有单价更低的加油站，则在本站加满油，然后抵达范围内最低的加油站，抵达后油量减去路上消耗。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;struct Gas{double dis;double price;
}gas[510];bool cmp(Gas x,Gas y){return x.dis<y.dis;
}int main(){double Cmax,Dis,Davg;int n;scanf("%lf%lf%lf%d",&Cmax,&Dis,&Davg,&n);for(int i=0;i<n;i++){scanf("%lf%lf",&gas[i].price,&gas[i].dis);}//对加油站按到出发点距离排序sort(gas,gas+n,cmp);if(gas[0].dis!=0){//第一个加油站不在起点printf("The maximum travel distance = 0.00");return 0;}//把终点设成距离为Dis和单价为0的最后一个加油站gas[n]={Dis,0};double longest=Cmax*Davg;//加满油的行驶距离    double cost=0;//已花费油费    int k=1;double tank=0;//油箱当前储备油量for(int i=0;i<n;i++){int diff=gas[k].dis-gas[i].dis;if(diff>longest){//超过续航范围printf("The maximum travel distance = %.2f",gas[i].dis+longest);return 0;}//下一站没超过续航范围，则检索范围内的加油站double Di_k=gas[k].dis-gas[i].dis;//i和k两个站间距离        int next=k;//保存范围内最便宜的加油站下标int flag=0;//用于每次选择时的指示标志while(Di_k<=longest&&k<=n){            if(gas[k].price<=gas[i].price){//找到更便宜的加油站，则先加恰能到达该站的油即可double need=(gas[k].dis-gas[i].dis)/Davg-tank;//需要加的实际油量cost+=need*gas[i].price;//printf("k=%d Di_k=%.2lf  cost=%.2lfn",k,Di_k,cost);flag=1;break;}if(gas[next].price>gas[k].price){next=k;}k++;Di_k=gas[k].dis-gas[i].dis;}if(flag==1){//找到更便宜的加油站了tank=0;i=k-1;k++;continue;}//否则加满油，开往范围内最便宜的加油站，即next站cost+=(Cmax-tank)*gas[i].price;//printf("next=%d price=%.2lf  cost=%.2lfn",next,gas[i].price,cost);tank=Cmax-(gas[next].dis-gas[i].dis)/Davg;i=next-1;}printf("%.2f",cost);   return 0;
}

35. 魔力优惠券（1037）

本题把输入的两个数组分别排序，然后将其正数对应相乘，负数对应相乘，最后相加即可得到最大优惠。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long LL;LL coupon[100010],product[100010];int main(){int Nc,Np;scanf("%d",&Nc);int Cp=0,Cn=0;for(int i=0;i<Nc;i++){scanf("%lld",&coupon[i]);if(coupon[i]<0)  Cn++;else Cp++;}scanf("%d",&Np);int Pp=0,Pn=0;for(int i=0;i<Np;i++){scanf("%lld",&product[i]);if(product[i]<0) Pn++;else Pp++;}//printf("%lld %lld %lld %lldn",Cn,Cp,Pn,Pp);sort(coupon,coupon+Nc);    sort(product,product+Np);LL sum=0;for(int i=0;i<Pn&&i<Cn;i++){//先算负数相乘结果sum+=coupon[i]*product[i];//printf("%lldn",sum);}for(int i=1;i<=Pp&&i<=Cp;i++){//先算负数相乘结果sum+=coupon[Nc-i]*product[Np-i];//printf("coupon=%lld,product=%lld,sum=%lldn",coupon[Cn+i],product[Pn+i],sum);}printf("%lld",sum);return 0;
}

语法：（1）typedef long long LL，重定义类型名为LL，

（2）long long类型占位符%lld。

36. 用0交换（1067）

这题有一个错觉：由于交换时都是将0和0当前下标对应数字交换，所以容易以为只要输入有几个数字和下标不同，就交换几次。但在0交换到首位时，由于必须用0交换，得先让0和一个无序的数字交换，再继续重复上述过程，即会产生1次无用交换。

因此我们用left统计输入时无序个数，每完成一次有效交换，则left-1（对把0换到0上的操作要再-1）；对无效操作把0换到其它随机位置上，left+1。要注意为了避免随机寻找与0位上0的交换的无序数字超时，每次寻找应该在上次查找位置之后继续进行，若从数组头部开始会超时。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int order[100010];//用来存储数字当前的序号
int check(int k){//为了避免寻找不在位置上的元素超时，应该从上次搜寻结果往后查找    for(int i=k;i<n;i++){if(order[i]!=i){return i;            }}return n;
}int main(){scanf("%d",&n);    int t,left=0;    for(int i=0;i<n;i++){scanf("%d",&t);order[t]=i;if(t!=i) left++;}//开始执行交换int sum=0;int k=1;while(left>0){            if(order[0]!=0){int temp=order[0];order[0]=order[order[0]];order[temp]=temp;if(order[0]==0) left--;left--;            }else{//0在0位上,随机找一个没排好的数交换            k=check(k);     order[0]=order[k];order[k]=0;left++;}sum++;}printf("%d",sum);return 0;
}

37. 寻找最小数字（1038）

这题很自然的想法是对输入数字按字符串升序排列再组合，但这样对于（321,32）这样的组合会出错，如按排序则结果32321，实际最小组合为3213。

本题正确的贪心策略应为，若s1+s2<s2+s1，则s1排在s2前面。证明思路：

（1）显然最小数字组合具有最优子结构特性；

（2）贪心性质：采用反证法思想，若s1+si<si+s1，则s1一定排在si前面，否则会破坏最优解，对所有字符串可同理证明。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;string str[10010];bool cmp(string x,string y){return x+y<y+x;
}int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>str[i];}sort(str,str+n,cmp);string ans;for(int i=0;i<n;i++){//拼接结果ans+=str[i];}while(ans.size()!=0 && ans[0]=='0'){//去除前导ase(ans.begin());}if(ans.size()==0) cout<<0;//去除前导0为空时，说明结果是0else cout<<ans;return 0;
}

语法：主要是掌握string的用法

（1）string输入输出只能用cin,cout，不能用scanf/printf（除非用c_str转化为字符数组）；

（2）string可以直接用==!=,<,>等进行比较；

（3）erase删除元素

二分

二分法核心思想在于，对于一个有序序列，我们可以利用有序这种数据性质，比遍历更加高效的查找目标。因此，使用二分法的思想关键在于：

（1）构建有序序列，有时候有序序列是显然的，有时要学会自己构造，比如正数累加和序列；

（2）正确书写二分查找函数，关键是要明确自己查找的目标是一个值还是一个区间，是开区间还是闭区间。

38. 完美序列（1085）

本题要求从输入数据找出满足M<=m*p的最长完美序列长度。思路也比较明确：先排序，在遍历筛选出最长序列长度，计算方法是找到第一个>m*p的元素下标减去序列首元素下标即为长度。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
int num[100010];
int n;int binarySearch(int left,int right,LL x){//二分查找第一个大于x的元素下标if(num[right]<=x) return right+1;int mid;left++;while(left<right){mid=(left+right)/2;if(num[mid]>x){right = mid;            }else{left = mid+1;}}return left;
}int main(){int p;scanf("%d%d",&n,&p);for(int i=0;i<n;i++){scanf("%d",&num[i]);}sort(num,num+n);int len=1;//完美序列长度for(int i=0;i<n;i++){//LL m=num[i]*p;这种写法会导致int超限时得到错误结果，//LL m=(LL)num[i]*p;正确写法，要进行强制类型转换len =max(len,binarySearch(i,n-1,(long long)num[i]*p)-i); //更新完美序列长度       }printf("%d",len);        return 0;
}

本题的二分函数本质上是找到>x的第一个数组下标。

if(num[right]<=x) return right+1;

如果没加这句话，right= n；加了则right=n-1，主要是要注意对x大于所有元素的情况。

语法：注意int相乘超限时，要做强制类型转化再赋给Long long型；LL m=num[i]*p;不转化的话m的结果就可能时错的。可以参考下面的输出结果进行比较

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
//int num[5] = { 9,9,9,10,11 };void binarySearch( LL x) {//二分查找第一个大于x的元素下标printf("%lldn",x);
}int main() {    int x = 2147483647;int p = 2;LL xp= x * p;LL xp2 =(LL) x * p;printf("%lldn", xp);printf("%lldn", xp2);binarySearch(xp);binarySearch((LL)x*p);return 0;
}

结果如下：

-2
4294967294
-2
4294967294

39. 找基数（1010）

这题目的是让找到一个进制，使给定两个数字相等。核心问题在于：

（1）如何比较两个不同进制的数字？用字符串方式存储两个数字，写一个函数，根据给定进制将字符串数字转化为10进制下数值，便于比较大小。这里要注意，给定的数字在进制很大时，即使是在long long情况下也会超限，注意讨论；

（2）如何正确选择出合适的进制，使两者相等。首先要确定进制的范围，在进行比较，下限显然是s2中出现最大数字+1，如果在5进制中出现>=5的数字显然不合理；上限则应该是s1的10进制数值和下界进制中较大值+1。因为如果进制更大，若s2是两位以上数字（最小为10），在该进制下肯定大于s1；而s2是1位数字，则s2的值介于0-36之间，其值大小与进制上限无关，去这个上界也行。

为了避免超时，在区间内寻找目标进制时应该采用二分法。

当然，还有一些细节要说明：

（1）可以把要求进制的数通过交换统一处理成s2，这样避免后面同样的操作分情况做两遍，可以有效减少代码长度，这也是一种常用小技巧；

（2）超限问题，前面说过在进制很大时，s2进制转化后可能会溢出导致转化结果num2<0，这个情况下，s2肯定是大于s1的，都应把进制调小继续求解。

（3）进制上界取s1的10进制数值和下界进制中较大值+1，是保证区间寻找至少会进行1次，避免s1=s2情况下，直接return-1，造成错误。

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
typedef long long LL;
string s1,s2;
LL num1,num2;
//const LL inf=(1LL<<63)-1;//long long最大值2^63-1LL Transform(string s,LL radix){//把字符串转化为10进制的数，便于比较int i=0;LL num=0;while(s[i]!=''){if(s[i]>='0'&&s[i]<='9'){num =num*radix+s[i]-'0';}else{num =num*radix+s[i]-'a'+10;}if(num<0){//若溢出或超过s1的十进制return -1;}i++;}return num;
}LL binary(LL l,LL r){//二分查找合适的进制LL mid;while(l<=r){mid=(l+r)/2;num2 = Transform(s2,mid);//cout<<"进制为"<<mid<<" num2="<<num2<<endl;if(num1==num2){//找到合适的进制return mid;}else if(num2<0||num1<num2){//溢出时肯定s2大，当前进制大了r=mid-1;}else{l=mid+1;}}return -1;
}int main(){int tag;LL radix;cin>>s1>>s2>>tag>>radix;//if(s1==s2) cout<<radix;if(tag==2){//统一处理成指定s1的radix，减少代码冗余string temp=s2;s2=s1;s1=temp;}num1 = Transform(s1,radix);//cout<<num1;LL M='0',i=0;;//寻找x2最大字符while(s2[i]!=''){if(s2[i]>M){M=s2[i];}i++;}if(M>='0'&&M<='9'){M-='0';}else{M=M-'a'+10;}//进制的下界为s2出现最大字符对应数字+1//进制的上届为s1对应的十进制数字 LL high=max(M,num1)+1;//确定上届，这里取二者大值，保证后续一定会进行比较LL result=binary(M+1,high);if(result==-1){cout<<"Impossible";}else cout<<result;    return 0;
}

语法：（1）const LL inf=(1LL<<63)-1;//long long最大值2^63-1

定义最大值的方法，LL共64位，最大值为2^63-1，即把1左移63位再-1

40. 在火星上购物（1044）

本题要求在输入数字中找到连续的序列，使之和等于M，如果找不到，就输出大于M的最小值序列。难点在于：

（1）如何确定这样的序列，如果从头开始暴力地进行累加判断，时间复杂度是n^2，肯定会超时。因此在读入序列时，顺便求出到第i个元素的累计和，这样i-j的和，只需要做sum[j] -sum[i]一次减法就可以了，在利用二分法搜寻到 j 的坐标，这样时间复杂度可以降到n(logn)。

（2）如果能找到等于M的情况，那直接输出就行。但如果找不到，就得在过程中比较出当前的最小和，最后再来根据最小和输出。因此我又设置了两个额外数组i_j和surpass，分别存储 i 对应的 j坐标和值，根据和值结果就可以输出。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;const int maxn=100010;
int n,m;
int num[maxn],sum[maxn];//存储输入数字，累计和
int i_j[maxn];//下标i处存储对应的j下标
int surpass[maxn]={0};
int sub;
int binary(int i){    int l=i,r=n,mid;int flag=0;if(sum[r]-sum[i-1]<m) return -1;while(l<=r){mid=(l+r)/2;sub=sum[mid]-sum[i-1];if(sub==m) {i_j[i]=mid;return 0;}if(sub>m){r=mid-1;surpass[i]=sub;//在这里更新surpass[i],防止后续找到<m的，覆盖了subi_j[i] = mid;//printf("surpass[%d]=%dn",i,sub);flag=1;}else{l=mid+1;            }}if(flag==1){//虽然没找到确切和，但找到了更大的        return 1;        } 
}int main(){scanf("%d%d",&n,&m);int total=0;sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&num[i]);total+=num[i];sum[i]=total;}int Pass=0;for(int i=1;i<=n;i++){int order=binary(i);if(order==0){//找到合适的printf("%d-%dn",i,i_j[i]);Pass=1;}else if(Pass==0&&order==1){total=min(total,surpass[i]);}}if(Pass==0){for(int i=1;i<=n;i++){if(surpass[i]==total){printf("%d-%dn",i,i_j[i]);}}}return 0;
}

双指针与排序

41. 插入排序 or 归并排序（1089）

本题是给出排序的中间情况，判断使用的是插入还是归并排序。由于结果一定是其中一种，且归并排序时间复杂度更低，所以我先模拟归并排序，每完成一轮，进行比较，若相同则再归并一次输出，否则就是插入排序，在排一个输出就行。

当然，由于本题数据较小，且只输出中间结果，也可以用sort对前i个元素排序和插入排序结果比较。归并排序也同理可用sort代替，不过为了熟悉归并排序，还是按归并书写了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int num[110],sortNum[110];
int n;//执行一轮归并，对两个有序序列[L1,R1]，[L2,R2]合并成一个有序序列
void merge(int L1,int R1,int L2,int R2){int i=L1,j=L2;int temp[110],index=0;while(i<=R1 && j<=R2){if(num[i]<num[j]){temp[index++]=num[i++];}else {temp[index++]=num[j++];}}//将有剩余的元素加入到temp中while(i<=R1) temp[index++] = num[i++];while(j<=R2) temp[index++] = num[j++];for(i=0;i<index;i++){num[L1+i]=temp[i];}
}void outNum(int a[]){//输出下一轮排序结果printf("%d",a[0]);for(int i=1;i<n;i++){printf(" %d",a[i]);}    printf("n");   
}void InsertSort(){int index;//先找到当前有序位置for(int i=0;i<n-1;i++){if(sortNum[i]>sortNum[i+1]){index=i+1;break;}}sort(sortNum,sortNum+index+1);printf("Insertion Sortn");outNum(sortNum);
}int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&num[i]);        }for(int i=0;i<n;i++){scanf("%d",&sortNum[i]);        }//检测归并排序int out=0;for(int step=2;step/2<=n;step*=2){int flag=0;        for(int i=0;i<n;i+=step){//对每一组int mid=i+step/2-1;if(mid+1<n){//右子区间若存在则合并merge(i,mid,mid+1,min(i+step-1,n-1));                }                      }//i循环if(out==1){printf("Merge Sortn");outNum(num);return 0;}  //一轮归并完成后进行检查//outNum(num);for(int j=n-1;j>=0;j--){if(num[j]!=sortNum[j]){flag=1;}                }if(flag==0){//说明是归并排序out=1;                 }}InsertSort();return 0;
}

注意点：（1）归并排序共两重循环，第一重step是用于逐步扩大分组，第二重i循环是对相邻两分组进行归并，第二重循环执行完一次才完成一次归并，并不是使用一次Merge函数就完成一次归并；

（2）注意使用merge函数的下标是从0还是从1开始，上述使用的0-n-1；

42. 中位数（1029）

本题是查找两个有序数组的中位数，显然给定两数组大小，就可以确定中位数的序号，然后使用双指针遍历两个数组找到这个序号即可。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=200010;
LL num1[maxn],num2[maxn];int main(){int n1,n2;scanf("%d",&n1);for(int i=1;i<=n1;i++){scanf("%lld",&num1[i]);}scanf("%d",&n2);for(int i=1;i<=n2;i++){scanf("%lld",&num2[i]);}int index=1,mid=(n1+n2+1)/2;int i=1,j=1;while(i<=n1&&j<=n2){if(num1[i]<num2[j]){            if(index==mid){printf("%lld",num1[i]);return 0;}i++;index++;}else {if(index==mid){printf("%lld",num2[j]);return 0;}j++;index++;}}if(i<=n1){//说明n2以比完printf("%lld",num1[mid-n2]);}else{printf("%lld",num2[mid-n1]);}return 0;
}

43. PAT数量（1093）

这题是要统计序列中能够形成的PAT子序列个数，我的想法是从头开始遍历，逐步确定PPAPAT的数量，因为当前A能形成PA的数量取决于之前P的数量，当前T能形成PAT的数量取决于之前的PA的数量，利用这个递推关系就可以遍历计算出结果了。

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn=100010;
const int MOD=1000000007;
char str[maxn];int main(){scanf("%s",str);    int sumPA=0,sumPAT=0;int sum=0,numP=0;   for(int i=0;i<strlen(str);i++){        if(str[i]=='P'){numP++;}else if(str[i]=='A'){//当前A可组成PA序列个数为numP//累计的A可以组成PA序列个数sumPAsumPA = (sumPA+numP)%MOD;            }else if(str[i]=='T'){  //当前的T可以组成PAT序列个数为sumPA//累计的T可以组成PAT序列个数如下sumPAT = (sumPAT+sumPA)%MOD;}}printf("%d",sumPAT);return 0;
}

当然，也可以利用网络上的解答，即注意到A可以形成PAT数量等于左边P数量*右边T数量。 

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn=100010;
const int MOD=1000000007;char str[maxn];
int leftNumP[maxn]={0};int main(){scanf("%s",str);int len = strlen(str);for(int i=0;i<len;i++){//计算左边P数量if(i>0){leftNumP[i]=leftNumP[i-1];}if(str[i]=='P'){leftNumP[i]++;}}int ans=0,rightNumT=0;for(int i=len-1;i>=0;i--){if(str[i]=='T'){rightNumT++;}else if(str[i]=='A'){ans=(ans+leftNumP[i]*rightNumT)%MOD;}}printf("%dn",ans);return 0;
}

44. 找快排主元（1101）

主元要求大于左边所有元素，小于右边所有元素。因此可以分别从左遍历和从右遍历一遍数组，找出每个元素左边和右边的最大值，在比较是否符合要求。

注意：主元可能不存在，比如2,1序列中2和1都不能做主元，但是输出时要输出一个空行。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
const int inf=(1<<31)-1;int num[maxn],leftMax[maxn],rightMin[maxn];
int pivot[maxn];int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&num[i]);}//为了便于处理，在头尾加上两个元素num[0]=0;num[n+1]=inf;int Max=num[0];for(int i=1;i<n+1;i++){//找出第i个数据左边的最大值        Max=max(num[i-1],Max);leftMax[i]=Max;}int Min=inf;for(int i=n;i>0;i--){//找出第i个数据右边的最小值        Min=min(num[i+1],Min);rightMin[i]=Min;}int sum=0;for(int i=1;i<=n;i++){if(num[i]>leftMax[i]&&num[i]<rightMin[i]){pivot[sum++]=num[i];}}printf("%dn",sum);if(sum==0) printf("n");for(int i=0;i<sum;i++){if(i<sum-1)printf("%d ",pivot[i]);else printf("%dn",pivot[i]);}    return 0;
}

语法：int最大值的定义方法：0x7fffffff 或者(1<<31)-1，都表示2^31-1，即int下的最大值。

44. 数字黑洞（1069）

模拟题，难度不大。基本步骤是对数字做拆解，然后排序得到最大值和最小值，作差。注意的点事输入本身为6174时，也要做一次循环，所以应该用do-while循环。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int a[4];
void extract(int n){    for(int i=0;i<4;i++){a[i]=n%10;n/=10;}
}int increase(){int n=a[0];for(int i=1;i<4;i++){n=n*10+a[i];}return n;
}int decrease(){int n=a[3];for(int i=2;i>=0;i--){n=n*10+a[i];}return n;
}int main(){int n;scanf("%d",&n);extract(n);int flag=0;for(int i=1;i<4;i++){if(a[i]!=a[0]){flag=1;}}if(flag==0) {printf("%04d - %04d = 0000n",n,n);return 0;}int M,m;            do{extract(n);sort(a,a+4);m=increase();M=decrease();        n=M-m;printf("%04d - %04d = %04dn",M,m,n);}while(n!=6174);//采用dowhile是避免输入就是6174情况return 0;
}

46. 电梯（1008）

简单题，根据输入序列，统计上楼和下楼数，再乘以对应时间+停顿时间即可。

#include<cstdio>
using namespace std;int num[100010];
int main(){num[0]=0;int n;scanf("%d",&n);int upFloor=0;int downFloor=0;for(int i=1;i<=n;i++){scanf("%d",&num[i]);if(num[i]>num[i-1]){upFloor+=(num[i]-num[i-1]);//printf("%dn",upFloor);}else{downFloor+=(num[i-1]-num[i]);}}int sum=upFloor*6+downFloor*4+5*n;printf("%dn",sum);return 0;
}

语法：（1）开始时，逻辑正确却输出不了任何结果，后来发现时scanf的时候没写&；

47. 数列片段和（1104）

这题从思路上的不难，只要发现第i个数据（设下标从1-n）,一共出现了i轮，每轮出现n-i+1次即可计算。但这题引发了很多关于精度问题的思考，非常有价值。

先贴一位博主的链接知乎 - 安全中心

可以看到，后面两个测试点出错的原因是由于double的不连续性和不精确性引起的，这样在N很大，多次乘法后误差会放大，引起差距。

解决办法有两种，

（1）是把sum定义为long long类型，计算过程中先把输入数据放大1000倍，转化为long long型，最后输出时在把sum/1000。

（2）是把sum定义为Long double类型，但我使用这种方法时却发现还是过不了最后两个测试点。检查后发现是sum+=(n-i+1)*i*tmp;出了问题，这里涉及double和两个int类型相乘的问题。如果先让int*int，那么在输入10^5级别的数据时，数量级达到10^10>2^31，就会发生溢出，因此应该把double放在前面，或者转化为Long long类型再与double相乘。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;int main() {int n;double tmp;long double sum=0;scanf("%d", &n);for(int i=1;i<=n;i++){scanf("%lf", &tmp);sum+=tmp*(n-i+1)*i;//或者sum+=((LL)(n-i+1)*i*tmp);//sum+=(n-i+1)*i*tmp;会发生int溢出}printf("%.2Lfn",sum);return 0;
}

语法：（1）Long double 在PAT上读入和输出时使用Lf占位符

48. 计算1的数量（1049）

本题的代码非常简洁，难点就在于如何正确地理清1的数量。参考答案后，正确地计算方法是关注每一位1出现的次数，然后累加起来。进一步发现，计算每位出现1的次数还需分3种情况：

（1）本位now是0，则本位出现1的次数为，left*10^now(now在这里指代从右往左数，从0开始的位数）。如1205，十位上出现1的次数12*10=120次（即0010，0101,0012，。。。1110,1111，。。。）。

（2）本位now是1，则本位出现1的次数为，left*10^now +right+1，如1205，0-999时，千位上都是0，所以Left=0，1000-1205千位出现206个1，所以rifht+1=206。

（3）本位Now>=2，则出现1次数为(left+1)*10^now，如1205中百位是2，其出现次数为200次。即：0100,0101,0102，。。。1100,1101,1102.。。。1199。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;int main(){int n,a=1,ans=0;scanf("%d",&n);//now表示当前位，left/right表示当前位左边、右边数字，int left,now,right;while(n>=a){left = n/(a*10);now = n/a % 10;//n/a即为left加一个当前位，再%10即可取得right = n%a;if(now==0) ans += left*a;else if(now==1) ans += left*a+right+1;else ans += (left+1)*a;a*=10;}printf("%d",ans);return 0;
}

实际上这种方法可以拓展到任意数字的出现次数计算。如5的出现次数。

（1）本位now是<=4，则本位出现5的次数为，left*10^now(now在这里指代从右往左数，从0开始的位数）。如1245，十位上出现5的次数12*10=120次（即0050，0051,0052，。。。1150,1151，。。。）。

（2）本位now是5，则本位出现1的次数为，left*10^now +right+1，如5421，0-4999时，千位上都不是5，所以Left=0，5000-5421千位出现422个1，所以rifht+1=422。

（3）本位Now>=6，则出现1次数为(left+1)*10^now，如1705中百位是2，百位出现5次数为200次。即：0500,0501,0502，。。。1500,1501,1502.。。。1599。

48. 有理和（1081）

本题虽然比较简单，但让我们应用了分数相加、分数化简、分数输出、辗转相除法等的写法。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;struct Fraction{LL up,down;//分子，分母 
}frac[110];LL gcd(LL a,LL b){//辗转相除法求最大公因子if(b==0) return a;//0和a最大公因子为aelse return gcd(b,a%b);
}Fraction reduction(Fraction f){//分数化简if(f.down<0){//若分母为负数，分子分母变为相反数，便于统一处理f.up = -f.up;f.down = -f.down;}if(f.up==0){//若分子为0，令分母=1f.down = 1;}else{int d=gcd(abs(f.up),abs(f.down));//求分子分母最大公约数f.up/=d;f.down/=d;}return f;
}void showFraction(Fraction f){//分数的输出//由于分数相加时已经约分过了，这里不再处理if(f.down == 1) printf("%lldn",f.up);//分母为1，直接输出分子else if(abs(f.up) > f.down){//假分数printf("%lld %lld/%lldn",f.up/f.down,abs(f.up)%f.down,f.down);}else{printf("%lld/%lldn",f.up,f.down);}
}Fraction add(Fraction f1,Fraction f2){//分数相加Fraction sum;sum.up = f1.up*f2.down + f2.up*f1.down;sum.down = f1.down*f2.down;        return reduction(sum);
}int main(){int n;scanf("%d",&n);Fraction sum={0,1};for(int i=0;i<n;i++){scanf("%lld/%lld",&frac[i].up,&frac[i].down); sum = add(sum,frac[i]);}showFraction(sum);return 0;
}