1. 知识总结
2h内结束，感觉最后考试肯定没这么简单。
100/100，也是比较简单的一套题目，主要是第二题稍微麻烦一点（阅读理解和代码量）
2. 分题题解
2.1 PAT 1152 Google Recruitment
基本的字符串操作加上数学
感觉第一题很喜欢考这种的，数学的话素数判断考得尤其多
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int x){
if(x<=1)return false;
if(x==2||x==3||x==5||x==7||x==11){
return true;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
int L,K;
string str;
int main(){
scanf("%d%d",&L,&K);
cin>>str;
for(int i=0;i<L-K+1;i++){
string temp=str.substr(i,K);
int num=stoi(temp);
if(isPrime(num)){
printf("%s\n",temp.c_str());
return 0;
}
}
printf("404");
return 0;
}
2.2 PAT 1153 Decode Registration Card of PAT
STL的用法以及英文水平的考察
题目和代码量都略长，所以……耐心细心最重要
没怎么卡时间和空间
#include<bits/stdc++.h>
using namespace std;
int N,M;
string id;
int score;
struct Student{
string id;
int level;
int test_site;
int test_date;
int test_id;
int score;
};
vector<Student>stu;
bool cmp1(Student a,Student b){
if(a.level!=b.level){
return a.level<b.level;
}else if(a.score!=b.score){
return a.score>b.score;
}else{
return a.id<b.id;
}
}
struct Ans3{
int site;
int Nt;
};
bool cmp3(Ans3 a,Ans3 b){
if(a.Nt!=b.Nt){
return a.Nt>b.Nt;
}else{
return a.site<b.site;
}
}
int type;
string term;
int cntA=0,cntB=0,cntT=0;
int main(){
scanf("%d%d",&N,&M);
stu.resize(N);
for(int i=0;i<N;i++){
cin>>id>>score;
stu[i].id=id;
stu[i].score=score;
if(id[0]=='T'){
stu[i].level=3;
cntT++;
}else if(id[0]=='A'){
stu[i].level=2;
cntA++;
}else{
stu[i].level=1;
cntB++;
}
stu[i].test_site=stoi(id.substr(1,3));
stu[i].test_date=stoi(id.substr(4,6));
stu[i].test_id=stoi(id.substr(10,3));
}
sort(stu.begin(),stu.end(),cmp1);
for(int k=0;k<M;k++){
cin>>type>>term;
printf("Case %d: %d %s\n",k+1,type,term.c_str());
if(type==1){
if((term=="A"&&cntA==0)||(term=="T"&&cntT==0)||(term=="B"&&cntB==0)){
printf("NA\n");
continue;
}
int l,r;
if(term=="B"){
l=0;r=l+cntB;
}else if(term=="A"){
l=cntB;r=l+cntA;
}else{
l=cntB+cntA;
r=N;
}
for(int i=l;i<r;i++){
printf("%s %d\n",stu[i].id.c_str(),stu[i].score);
}
}else if(type==2){
int Nt=0,Ns=0;
int site=stoi(term);
for(int i=0;i<N;i++){
if(stu[i].test_site==site){
Nt++;
Ns+=stu[i].score;
}
}
if(Nt==0){
printf("NA\n");
}else{
printf("%d %d\n",Nt,Ns);
}
}else{
int date=stoi(term);
map<int,int>mp;
for(int i=0;i<N;i++){
if(stu[i].test_date==date){
if(mp.find(stu[i].test_site)!=mp.end()){
mp[stu[i].test_site]++;
}else{
mp[stu[i].test_site]=1;
}
}
}
if(mp.size()==0){
printf("NA\n");
}else{
vector<Ans3>ans3;
Ans3 ans;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
ans.site=it->first;
ans.Nt=it->second;
ans3.push_back(ans);
}
sort(ans3.begin(),ans3.end(),cmp3);
for(int i=0;i<ans3.size();i++){
printf("%03d %d\n",ans3[i].site,ans3[i].Nt);
}
ans3.clear();
}
}
}
return 0;
}
2.3 PAT 1154 Vertex Coloring
简单的图论，经典题目改编，判断的条件是相邻两个点是否同色，其实构建图的话，单边图就够了（代码构造的是双边图，可以纠正一下），没卡时间所以AC容易
#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<vector<int>>graph;
vector<int>color;
int total;
set<int>col;
int u,v;
int K;
bool isKcolor(){
set<int>temp;
for(int i=0;i<N;i++){
for(int j=0;j<graph[i].size();j++){
if(color[i]==color[graph[i][j]]){
return false;
}
}
}
return true;
}
int main(){
scanf("%d%d",&N,&M);
graph.resize(N);
color.resize(N);
for(int i=0;i<M;i++){
scanf("%d%d",&u,&v);
graph[u].push_back(v);
graph[v].push_back(u);
}
scanf("%d",&K);
for(int i=0;i<K;i++){
for(int j=0;j<N;j++){
scanf("%d",&color[j]);
col.insert(color[j]);
}
total=col.size();
if(isKcolor()){
printf("%d-coloring\n",total);
}else{
printf("No\n");
}
col.clear();
}
return 0;
}
2.4 PAT 1155 Heap Paths
这题和堆关联,不涉及堆的相关操作，主要是借助堆的数组的特性去解题，主要算法是DFS
堆的特性：对于大顶堆而言
v
[
i
n
d
e
x
]
>
v
[
2
?
(
i
n
d
e
x
+
1
)
?
1
]
v[index]>v[2*(index+1)-1]
v[index]>v[2?(index+1)?1]且
v
[
i
n
d
e
x
]
>
v
[
2
?
(
i
n
d
e
x
+
1
)
]
v[index]>v[2*(index+1)]
v[index]>v[2?(index+1)]
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>v;
vector<int>temp;
int type=0;
void getVec(int index,vector<int>path){
path.push_back(v[index]);
bool can_next=false;
if((index+1)*2<N){
getVec((index+1)*2,path);
can_next=true;
}
if((index+1)*2-1<N){
getVec((index+1)*2-1,path);
can_next=true;
}
if(!can_next){
for(int i=0;i<path.size();i++){
if(i){
printf(" ");
if(type==1){
if(path[i-1]>path[i]){
type=0;
}
}else if(type==2){
if(path[i-1]<path[i]){
type=0;
}
}
}
printf("%d",path[i]);
}
printf("\n");
}
}
int main(){
scanf("%d",&N);
v.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&v[i]);
}
if(v[0]>v[1])type=2;
else if(v[0]<v[1])type=1;
getVec(0,temp);
if(type==1){
printf("Min Heap");
}else if(type==2){
printf("Max Heap");
}else{
printf("Not Heap");
}
return 0;
}
3. 参考资料
无
|