PAT-Advanced 热身题

2020-04-02
Abstract：也就是所谓的水题，如果你刚开始刷PAT可以先做这些熟悉PAT的模式

1036 Boys vs Girls (25分)

image-20200402180429421

完整解法

模拟题意就行了，没有算法

#include <iostream>

struct Student {      // Input student structure
	std::string name;
	char gender;
	std::string ID;
	int grade;
};

/* Global */
int num;                    // Input number
Student student, girl, boy; // maxGirl & minBoy

void ParseInput() {
	girl.grade = -1;
	boy.grade = 101;
	std::cin >> num;
	for (int i = 0; i < num; i++) {  // Update max and min if it's exist
		std::cin >> student.name >> student.gender >> student.ID >> student.grade;
		if (student.gender == 'F' && student.grade > girl.grade) girl = student;
		if (student.gender == 'M' && student.grade < boy.grade) boy = student;
	}
}

void OutPutStudent(const Student& s) { // give an output of student
	std::cout << s.name << " " << s.ID << std::endl;
}

int main() {
	ParseInput();

	if (girl.grade != -1) OutPutStudent(girl);
	else std::cout << "Absent" << std::endl;

	if (boy.grade != 101) OutPutStudent(boy);
	else std::cout << "Absent" << std::endl;

	if (boy.grade == 101 || girl.grade == -1) std::cout << "NA" << std::endl;
	else std::cout << girl.grade - boy.grade;
}

压缩版

#include <iostream>
struct Student {
	std::string name;
	char gender;
	std::string ID;
	int grade;
};
int main() {
	int num;
	std::cin >> num;
	Student s, girl, boy;
	girl.grade = -1, boy.grade = 101;
	for (int i = 0; i < num; i++) {
		std::cin >> s.name >> s.gender >> s.ID >> s.grade;
		if (s.gender == 'F' && s.grade > girl.grade) girl = s;
		if (s.gender == 'M' && s.grade < boy.grade) boy = s;
	}
	if (girl.grade != -1) std::cout << girl.name << " " << girl.ID << std::endl;
	else std::cout << "Absent" << std::endl;
	if (boy.grade != 101) std::cout << boy.name << " " << boy.ID << std::endl;
	else std::cout << "Absent" << std::endl;
	if (boy.grade == 101 || girl.grade == -1) std::cout << "NA" << std::endl;
	else std::cout << girl.grade - boy.grade;
}

1005 Spell It Right (20分)

image-20200403171941141

完整解法

100次方显然是提示我们用字符串读入，所幸只需要逐个相加，那么这个问题就变成了将100个以内的个位数相加再逐个输出对应字符串的幼儿园问题了

#include <iostream>
#include <string>

int sum = 0;

void ParseInput() {
	std::string s;
	std::getline(std::cin, s);
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != 0) sum += s[i] - 48;
	}
}

void OutPutN(int num) {
	std::string s = std::to_string(num);
	for (int i = 0; i < s.length();i++) {
		if (s[i] == '0')std::cout << "zero";
		if (s[i] == '1')std::cout << "one";
		if (s[i] == '2')std::cout << "two";
		if (s[i] == '3')std::cout << "three";
		if (s[i] == '4')std::cout << "four";
		if (s[i] == '5')std::cout << "five";
		if (s[i] == '6')std::cout << "six";
		if (s[i] == '7')std::cout << "seven";
		if (s[i] == '8')std::cout << "eight";
		if (s[i] == '9')std::cout << "nine";
		if (i != s.length() - 1)std::cout << " ";
	}
}

int main() {
	ParseInput();
	OutPutN(sum);
}

1008 Elevator (20分)

image-20200403174240234

完整解法

模拟题意，造一个变量维护上一次的层数，幼儿园题目

#include <iostream>

int main() {
	int sum = 0, num, curr, prev = 0;
	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> curr;
		int diff = curr - prev;
		if (diff > 0)sum += 6 * diff;
		else sum += -4 * diff;
		sum += 5;
		prev = curr;
	}
	std::cout << sum;
}

1011 World Cup Betting (20分)

image-20200403181910338

完整解法

题目看着挺长，其实就是求三组最大值这种幼儿园操作

#include <iostream>

int main() {
	float curr,max[3];
	for (int i = 0; i < 3; i++) {
		char idx;
		for (int j = 0; j < 3; j++) {
			std::cin >> curr;
			if (curr > max[i]) {
				max[i] = curr;
				if (j == 0)idx = 'W';
				if (j == 1)idx = 'T';
				if (j == 2)idx = 'L';
			}
		}
		std::cout << idx << " ";
	}
	printf("%.2f", (max[0] * max[1] * max[2] * 0.65 - 1) * 2);
}

1015 Reversible Primes (20分)

image-20200403204100393

完整解法

素数判断 + 进制转换

#include<iostream>
#include<cmath>

bool isPrime(int val) {
	if (val <= 1) return false;
	for (int i = 2; i <= std::sqrt(val); i++) {
		if (val % i == 0) return false;
	}
	return true;
}

int toGeneral(int n, int b) {
	int ans = 0;
	while (n > 0) {
		ans = ans * b + (n % b);
		n /= b;
	}
	return ans;
}

int main() {
	int n, b;
	std::ios::sync_with_stdio(false); std::cin.tie(0);
	while (std::cin >> n) {
		if (n < 0) return 0;
		std::cin >> b;
		int general = toGeneral(n, b);
		if (isPrime(general) && isPrime(n))
			std::cout << "Yes" << std::endl;
		else 
			std::cout << "No" << std::endl;
	}
}

1001 A+B Format (20分)

image-20200401154141730

解法一

  • 每三个数加入一个逗号
  • 记得处理零，负号以及头部的逗号
#include <iostream>

// Parse number to string
std::string toString(int x) {
	std::string ans = "";
	int count = 0;
	while (x != 0) {
		char n = x % 10;
		ans += n+48;
		count++;
		if (count % 3 == 0)ans += ',';
		x /= 10;
	}
	return ans;
}

int main(){
	int a, b;
	std::cin >> a >> b;
	std::string str;
	int number = a + b;
	// Zero
	if (number == 0) {
		std::cout << 0;
		return 0;
	}
	// Negative
	else if (number < 0) {
		str = toString(-(number));
		std::cout << '-';
	}
	// Positive
	else str = toString(number);

	// Linear scan
	int len = str.length();
	for (int i = len-1 ; i > -1;i--) {
		if (i == len - 1 && str.at(i) == ',')continue;
		else std::cout << str.at(i);
	}
}

解法二：to_string（）

to_string很方便，但是要动态输出逗号

#include <iostream>
int main() {
    int a, b;
    std::cin >> a >> b;
    std::string s = std::to_string(a + b);
    int len = s.length();
    for (int i = 0; i < len; i++) {
        std::cout << s.at(i);
        if (s.at(i) == '-') continue;
        if ((i + 1) % 3 == len % 3 ) std::cout << ",";
    }
    return 0;
}

1041 Be Unique (20分)

image-20200413011119370

解法一：std::unordered_map

很简单，但是要注意unordered_map遍历时key是无插入序的，所以另外维护一个vector来记录插入顺序

#include<iostream>
#include<unordered_map>
#include<vector>

int num, val;
std::unordered_map<int,int> map;
std::vector<int> order;

int main() {
	std::cin >> num;
	order = std::vector<int>(num);
	for (int i = 0; i < num; i++) {
		std::cin >> order[i];
		if (map.find(order[i]) == map.end())
			map.insert({ order[i], 1 });
		else map[order[i]]++;
	}

	for(int i : order)
		if (map[i] == 1) {
			std::cout << i;
			return 0;
		}
	std::cout << "None";	
}

解法二：数组hashmap

同上

#include<iostream>
#include<unordered_map>
#include<vector>

int num, map[100001] = { 0 };
std::vector<int> order;

int main() {
	std::cin >> num;
	order = std::vector<int>(num);
	for (int i = 0; i < num; i++) {
		std::cin >> order[i];
		map[order[i]]++;
	}

	for (int i : order) {
		if (map[i] == 1) {
			std::cout << i;
			return 0;
		}
	}
	std::cout << "None";	
}

1027 Colors in Mars (20分)

image-20200415165931036

解法一

跟柳神学的进制转换小技巧​，就很实用​

#include<iostream>

int main() {
	const char* c = "0123456789ABC";
	int val;
	std::cout << '#';
	for (int i = 0; i < 3; i++) {
		std::cin >> val;
		std::cout << c[val / 13] << c[val % 13];
	}
}

1019 General Palindromic Number (20分)

image-20200415180343828

解法一

进制转换 + 回文判断

#include<iostream>
#include<vector>

bool isPalindromic(const std::vector<int>& num) {
	int lo = 0, hi = num.size() - 1;
	while (lo < hi) {
		if (num[lo] != num[hi]) return false;
		lo++; hi--;
	}
	return true;
}

void toGeneral(int n, int b, std::vector<int>& num) {
	while (n != 0) {
		num.push_back(n % b);
		n /= b;
	}
}

int main() {
	int n, b;
	std::ios::sync_with_stdio(false); std::cin.tie(0);
	std::cin >> n >> b;

	std::vector<int> num;
	toGeneral(n, b, num);

	if (isPalindromic(num)) std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;

	for (int i = num.size() - 1; i > -1; i--) {
		if (i == 0) std::cout << num[i];
		else std::cout << num[i] << " ";
	}
}

1023 Have Fun with Numbers (20分)

image-20200416182127969

解法一

大数加法，维护一个map来确认double前后的各个数字出现的个数是否相等

注意如果最高位出现了进位，那么貌似不需要map[1]也能通过，涉及到数论我不知道这个命题是否正确（因为测试数据也不是百分百严谨的），这里我还是加上了map[1]，有兴趣的朋友可以自行证明

#include<iostream>

std::string num;
int map[11] = { 0 };

void doubleIt(std::string& num) {
	int carry = 0;
	for (int i = num.length() - 1; i > -1; i--) {
		map[num[i] - '0']++;

		num[i] = 2 * num[i] - '0' + carry;
		if (num[i] > '9') {
			num[i] -= 10;
			carry = 1;
		}
		else carry = 0;

		map[num[i] - '0']--;
	}
	if (carry == 1) { map[10]++; map[1]++; } // map[10]表示最高位进位的情况
}

bool checkPerm() {
	for (int i : map)
		if (i != 0) return false;
	return true;
}

int main() {
	// std::ios::sync_with_stdio(false); std::cin.tie(0);
	std::cin >> num;
	doubleIt(num);
	std::cout << (checkPerm() ? "Yes" : "No") << std::endl;
	if (map[10]) std::cout << 1;
	std::cout << num;
}

1092 To Buy or Not to Buy (20分)

image-20200417181139362

image-20200417181150315

解法一

幼儿园题目，因为ascii码一共就100来个，直接开个数组就行了，连unordered_map都不需要

再快一点可以单个字符读入，但是string长度不超过1000，所以就无所谓了

#include<iostream>

int map[200], miss = 0;

int main() {
	std::string beads, target;
	std::cin >> beads >> target;
	for (char& c : beads) map[c]++;
	for (char& c : target) {
		if (map[c] == 0) miss++;
		else map[c]--;
	}
	if (miss == 0)
		std::cout << "Yes " << beads.length() - target.length();
	else 
		std::cout << "No " << miss;
}

1050 String Subtraction (20分)

image-20200417191921746

解法一

同上题，不能再简单了

#include<iostream>
#include<string>

int map[100];

int main() {
	std::string s1, s2;
	std::getline(std::cin, s1);
	std::getline(std::cin, s2);
	for (char& c : s2) map[c]++;
	for (char& c : s1) 
        if (map[c] == 0) std::cout << c;
}

1120 Friend Numbers (20分)

image-20200417195724519

解法一：std::set

简单方便

#include<iostream>
#include<set>

int sumIt(const std::string& val) {
	int ans = 0;
	for (char c : val)
		ans += c - '0';
	return ans;
}

int main() {
	int num;
	std::string val;
	std::set<int> nums;
	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> val;
		int fn = sumIt(val);
		nums.insert(fn);
	}

	std::cout << nums.size() << std::endl;
	for (auto i = nums.begin(); i != nums.end(); i++) {
		if (i == --nums.end())
			std::cout << *i;
		else
			std::cout << *i << " ";
	}
}

同理也可以手动set

1058 A+B in Hogwarts (20分)

image-20200420152628228

解法一

穷人版的大数加减法

#include<iostream>

struct num {
	long long a, b, c;
}n1, n2;

num sumOf(num& x, num& y) {
	int carry = 0;
	long long a, b, c;
	c = x.c + y.c; 
	carry = c >= 29 ? 1 : 0; c = carry ? c - 29 : c;
	b = x.b + y.b + carry; 
	carry = b >= 17 ? 1 : 0; b = carry ? b - 17 : b;
	a = x.a + y.a + carry; 
	return { a,b,c };
}

int main() {
	scanf("%lld.%lld.%lld", &n1.a, &n1.b, &n1.c);
	scanf("%lld.%lld.%lld", &n2.a, &n2.b, &n2.c);
	num ans = sumOf(n1, n2);
	printf("%lld.%lld.%lld", ans.a, ans.b, ans.c);
}

1083 List Grades (25分)

image-20200420153758520

image-20200420153813059

解法一：std::sort()又双叒秒了

#include<iostream>
#include<vector>
#include<algorithm>

struct Student {
	std::string name, id;
	int mark;
};

std::vector<Student> records;
int grade1, grade2;

int compare(Student a, Student b) {
	return a.mark > b.mark;
}

void parseInput() {
	int num;
	std::cin >> num;
	records = std::vector<Student>(num);
	for (int i = 0; i < num; i++)
		std::cin >> records[i].name >> 
		records[i].id >> records[i].mark;
	std::sort(records.begin(), records.end(),compare);

	std::cin >> grade1 >> grade2;
}

int main() {
	parseInput();
	bool check = false;
	for (Student i : records) {
		if (i.mark >= grade1 && i.mark <= grade2) {
			std::cout << i.name << " " << i.id << std::endl;
			check = true;
		}
	}
	if (check == false)
		std::cout << "NONE";
}

1084 Broken Keyboard (20分)

image-20200420161604998

解法一

自制map记录实际输入的键，剩下应该输入但没输入的就是坏的，注意先转换大小写

#include<iostream>
#include<string>

bool map[200] = { false };

int main() {
	std::string input, typeout;
	std::getline(std::cin, input);
	std::getline(std::cin, typeout);

	for (char c : typeout) {
		c = isalpha(c) ? toupper(c) : c;
		map[c] = true;
	}

	for (char c : input) {
		c = isalpha(c) ? toupper(c) : c;
		if (map[c] == false) {
			std::cout << c;
			map[c] = true;
		}
	}
}

1065 A+B and C (64bit) (20分)

image-20200421170200351

解法一

数据范围正负2的64次方，显然暗示我们处理long long的溢出，而不是字符串模拟

注意必须用一个long long 变量来接收a+b，而不是直接判断a+b与0的关系，因为

#include<iostream>

bool checkRes(long long& a, long long& b, long long& c) {
	long long sum = a + b;
	if (a > 0 && b > 0 && sum < 0)  return true;
	if (a < 0 && b < 0 && sum >= 0) return false;
	return a + b > c;
}

int main() {
	int num;
	long long a, b, c;
	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> a >> b >> c;
		if (checkRes(a, b, c))
			printf("Case #%d: true\n", i + 1);
		else
			printf("Case #%d: false\n", i + 1);
	}
}

1035 Password (20分)

image-20200422152257299

image-20200422152317407

解法一

就遍历把该改掉的改掉就行了，没什么可说的，结果为空时，根据N的不同输出略有不同

#include<iostream>
#include<vector>

int num;
std::string id, pw;
std::vector<std::string> ids, pws;

void parseInput() {
	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> id >> pw;
		bool check = false;
		for (char& c : pw) {
			if (c == '1' || c == '0' || c == 'l' || c == 'O') {
				check = true;
				if (c == '1') c = '@';
				else if (c == '0') c = '%';
				else if (c == 'l') c = 'L';
				else if (c == 'O') c = 'o';
			}
		}
		if (check) {
			ids.push_back(id);
			pws.push_back(pw);
		}
	}
}

int main() {
	parseInput();
	if (ids.empty()) {
		if (num == 1)
			printf("There is 1 account and no account is modified");
		else
			printf("There are %d accounts and no account is modified", num);
	}
	else {
		std::cout << ids.size() << std::endl;
		for (int i = 0; i < ids.size(); i++)
			std::cout << ids[i] << " " << pws[i] << std::endl;
	}
}
© 2020 Overyam - Powered by Hexo - Theme Chan