2022.3.5 PAT甲级 2022年春季考试 89分
7-1 Simple Lie Detection (20 分)
简单字符串问题，注意连续相同子段和连续上升子段的细节。
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
int n,t,k;
string s;
cin>>n>>t>>k;
while(k--)
{
cin>>s;
int len=s.length();
int ans=0;
if(s[0]=='f')
ans-=2;
if(s[len-1]=='a')
ans-=1;
int f;
f=s.find("aaaaaa");
if(f!=-1) ans+=3;
f=s.find("bbbbbb");
if(f!=-1) ans+=3;
f=s.find("cccccc");
if(f!=-1) ans+=3;
f=s.find("dddddd");
if(f!=-1) ans+=3;
f=s.find("eeeeee");
if(f!=-1) ans+=3;
f=s.find("ffffff");
if(f!=-1) ans+=3;
f=s.find("gggggg");
if(f!=-1) ans+=3;
f=s.find("hhhhhh");
if(f!=-1) ans+=3;
for(int i=0;i<len-1;i++)
if(s[i]=='a')
if(s[i+1]=='e'||s[i+1]=='h')
ans-=4;
for(int i=0;i<len-3;)
{
int temp=1;
for(int j=i+1;j<len;j++)
{
if(s[j]==s[j-1]+1)
temp++;
else
break;
}
if(temp>3) ans+=5;
i+=temp;
}
cout<<ans;
if(ans>t)
cout<<"!!!";
cout<<endl;
}
return 0;
}
7-2 The First K Largest Numbers (25 分)
这道题空间限制有点严格，如果用C++，只能用优先队列（或者类似方式），而且注意应该是小端优先队列，队列内其实只需要保留5个数，每次加入一个数，就将最小的删去，最后剩下最大的5个数，输出k个数即可。
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int a[10];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k,t;
cin>>n>>k;
if(k>n) k=n;
if(n<=5)
{
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
reverse(a,a+n);
cout<<a[0];
for(int i=1;i<k;i++)
cout<<" "<<a[i];
}
else
{
priority_queue<int,vector<int>,greater<int>> q;
for(int i=0;i<5;i++)
{
cin>>t;
q.push(t);
}
for(int i=5;i<n;i++)
{
cin>>t;
q.push(t);
q.pop();
}
for(int i=4;i>=0;i--)
{
a[i]=q.top();
q.pop();
}
cout<<a[0];
for(int i=1;i<k;i++)
cout<<" "<<a[i];
}
return 0;
}
7-3 Is It A Binary Search Tree – Again (25 分)
二叉查找树判断，并输出中序遍历，简单递归即可。判断是否为二叉查找树，只需要看中序遍历是否是递增的就行，并不需要另外对每个结点进行判断了。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,tree[1005],flag=1;
vector<int> v;
void inorder(int temp)
{
if(temp>n) return;
//if(2*temp<=n&&tree[2*temp]!=-1&&tree[2*temp]>tree[temp])
// flag=0;
//if(2*temp+1<=n&&tree[2*temp+1]!=-1&&tree[2*temp+1]<tree[temp])
// flag=0;
inorder(2*temp);
if(tree[temp]!=-1)
v.emplace_back(tree[temp]);
inorder(2*temp+1);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>tree[i];
inorder(1);
for(int i=1;i<v.size();i++)
if(v[i]<v[i-1])
flag=0;
if(flag==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
cout<<v[0];
for(int i=1;i<v.size();i++)
cout<<" "<<v[i];
return 0;
}
7-4 The Rescue (30 分)
这其实是一道BFS题，但题目相对比较复杂，到考试后半阶段，还没有几个人提交代码，最后满分的也只有个位数。
面对复杂问题，我们可以通过提交，将n和m较小的样例0、1、2的情况测出来，在《算法笔记》附录里面有提到这种方法，然后手工计算即可。
样例3情况较为复杂，虽然不包含“#”符号，但通过找规律还是很难得出结论。由于一开始想着骗分，最后来不及写BFS了，混了19分。
#include <iostream>
#include <cstdio>
using namespace std;
char g[105][105];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
if(n==3&&m==3)
{
if(g[3][2]=='X')//样例2
{
cout<<"1223"<<endl;
}
if(g[3][3]=='X')//样例1
{
cout<<"1122"<<endl;
}
}
else if(n==5||m==5)
{
if(g[2][3]=='X')//样例0
{
cout<<"00011300121133"<<endl;
}
}
else//样例345
{
if(n==99&&m==99&&g[50][50]=='X')//样例4
{
for(int i=49;i>=2;i--)
{
for(int j=1;j<=i;j++)
cout<<"0";
for(int j=1;j<=i;j++)
cout<<"1";
for(int j=1;j<=i;j++)
cout<<"2";
for(int j=1;j<=i;j++)
cout<<"3";
for(int j=1;j<=i-1;j++)
cout<<"0";
for(int j=1;j<=i-1;j++)
cout<<"1";
cout<<"0";
for(int j=1;j<=i-1;j++)
cout<<"3";
for(int j=1;j<=i-1;j++)
cout<<"1";
for(int j=1;j<=i-1;j++)
cout<<"2";
}
cout<<"0"<<endl;
}
}
return 0;
}
前三题主要考察编程基本功，基础数据结构，没什么难度，有一些细节需要注意。这次的第四题确实相比之前有些复杂，能完全AC的代码量估计也要达到200行了，在考场上很难一下子就写正确。
第二次考PAT甲级，虽然现在可能没有机试了，但还是可以通过考试来多练练手。上次考了满分，这次题目略难，最后拿了89分，排名20多，总体还算满意啦。