PAT乙级学习笔记（二）
##续接PAT乙级学习笔记（一）
##以下PAT乙级模拟题
1.B1053住房空置率。注意变量的命名方式，更加有助于解题和找bug。注意题目中输出一位小数点百分数的方式，（double）强制类型转换。
double mayvoid1=(double)mayvoid/n*100;
double isvoid1=(double)isvoid/n*100;
printf("%.1f%% %.1f%%",mayvoid1,isvoid1);
使用%%来输出一个%。使用\来输出一个,对于其他的转义字符需要\来输出，如printf(“\n”）将输出一个\n。
2.B1051复数乘法。当A或B在-0.005到+0.005之间时候，应该输出0.00而不应该输出-0.00，所以在输出的时候需要有一步判断。
3.B1050螺旋矩阵。这道题的思路不是很明确，不知道怎么样输出螺旋矩阵，所以做不出来。柳神给出来的思路很明确，需要借鉴参考学习。
4.B1046划拳。比较简单的一道题，5分钟就搞定了，注意书写变量的命名。
5.B1026程序运行时间。认真体会四舍五入时加上50的写法。注意当其中一项是0的时候应该输出00所以输出格式应该是%02d。输出控制符%.mf是保障精确到小数点后面几位，不是四舍五入，四舍五入应该用round（double）函数。
6.B1018锤子剪子布。题目较简单，注意变量命名的方式，一定要让自己能够看懂。对于每一个人胜利的存储可以参考柳神的方式，用数组，然后找出最大的下标。很巧妙。
int maxjia = jia[0] >= jia[1] ? 0 : 1;
maxjia = jia[maxjia] >= jia[2] ? maxjia : 2;
int maxyi = yi[0] >= yi[1] ? 0 : 1;
maxyi = yi[maxyi] >= yi[2] ? maxyi : 2;
char str[4] = {"BCJ"};
cout << str[maxjia] << " " << str[maxyi];
7.B1016部分A+B。题目较简单，认为书写函数的方式要好于柳神的方法，代码也比较短。
##以下PAT乙级数学题
1.B1056组合数的和。本题每个输入的数，相当于被加了N-1次，所以可以使用柳神的方式sum += temp * 10 * (N - 1) + temp * (N - 1);当然考场上如果想不起来，也可以使用两层for循环来写，也非常简单。
2.1049数列的片段和。编程不难，数学思想比较难想到，可以通过画图找规律，每一个数实际上都是被加了（n-i）*（n+1）次，通过在纸上演算可以得到。也可以参考柳神的代码用双指针的思想考虑，每个片段的头指针有i种选择，每个尾指针有n-1-i种选择。
3.B1019数字黑洞。这是一道做过的题，注意输入可能不是4位数，计算的过程中可能不是4位数，所以需要两次判断。s.insert(0,4-s.length(),'0');这种插入的用法必须学会。另外当输入为6174的时候也需要进行循环，所以需要使用do语句，不能使用while语句。
##以下是PAT乙级HASH散列问题
1.B1083是否存在相等的数。将相减的数直接作为数组的下标记录个数就行，相对较简单。
2.B1047编程团体赛。本题注意柳神的scanf的应用，比我的方法简单太多了。scanf("%d-%d %d", &t, &num, &score);我是采用读取字符串，然后判断的方法，简直蠢透了。附上我的代码
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
int main(){
int n,sum[1001]={0};
int maxnum,maxscore=0;
string s;
cin>>n;
getchar();
for(int i=0;i<n;i++){
int com,score=0;
getline(cin,s);
for(int j=0;j<s.length();j++){
if(s[j]=='-'){
com=stoi(s.substr(0,j));
}
if(s[j]==' '){
score=stoi(s.substr(j+1));
}
}
sum[com]+=score;
}
for(int i=1;i<=1000;i++){
if(sum[i]>maxscore){
maxscore=sum[i];
maxnum=i;
}
}
cout<<maxnum<<" "<<maxscore;
return 0;
}
附上柳神的代码：
#include <iostream>
using namespace std;
int main() {
int n, t, num, score;
cin >> n;
int team[1001] = {0};
for (int i = 1; i <= n; i++) {
scanf("%d-%d %d", &t, &num, &score);
team[t] += score;
}
int max = 0;
for (int i = 0; i < 1001; i++) {
if (team[max] < team[i])
max = i;
}
cout << max << " " << team[max];
return 0;
}
3.B1043输出PATest。我的思路是遍历每一个字符，然后如果字符是P就把他放在字符数组的第1个位置，对于下一个P就把它放在第七个位置，但是代码能力太弱，写出来的漏洞百出。以下附上柳神的代码以供学习：
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
int main(){
int map[128]={0},c;\\一共128个ascii码。
while((c=cin.get())!=EOF) map[c]++;
while (map['P'] > 0 || map['A'] > 0 || map['T'] > 0 || map['e'] > 0 ||map['s'] > 0 || map['t'] > 0) {
if (map['P']-- > 0) cout << 'P';
if (map['A']-- > 0) cout << 'A';
if (map['T']-- > 0) cout << 'T';
if (map['e']-- > 0) cout << 'e';
if (map['s']-- > 0) cout << 's';
if (map['t']-- > 0) cout << 't';
}
return 0;
}
4.B1042字符统计。所有变量如果不直接输入都要初始化，这道题如果不初始化t，就会导致测试点2不通过。对于单个字符的hash散列可以使用它的ascii码作为键值。当要求有并列的时候从最小的输出时候，可以从遍历字母的最小的ascii开始。
5.B1039到底买不买。每一个珠子个数都存成a[s[i]-‘0’]的形式，a[]里面对应的不一定是这个字符的ascii码，不过不会影响最后的结果，不过像下面这样也是可以的s[i]默认选取其ascii码。柳神的代码采用了两个for循环，不易想到。
string s1,s2;
cin>>s1>>s2;
for(int i=0;i<s2.length();i++){
b[s2[i]]++;
}
6.B1038统计同成绩的学生的个数。相对简单，柳神的代码中使用了vector容器，我是用了数组保存成绩，注意数组的范围是a[101]。
7.B1033旧键盘打印。题目较难，可以参考柳神的代码，尤其注意string：：npos的用法，《算法笔记》p207有详细解释：
#include<iostream>
#include <string>
#include<cctype>
#include <map>
using namespace std;
int main(){
string bad,should;
getline(cin,bad);
getline(cin,should);
for(int i=0;i<should.length();i++){
if(bad.find(toupper(should[i]))!=string::npos) continue;
if(isupper(should[i])&&bad.find('+')!=string::npos) continue;
cout<<should[i];
}
return 0;
}
8.B1029旧键盘。学会了柳神的find函数，对于判断字母还是大小写处理的还不是很好。
#include<iostream>
#include <string>
#include<cctype>
#include <map>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int a[128]={0};
for(int i=0;i<s1.length();i++){
if(s2.find(s1[i])==string::npos&&a[s1[i]]==0){
if(!isalpha(s1[i])){
a[s1[i]]++;
cout<<s1[i];
}else{
if(islower(s1[i])){
a[s1[i]-32]++;
a[s1[i]]++;
s1[i]=toupper(s1[i]);
cout<<s1[i];
}
else{
a[s1[i]+32]++;
a[s1[i]]++;
cout<<s1[i];
}
}
}
}
return 0;
}
柳神的代码采用字符串相加的方式,真是妙！
#include <iostream>
#include <cctype>
using namespace std;
int main() {
string s1, s2, ans;
cin >> s1 >> s2;
for (int i = 0; i < s1.length(); i++)
if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) ==string::npos)
ans += toupper(s1[i]);
cout << ans;
return 0;
}
##以下是PAT乙级STL-map题：
1.B1090危险品装箱。这道题比较难，参考了柳神的代码：
#include<iostream>
#include <string>
#include<cctype>
#include<map>
#include<vector>
using namespace std;
int main(){
int n,k,t1,t2;
map<int,vector<int> > m;//每个数关联的数不是确定个，所以使用vector
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d%d",&t1,&t2);
m[t1].push_back(t2);
m[t2].push_back(t1);
}
while(k--){
int cnt,flag=0,a[100000]={0};
scanf("%d",&cnt);
vector<int> v(cnt);
for(int i=0;i<cnt;i++){
scanf("%d",&v[i]);
a[v[i]]=1;//将每一个数都设置为1，散列
}
for(int i=0;i<v.size();i++)//从输入的第一个数开始遍历
for(int j=0;j<m[v[i]].size();j++)//从每个数关联的数开始遍历
if(a[m[v[i]][j]]==1) flag=1;
//m[v[i][j]]表示关联的第j个数，a[]表示关联的数存在
printf("%s\n",flag ? "No" : "Yes");
}
return 0;
}
2.B1085PAT单位排行。题目不会做，参考了柳神的代码。注意写代码的时候的代码风格，变量和运算符之间需要加空格，结束符，逗号等要靠在前面的变量。scanf（“%lf”，&a）中间是字母l不是数字1.
#include<iostream>
#include<algorithm>
#include<cctype>
#include<vector>
#include<unordered_map>
using namespace std;
struct node{
string school;
int tws,ns;
};
bool cmp(node a,node b){
if(a.tws!=b.tws)
return a.tws>b.tws;
else if(a.ns!=b.ns)
return a.ns<b.ns;
else
return a.school<b.school;
}
int main() {
int n;
scanf("%d", &n);
unordered_map<string, int> cnt;
unordered_map<string, double> sum;
for(int i = 0;i < n; i++){
string id,school;
cin>>id;
double score;
scanf("%lf",&score);
cin>>school;
for(int j=0;j<school.length();j++)
school[j]=tolower(school[j]);
if(id[0]=='B')
score=score/1.5;
else if(id[0]=='T')
score=score*1.5;
sum[school]+=score;
cnt[school]++;
}
//下面是本题的重点
vector<node> ans;
for(auto it=cnt.begin();it!=cnt.end();it++)
ans.push_back(node{it->first,(int)sum[it->first],cnt[it->first]});
sort(ans.begin(),ans.end(),cmp);
int rank=0,pres=-1;
printf("%d\n",(int)ans.size());
for(int i=0;i<ans.size();i++){
if(pres!=ans[i].tws) rank=i+1;
pres=ans[i].tws;
printf("%d ",rank);
cout<<ans[i].school;
printf(" %d %d\n",ans[i].tws,ans[i].ns);
}
return 0;
}
3.B1080MOOC期中成绩。这道题和B1085很像，都使用了结构体，自己书写sort的cmp函数，我没做出来，参考的柳神的代码
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
struct node{
string name;
int gp, gm, gf, g;
};
bool cmp(node a, node b){
return a.g != b.g ? a.g > b.g : a.name < b.name;
}
map<string, int> idx;
int main(){
int p, m, n, score, cnt = 1;
scanf("%d %d %d",&p, &m, &n);
vector<node> v, ans;
string s;
for(int i=0;i<p;i++){
cin >> s >> score;
if(score>=200) {
v.push_back(node{s, score, -1, -1, 0});
idx[s] = cnt++;//起到标记的作用
}
}
for(int i=0; i<m; i++){
cin >> s >> score;
if(idx[s] != 0) v[idx[s] - 1].gm = score;
}
for(int i=0; i<n; i++){
cin >> s >> score;
if(idx[s]!= 0){
int temp = idx[s] - 1;
v[temp].gf = v[temp].g = score;
if(v[temp].gm > v[temp].gf)
v[temp].g = int(v[temp].gm*0.4 + v[temp].gf*0.6 + 0.5);
}
}
for(int i = 0; i < v.size(); i++)
if(v[i].g >= 60) ans.push_back(v[i]);
sort(ans.begin(), ans.end(), cmp);
for(int i = 0; i < ans.size();i++)
printf("%s %d %d %d %d\n",ans[i].name.c_str(), ans[i].gp, ans[i].gm, ans[i].gf, ans[i].g);
return 0;
}
注意输出时，因为名字使用的%s格式，所以输出的时候需要把.name的string格式变为.name.c_str格式，这一点需要注意。
4.B1069微博转发抽奖。本道题自己做出来了，但是思维逻辑有点混乱，参考了柳神的代码。用来做标记的flag可以设置成bool类型false，true。
5.B1063火星数字。参考了柳神的代码，柳神的代码书写真的很规范！
#include <iostream>
#include <string>
using namespace std;
string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string b[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
string s;
int len;
void func1(int t) {
if (t / 13) cout << b[t / 13];
if ((t / 13) && (t % 13)) cout << " ";
if (t % 13 || t == 0) cout << a[t % 13];
}
void func2() {
int t1 = 0, t2 = 0;
string s1 = s.substr(0, 3), s2;
if (len > 4) s2 = s.substr(4, 3);
for (int j = 1; j <= 12; j++) {
if (s1 == a[j] || s2 == a[j]) t2 = j;
if (s1 == b[j]) t1 = j;
}
cout << t1 * 13 + t2;
}
int main() {
int n;
cin >> n;
getchar();
for (int i = 0; i < n; i++) {
getline(cin, s);
len = s.length();
if (s[0] >= '0' && s[0] <= '9')
func1(stoi(s));
else
func2();
cout << endl;
}
return 0;
}
注意以下的代码风格的规范
void fun1(int x, int y, int z);//良好
void fun1 (int x,int y,int z); //不良好
if (year >= 200) //良好
if(year>=200) //不良好
if ((a>=b) && (a<=d)) //良好
if(a>=b&&a<=d) //不良好
for (i=0; i<10; i++) //良好风格
for(i=0;i<10;i++) //不良好风格
for (i = 0; i < 10; i++) //过多的空格
x = a < b ? a : b; //良好
x=a<b?a:b; //不良好
int *x=&b; //良好
int * x=& b; //不良好
6.B1065单身狗。一定要注意“=”和“==”的区别，出现bug第一时间检查是不是这个出问题了！！！写代码的时候可以开大数组，少用STL等，会导致超时！！当输出有0的时候一定要注意输出格式！！这道题自己一点点的做出来了，用了两个多小时：下面是代码
#include<iostream>
#include<unordered_map>
#include<set>
using namespace std;
int sign[100000];
int a[100000]={-1};
int b[100000]={-1};
int main(){
int n, m;
cin >> n;
set<int> ans;
for(int i = 0; i < n; i++){
int id1, id2;
scanf("%d %d",&id1,&id2);
a[id1] = id2;
b[id2] = id1;
}
cin >> m;
int c[m];
for(int i = 0; i < m; i++){
scanf("%d",&c[i]);
if(a[c[i]] == -1 && b[c[i]] == -1) ans.insert(c[i]);//说明是单身来了聚会
else sign[c[i]] = 1;//说明不是单身，但是他的另一半有没有来聚会，需要下面判断
}
for(int i = 0; i < m; i++){//判断不是单身的这些人，另一半来没来
if(sign[c[i]] == 1){
int flag1 = 0;
for(int j = 0; j < m; j++){
if(a[c[i]] == c[j] || b[c[i]] == c[j]) flag1 = 1;
}
if(flag1 == 0) ans.insert(c[i]);
}
}
//将单身的按照顺序输出，注意输出空格的方法
cout << ans.size() << endl;
int space = ans.size();
for(auto it = ans.begin(); it != ans.end(); it++){
printf("%05d",*it);
if(space-- > 1) printf(" ");
}
return 0;
}
7.B1064朋友数。这道题比较简单，注意后面输出空格的方法。另外，stoi只能作用于字符串。