PAT乙级学习笔记（四）
##续接PAT乙级学习笔记（三）
##以下PAT乙级其它题目
1.B1062最简分数。分数比较的时候可以使用交叉相乘的方法，不要想着使用double类型得到分数的小数形式比较大小。学会使用gcd求最大公倍数的递归写法，当成模板记住。数组定义的时候尽量初始化，不然按照判断数组的数是否为0就会出现错误。以下是代码
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b){
if(b == 0) return a;
else return gcd(b, a % b);
}
int main(){
int n1, m1, n2, m2, k;
scanf("%d/%d %d/%d %d",&n1, &m1, &n2, &m2, &k);
if(n1 * m2 > n2 * m1){
swap(n1, n2);
swap(m1, m2);
}
int a[k] = {0};
int cnt = 0;
for(int i = 1; i < k; i++){
if(n1 * k < m1 * i && i * m2 < k * n2 && gcd(k, i) == 1){
a[i] = i;
cnt++;
}
}
for(int i = 0; i < k; i++){
if(a[i] != 0){
printf("%d/%d",a[i],k);
if(--cnt > 0) cout << " ";
}
}
return 0;
}
注意体会柳神代码中输出空格的写法，相当于第一项不输出空格，其他的每一项都先输出空格再输出数
bool flag = false;
while(n1 * k >= m1 * num) num++;
while(n1 * k < m1 * num && m2 * num < n2 * k) {
if(gcd(num, k) == 1) {
printf("%s%d/%d", flag == true ? " " : "", num, k);
flag = true;
}
num++;
}
2.B1066图像过滤。这道题比较简单，下面是存储到数组中，统一输出的代码
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int m, n, a, b, c;
cin >> m >> n >> a >> b >> c;
int ans[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
scanf("%d", &ans[i][j]) ;
if(ans[i][j] >= a && ans[i][j] <= b){
ans[i][j] = c;
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
printf("%03d", ans[i][j]);
if(j != n -1) cout << " ";
}
cout << endl;
}
return 0;
}
下面是一边处理一边输出的代码
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int m, n, a, b, c;
cin >> m >> n >> a >> b >> c;
int ans[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
scanf("%d", &ans[i][j]) ;
if(ans[i][j] >= a && ans[i][j] <= b){
ans[i][j] = c;
}
printf("%03d", ans[i][j]);
if(j != n -1) cout << " ";
}
cout << endl;
}
return 0;
}
3.B1071小赌怡情。较简单，注意游戏结束后要break退出
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int t0, k;
cin >> t0 >> k;
for(int i = 0; i < k; i++){
int n1, b, t, n2;
cin >> n1 >> b >> t >> n2;
if(t0 == 0){
printf("Game Over.\n");
break;
}
else{
if(t0 < t) printf("Not enough tokens. Total = %d.\n",t0);
else{
if(b == 0 && n2 < n1 || b == 1 && n2 > n1){
t0 = t0 + t;
printf("Win %d! Total = %d.\n",t,t0);
}
else{
t0 = t0 - t;
printf("Lose %d. Total = %d.\n",t,t0);
}
}
}
}
return 0;
}
4.B1072开学寄语。属于简单题，注意变量定义的位置。一定要注意“=”和“==”的区别!!!数组初始化如果全部赋值为0可以直接用={0}来赋值，如果赋值为其他数，需要使用循环或者按照本题目中的做法：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int check[10000] = {0};
int main(){
int n, m, cnt0 = 0, cnt1 = 0;
cin >> n >> m;
for(int i = 0; i < m; i++){
int temp;
cin >> temp;
check[temp] = 1;
}
for(int i = 0; i < n; i++){
string name;
int k,flag = 0;
cin >> name >> k;
int ans[11] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
for(int j = 0; j < k; j++){
int temp1;
cin >> temp1;
if(check[temp1] == 1){
flag =1;
ans[j] = temp1;
cnt1++;
}
}
if(flag == 1){
cnt0++;
bool space = false;
cout << name <<": ";
for(int j = 0; j < k; j++){
if(ans[j] != -1){
if(space == true) cout << " ";
printf("%04d",ans[j]);
space = true;
}
}
cout << endl;
}
}
cout << cnt0 << " " << cnt1;
return 0;
}
柳神的代码不太好理解，这里有一个技巧就是，输出名字后，其实每一个违禁品编号前面都有有个空格。对于输出也是只有第一个前面输出名字，其他的都不输出。
#include <iostream>
#include <algorithm>
using namespace std;
bool forbid[10000];
int main() {
int n, m, temp, k, snum = 0, fnum = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d", &temp);
forbid[temp] = true;
}
for (int i = 0; i < n; i++) {
char name[10];
bool flag = false;
scanf("%s %d", name, &k);
for (int j = 0; j < k; j++) {
scanf("%d", &temp);
if (forbid[temp]) {
if (!flag) {
printf("%s:", name);
flag = true;
}
printf(" %04d", temp);
fnum++;
}
}
if (flag) {
printf("\n");
snum++;
}
}
printf("%d %d\n", snum, fnum);
return 0;
}
5.B1076Wifi密码。这道题相对简单，注意使用scanf以%c的形式是可以读入空格和换行的。使用getline之前必须使用getline来吸收一下。
#include <iostream>
#include <string>
using namespace std;
int main(){
int n;
cin >> n;
getchar();
string s;
for(int i = 0; i < n; i++){
getline(cin, s);
for(int j = 0; j < s.length(); j++){
if(s[j] == '-' && s[j + 1] == 'T'){
cout << s[j - 1] - 'A' + 1;
}
}
}
return 0;
}
注意柳神中while的写法，真的太巧妙了
#include <iostream>
using namespace std;
int main() {
string s;
while (cin >> s)
if(s.size() == 3 && s[2] == 'T') cout << s[0]-'A'+1;
return 0;
}
6.B1077互评成绩。注意变量定义后的作用范围，这道题vector需要定义在数组以内，如果定义在外面出错，相当于每个循环都初始化一次。四舍五入就是要加上0.5后得到整数。
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int main(){
int n, m;
double g1, g2;
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> g1;
vector<int> v;
for(int j = 1; j < n; j++){
int temp;
cin >> temp;
if(temp >= 0 && temp <= m){
v.push_back(temp);
}
}
int sum = 0;
sort(v.begin(),v.end());
for(int i = 1; i < v.size() - 1; i++){
sum += v[i];
}
double g2 = sum / (v.size() - 2) ;
cout << (int)((g1 + g2) / 2 + 0.5) << endl;
}
return 0;
}
7.B1087有多少不同的值。是一道简单题，使用set可以大大减少代码量
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int main(){
int n;
cin >> n;
set<int> st;
for(int i = 0; i <= n; i++){
int temp = (i / 2) + (i / 3) + (i / 5);
st.insert(temp);
}
cout << st.size();
return 0;
}
8.B1020月饼。注意需要按照单价排序，不是按照价格排序。注意是正数还是正正数。需要考虑所有都不满足的情况。下面是代码
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct node{
double total, sumprice,price;
};
bool cmp(node a, node b){
return a.price > b.price;
}
int main(){
int n, d;
cin >> n >> d;
vector <node> v(n);
for(int i = 0; i < n; i++) cin >> v[i].total;
for(int i = 0; i < n; i++) cin >> v[i].sumprice;
for(int i = 0; i < n; i++){
v[i].price = v[i].sumprice * 1.0 / v[i].total;
}
sort(v.begin(),v.end(),cmp);
// for(int i = 0; i < n; i++) cout << v[i].total <<"*"<< v[i].price << endl;
double sum = 0;
int i = 0;
while(d > 0 && i < n){
// cout << v[i].total << v[i].price << endl;
if(d >= v[i].total){
sum += v[i].sumprice;
}
else{
sum += (d * v[i].sumprice * 1.0/ v[i].total);
}
d = d - v[i].total;
i++;
}
int tmp = 0;
for(int i = 0; i < n; i++){
tmp += v[i].sumprice;
}
if(d > tmp) cout << tmp;
else printf("%.2f", sum);
return 0;
}
注意柳神代码中的算法：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct mooncake{
float mount, price, unit;
};
int cmp(mooncake a, mooncake b) {
return a.unit > b.unit;
}
int main() {
int n, need;
cin >> n >> need;
vector<mooncake> a(n);
for (int i = 0; i < n; i++) scanf("%f", &a[i].mount);
for (int i = 0; i < n; i++) scanf("%f", &a[i].price);
for (int i = 0; i < n; i++) a[i].unit = a[i].price / a[i].mount;
sort(a.begin(), a.end(), cmp);
float result = 0.0;
for (int i = 0; i < n; i++) {
if (a[i].mount <= need) {
result = result + a[i].price;
} else {
result = result + a[i].unit * need;
break;
}
need = need - a[i].mount;
}
printf("%.2f",result);
return 0;
}
9.B1068万绿丛中一点红。这道题参考了柳神的代码，注意容器的resize的用法，为重新指定有效元素的个数，当定义两个变长的二维数组的时候，需要这样定义。vector<vector
10.B1070结绳。这道题题目读不懂，所以导致做不出来，不过思路是对的，浮点数与正数相加是浮点数。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
double ans = a[0];
for(int i = 1; i < n; i++){
ans = (ans + a[i]) / 2;
}
printf("%d", (int)ans);
return 0;
}
10.B1045快速排序。这道题注意思路。一个数如果按照从小到大的顺序排列后，它的位置和源位置一样，并且大于左边的最大数，这个数就是主元。（另外一种思路是遍历数组，用一个数组来存储这个数左边的最大数，包括自己，遍历右边的数组，用一个数组存储这个数右边的最小数，包括自己，然后再遍历数组后，经过比较，找到主元。）注意当没有主元的时候，为了体现出第二行，需要输出换行符
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int v[100000];
int main(){
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) {
scanf("%d",&a[i]);
b[i] = a[i];
}
int max = 0, cnt = 0;
sort(b.begin(),b.end());
for(int i = 0; i < n; i++){
if(a[i] == b[i] && a[i] > max){
v[cnt++] = a[i];
}
if(a[i] > max)
max = a[i];
}
printf("%d\n", cnt);
for(int i = 0; i < cnt; i++){
printf("%d", v[i]);
if(i != cnt - 1) printf(" ");
}
printf("\n");
return 0;
}
11.B1075链表元素分类。这道题相当于一个模板，用node结构体来存储每一个链表结点的数据和下一个地址，另定义为list[100000]，list的下标就是地址。输入的时候本结点的地址就相当于是临时变量，存储进list结构体里面。遍历的时候注意使用的是while循环，设定临时指针等于第一个地址（start）当p != -1的时候作为遍历条件，结尾组不要忘记p指向下一个地址。输出时第一个结点只输出本结点地址和数据，其他的结点输出一个本结点地址，换行，再输出一个本结点地址，再输出本结点数据，最后的时候不要忘记输出最后结点的下一个地址为-1.本道题和1025反转链表一个采用顺序存储，一个采用链式存储，需要多注意。
#include <iostream>
#include <vector>
using namespace std;
struct node{
int data,next;
}list[100000];
vector <int> v[3];
int main(){
int start, n, k, a;
scanf("%d %d %d", &start, &n, &k);
for(int i = 0; i < n; i++){
scanf("%d", &a);
scanf("%d%d", &list[a].data, &list[a].next);
}
int p = start;
while(p != -1){
int data = list[p].data;
if(data < 0)
v[0].push_back(p);
else if(data >= 0 && data <= k)
v[1].push_back(p);
else
v[2].push_back(p);
p = list[p].next;
}
int flag = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < v[i].size(); j++){
if(flag == 0){
printf("%05d %d", v[i][j], list[v[i][j]].data);
flag = 1;
}else{
printf(" %05d\n%05d %d",v[i][j], v[i][j], list[v[i][j]].data);
}
}
}
printf(" -1");
return 0;
}