PTA甲级刷题记录——算法初步题解，方便自己复盘
1010 Radix (25分)（二分）
题目大意：
输入四个整数N1，N2，tag，radix。其中tag1表示N1为radix进制数，tag2表示N2为radix进制数。范围：N1和N2均不超过10个数位，且每个数位均为0～9或a～z，其中0～9表示数字，a～z表示数字10～35.
求N1和N2中未知进制的那个数是否存在，并满足某个进制时和另一个数在十进制下相等的条件。若存在，则输出满足条件的最小进制，否则，输出Impossible
- 将已经确定进制的数放在N1，未确定进制的数放在N2，以便在后面进行统一的计算。
- 将N1转化为十进制，使用long long类型来存储。考虑对一个字符串来说，它的进制越大，将该数字串转化为十进制的结果也就越大，因此就可以使用二分法。二分N2的进制，将N2从该进制转化为十进制，令其与N1的十进制比较：如果大于N1的十进制，说明N2的当前进制太大，应该往左子区间继续二分；如果小于N2的十进制，说明N2的当前进制太小，应往右子区间继续二分，当二分结束时即可判断解是否存在。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
typedef long long LL;
map<char, int> Map;
LL inf = 9223372036854775807 ;
LL convertNum10(string a,LL radix,LL t)
{
LL ans = 0;
for(int i = 0 ; i<a.length() ; i++)
{
ans = ans * radix +Map[a[i]];
if(ans<0 || ans >t) return -1;
}
return ans;
}
int cmp(string n2,LL radix,LL t )
{
LL num = convertNum10(n2, radix, t);
if(num < 0) return 1;
if(t>num)
{
return -1;
}
else if(t== num)
{
return 0;
}
else
{
return 1;
}
}
LL binarySearcj(string n2 ,LL left,LL right ,LL t)
{
LL mid;
while(left <= right)
{
mid = (right+left)/2;
int flag = cmp(n2, mid, t);
if(flag == 0)
{
return mid;
}
else if(flag == -1)
{
left = mid+1;
}
else
{
right = mid-1;
}
}
return -1;
}
LL findLargestDigit(string n2)
{
LL ans = -1;
for(int i = 0 ; i<n2.length() ; i++)
{
if(Map[n2[i]] >ans)
{
ans = Map[n2[i]];
}
}
return ans +1;
}
string N1,N2, temp;
int tag,radix;
int main(int argc, const char * argv[]) {
for(char c = '0' ; c <= '9' ; c++)
{
Map[c] = c-'0';
}
for(char c = 'a' ; c <= 'z' ; c++)
{
Map[c] = c-'a' +10;
}
cin>>N1;
cin>>N2;
cin>>tag;
cin>>radix;
if(tag == 2)
{
temp = N1;
N1 = N2;
N2 = temp;
}
LL t = convertNum10(N1, radix, inf);
LL low = findLargestDigit(N2);
LL high = max(low,t) +1;
LL ans = binarySearcj(N2, low, high, t);
if(ans == -1) printf("Impossible\n");
else
{
printf("%lld\n" ,ans);
}
return 0;
}
|
1012 The Best Rank (25分)（排序）
题目大意：
已知n个考生的3门课分数C,M,E，而平均分数A可以由这3个分数得到。现在分别按这4个分数对n个考生从高到低排序，对每个考生来说，会有四个排名，且每个分数都会有一个排名。接下来会有m个查询，每个查询输入一个考生的ID，输出该考生4个排名中最高的那个排名以及对应是A，C，M，E中的哪一个。如果不同课程排名相同，则按优先级A>C>M>E输出；如果查询的考生ID不存在，则输出N/A。
思路：
（1）用map<int,vector>存储Ranks的值，key为id，value为每一个成绩的排名，顺序为A>C>M>E
（2）结构体Students存放id和四个分数，顺序为A>C>M>E
（3）读入考生id和三个分数，计算平均分（这里我们计算平均分，直击算了总分，因为平均分和总分排序是相同的）
（4）然后用自带的sort函数对每一个成绩进行排序，now为当前正在计算的成绩，然后将序列存入Ranks
（5）查询时根据query从Ranks中取出对应的value，输出，如果Ranks.count(query) ==0 说明这个query不存在，输出N/A.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
#include <vector>
using namespace std;
struct Student{
int id;
int grade[4];
Student(int s,int a,int c,int m,int e )
{
id =s;
grade[0] = a;
grade[1] = c;
grade[2] = m;
grade[3] = e;
}
};
vector<Student> students;
int now = 0;
bool cmp(Student a,Student b)
{
return a.grade[now] >b.grade[now];
}
int main(int argc, const char * argv[]) {
int n,m;
scanf("%d %d",&n,&m);
int s;
int c,math,e;
map<int,char> course;
course[0] = 'A';
course[1] = 'C';
course[2] = 'M';
course[3] = 'E';
map<int,vector<int>> Ranks;
for(int i = 0 ; i< n ; i++)
{
scanf("%d%d%d%d",&s,&c,&math,&e);
int avg = c+math+e;
students.push_back(Student(s,avg,c,math,e));
vector<int> temp;
temp.push_back(0);
temp.push_back(0);
temp.push_back(0);
temp.push_back(0);
Ranks[s] = temp;
}
for( now = 0 ; now <4 ; now++)
{
sort(students.begin(), students.end(), cmp);
Ranks[students[0].id][now] = 1;
for(int i = 1; i< n ; i++)
{
if(students[i].grade[now] == students[i-1].grade[now])
{
Ranks[students[i].id][now] = Ranks[students[i-1].id][now];
}else
{
Ranks[students[i].id][now] =i+1;
}
}
}
int query ;
for(int i = 0 ; i< m ; i++)
{
scanf("%d",&query);
if(Ranks.count(query) <=0)
{
printf("N/A\n");
}
else
{
int k = 0 ;
for(int j = 0 ; j< 4 ; j++)
{
if(Ranks[query][j] <Ranks[query][k])
{
k = j;
}
}
printf("%d %c\n",Ranks[query][k],course[k]);
}
}
return 0;
}
|
