明天要上2019年的第一节课。令人兴奋嗷(￣￣)
今天这套（PAT甲级2018冬）也是写的hin顺的一套，一次提交全AC，可能冬季确实比较水？
为了这个8连 最后一题检查了好久wwwww
1152 | Google Recruitment
从长度为n一串数字中，找出第一个长度为k的素数。很顺利。
string部分拷贝：temp_str = str.substr(0,5); // 从str[0]开始的5个
没想起来substr，就+=一波。。。
stoi好用。
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
bool isPrime(int num) {
if (num < 2) return false;
int bound = sqrt(num);
for (int i = 2; i <= bound; ++i) {
if (num % i == 0) return false;
}
return true;
}
int main() {
int nn, kk;
string str;
cin >> nn >> kk >> str;
for (int i = 0; i + kk <= nn; ++i) {
string temp;
for (int j = i; j < i + kk; ++j)
temp += str[j];
if (isPrime(stoi(temp))) {
cout << temp << endl;
return 0;
}
}
puts("404");
return 0;
}
1153 | Decode Registration Card of PAT
一开始想着把每项都拆出来，存到结构体里，再排序、统计……
后来觉得没必要。
- 在输入的时候就用map分别存这三种查询需要的统计。
- map套map稍微考虑了一下……
因为date、site两个坐标才能定下来cnt，但查询是仅按date查，对应出的site还要再按date，site对应出的 cnt 和 site编号大小再排序。
所以先map嵌套存下来，在查询的时候再拖出来排个序。
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
#include <set>
using namespace std;
struct Stu {
string str_id;
int score; // %03d %06d %03d
bool operator<(const Stu &s2) const {
return score == s2.score ? str_id < s2.str_id : score > s2.score;
}
};
map<int, pair<int, int>> site_total;
map<char, set<Stu>> level_stuId;
map<int, map<int, int>> date_site_cnt;
struct Rec {
int p1, p2;
bool operator<(const Rec &r2) const {
return p2 == r2.p2 ? p1 < r2.p1 : p2 > r2.p2;
}
};
int main() {
int nn, nq, score;
char temp[15];
scanf("%d%d", &nn, &nq);
getchar();
for (int i = 0; i < nn; ++i) {
int site, date, no;
scanf("%s%d", temp, &score);
level_stuId[temp[0]].insert(Stu{temp, score});
string attr;
int j = 1;
for (; j < 4; ++j) attr += temp[j];
site = stoi(attr);
attr = "";
for (; j < 10; ++j) attr += temp[j];
date = stoi(attr);
attr = "";
site_total[site].first++;
site_total[site].second += score;
date_site_cnt[date][site]++;
}
int type;
for (int i = 1; i <= nq; ++i) {
scanf("%d", &type);
printf("Case %d: ", i);
switch (type) {
case 1:
getchar();
char ch;
scanf("%c", &ch);
printf("%d %c\n", type, ch);
if (level_stuId[ch].empty()) puts("NA");
else
for (auto &item:level_stuId[ch])
printf("%s %d\n", item.str_id.data(), item.score);
break;
case 2:
int site;
scanf("%d", &site);
printf("%d %03d\n", type, site);
if (site_total.find(site) != site_total.end())
printf("%d %d\n", site_total[site].first, site_total[site].second);
else puts("NA");
break;
case 3:
int date;
scanf("%d", &date);
printf("%d %06d\n", type, date);
if (date_site_cnt[date].empty()) puts("NA");
else {
set<Rec> res;
for (auto &item: date_site_cnt[date])
res.insert(Rec{item.first, item.second});
for (auto &item: res)
printf("%03d %d\n", item.p1, item.p2);
}
break;
}
}
return 0;
}
1154 | Vertex Coloring
图染色，看标题吓了一跳。但实际上非常水哈～
unordered_set计数一下颜色种数。
然后遍历一下每个点与相连的边有没有同色，有则No，否则……
#include <cstdio>
#include <vector>
#include <unordered_set>
using namespace std;
int colors[10001];
vector<int> graph[10001];
int main() {
int nn, mm, v1, v2;
scanf("%d%d", &nn, &mm);
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &v1, &v2);
graph[v1].emplace_back(v2);
graph[v2].emplace_back(v1);
}
int ncheck, ncolor;
scanf("%d", &ncheck);
for (int i = 0; i < ncheck; i++) {
unordered_set<int> mset;
for (int j = 0; j < nn; ++j) {
scanf("%d", &colors[j]);
mset.insert(colors[j]);
}
ncolor = mset.size();
bool flag = true;
for (int j = 0; flag && j < nn; ++j) {
for (auto &item:graph[j]) {
if (colors[j] == colors[item]) {
flag = false;
break;
}
}
}
flag ? printf("%d-coloring\n", ncolor) : printf("No\n");
}
return 0;
}
1155 | Heap Paths
给定完全二叉树，输出所有根到叶子的路径，判断是不是堆（大顶or小顶）。
- 输出路径DFS即可。
- 注意题目要求：路径顺序是从右到左。dfs先右后左。
- 注意路径不要重复：套个 set<vector<int>>应该是最省事的哈。
用vector<vector<int>> paths存所有路径的话，就要注意：- 若无孩子（编号>=nn / 2），这条路走完了，把当前路径加到paths里。
- 往下走时，注意判断孩子不是null（编号小于n）。
- 遍历输出所有路径，顺便判断类型。
#include <cstdio>
#include <vector>
using namespace std;
int tree[1001];
vector<vector<int>> paths;
vector<int> curr_path;
int nn;
void dfs_path(int root) {
if (root >= nn / 2) {
curr_path.push_back(tree[root]);
paths.push_back(curr_path);
curr_path.pop_back();
} else {
curr_path.push_back(tree[root]);
if (2 * root + 2 < nn) dfs_path(2 * root + 2);
if (2 * root + 1 < nn) dfs_path(2 * root + 1);
curr_path.pop_back();
}
}
int main() {
scanf("%d", &nn);
for (int i = 0; i < nn; ++i) {
scanf("%d", &tree[i]);
}
dfs_path(0);
if (paths[0][0] > paths[0][1]) { // check max heap
bool isHeap = true;
for (auto &item: paths) {
int pre = 0x3fffffff, size = item.size();
for (int i = 0; i < size; ++i) {
i == size - 1 ? printf("%d\n", item[i]) : printf("%d ", item[i]);
pre > item[i] ? pre = item[i] : isHeap = false;
}
}
printf(isHeap ? "Max Heap\n" : "Not Heap\n");
} else { // check min heap
bool isHeap = true;
for (auto &item: paths) {
int pre = -1, size = item.size();
for (int i = 0; i < size; ++i) {
i == size - 1 ? printf("%d\n", item[i]) : printf("%d ", item[i]);
pre < item[i] ? pre = item[i] : isHeap = false;
}
}
printf(isHeap ? "Min Heap\n" : "Not Heap\n");
}
return 0;
}
网友评论