今天自己模拟考试的,第三题没写出来,PAT上15/25
我的Code Blocks16.01,不知道为何stoi函数没法用,开了C++11,就手写了
4268性感素数 PAT 1156
#include <iostream>
using namespace std;
bool is_prime(int n)
{
if (n < 2) return false;
for (int i = 2; i <= n / i; i++ ) {
if (n % i == 0) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n; cin >> n;
bool valid = false;
if (is_prime(n)) {
if (is_prime(n - 6) or is_prime(n + 6)) {
valid = true;
}
}
if (valid) {
cout << "Yes" << endl;
if (!is_prime(n - 6)) cout << n + 6;
else cout << n - 6;
}
else {
cout << "No" << endl;
int num = n + 1;
while (1) {
if (is_prime(num) and (is_prime(num + 6) or is_prime(num - 6))) {
break;
}
num++ ;
}
cout << num;
}
return 0;
}
4269校庆 PAT 1157
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Person
{
string id;
int year, month, day;
bool operator<(const Person& A) {
if (year != A.year) return year < A.year;
else if (month != A.month) return month < A.month;
else return day < A.day;
}
};
vector<Person> alumni;
vector<Person> guest;
set<string> all_alumni;
int n, m;
int to_int(string s)
{
int res = 0;
for (int i = 0; i < s.size(); i++ ) {
res = res * 10 + s[i] - '0';
}
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++ ) {
string id; cin >> id;
all_alumni.insert(id);
}
cin >> m;
for (int i = 0; i < m; i++ ) {
string id; cin >> id;
//370205198709275042
int cyear = stoi(id.substr(6, 4));
int cmonth = stoi(id.substr(10, 2));
int cday = stoi(id.substr(12, 2));
Person cperson = {id, cyear, cmonth, cday};
if (all_alumni.find(id) != all_alumni.end()) {
alumni.push_back(cperson);
}
else {
guest.push_back(cperson);
}
}
sort(alumni.begin(), alumni.end());
sort(guest.begin(), guest.end());
cout << alumni.size() << endl;
if (alumni.size() == 0) {
cout << guest[0].id;
}
else {
cout << alumni[0].id;
}
return 0;
}
4270电信诈骗(WA 15/25, acwing 6/11) PAT 1158
#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int N = 1010, M = 1e5 + 10;
int g[N][N];
int father[N];
int short_call[N];
bool suspect[N];
set<int> made_call[N];
vector<int> relation[N];
int n, m, k;
void init()
{
for (int i = 1; i <= n; i++ ) father[i] = i;
}
int find_father(int x)
{
if (x != father[x]) father[x] = find_father(father[x]);
return father[x];
}
int cal_response(int c)
{
int res = 0;
for (int i = 1; i <= n; i++ ) {
if (i == c) continue;
if ((g[c][i] <= 5 and g[c][i]) and g[i][c]) res++;
}
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> k >> n >> m;
init();
for (int i = 1; i <= m; i++ ) {
int c, r, d; cin >> c >> r >> d;
g[c][r] = d; //c->r
if (d <= 5 and made_call[c].find(r) == made_call[c].end()) {
short_call[c]++ ;
made_call[c].insert(r);
}
}
for (int i = 1; i <= n; i++ ) {
int response = cal_response(i);
if (short_call[i] > k and (double)response <= (double)short_call[i] * 0.2) suspect[i] = true;
}
for (int i = 1; i < n; i++ ) {
for (int j = i + 1; j <= n; j++ ) {
if (suspect[i] and suspect[j]) {
if (g[i][j] and g[j][i]) {
int fi = find_father(i), fj = find_father(j);
father[fi] = fj;
}
}
}
}
for (int i = 1; i <= n; i++ ) {
if (suspect[i]) {
int fi = find_father(i);
relation[fi].push_back(i);
}
}
int cnt = 0;
bool ept = true;
for (int l = 1; l <= n; l++ ) {
if (relation[l].size()) {
ept = false;
if (cnt) cout << endl;
cnt++ ;
for (int i = 0; i < relation[l].size(); i++ ) {
if (i) cout << " ";
cout << relation[l][i];
}
}
}
if (ept) cout << "None";
//for (int i = 1; i <= n; i++ ) {
// cout << short_call[i] << " " << suspect[i] << endl;
//}
return 0;
}
AC_version
#include <iostream>
#include <set>
#include <vector>
#include <stdlib.h>
using namespace std;
const int N = 1010, M = 1e5 + 10;
int g[N][N];
int father[N];
bool vis[N]; //cout suspects, if a suspect has been visited, note as true
vector<int> suspect;
int n, m, k;
void init()
{
for (int i = 1; i <= n; i++ ) father[i] = i;
}
int find_father(int x)
{
if (x != father[x]) father[x] = find_father(father[x]);
return father[x];
}
bool is_suspect(int u)
{
int short_call = 0, reply_call = 0;
for (int i = 1; i <= n; i++ ) {
if (i == u) continue;
if (g[u][i] and g[u][i] <= 5) { //u have a short call with i
short_call++;
if (g[i][u]) reply_call++ ; //i replys u
}
}
return short_call > k and short_call >= reply_call * 5; //reply <= 0.2*call
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> k >> n >> m;
init();
for (int i = 1; i <= m; i++ ) {
int c, r, d; cin >> c >> r >> d;
g[c][r] += d; //c->r add d, record total phone times here
}
for (int i = 1; i <= n; i++ ) {
if (is_suspect(i)) suspect.push_back(i);
}
if (suspect.size() == 0) {
cout << "None";
exit(0);
}
for (int i = 0; i < suspect.size() - 1; i++ ) {
for (int j = i + 1; j < suspect.size(); j++ ) {
int a = suspect[i], b = suspect[j];
if (g[a][b] and g[b][a]) { //suspect a and b have interacted with each other
int fa = find_father(a), fb = find_father(b);
father[fa] = fb; //conside a and b as the same gang
}
}
}
// for (int i = 0; i < suspect.size(); i++ ) cout << suspect[i] << " - ";
// cout << endl;
int cnt = 0;
for (int i = 0; i < suspect.size(); i++ ) {
int c = suspect[i];
if (vis[c]) continue;
if (cnt) cout << endl;
cnt = 1;
cout << c;
int fc = find_father(c);
vis[c] = 1;
for (int j = i + 1; j < suspect.size(); j++ ) {
int v = suspect[j];
int fv = find_father(v);
if (!vis[v] and fv == fc) {
cout << " " << v;
vis[v] = 1;
}
}
}
//for (int i = 1; i <= n; i++ ) {
// cout << short_call[i] << " " << suspect[i] << endl;
//}
return 0;
}
4271 二叉树的结构 PAT 1159
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;
const int N = 1010;
int parent[N], l_tr[N], r_tr[N];
int level[N];
int postorder[N], inorder[N];
int in_id[N];
int n, m, root;
int to_int(string t)
{
int res = 0;
for (int i = 0; i < t.size(); i++ ) {
res = res * 10 + t[i] - '0';
}
return res;
}
int build_tree(int pl, int pr, int ml, int mr, int lv)
{
if (pl > pr) return 0;
int root = postorder[pr];
level[root] = lv;
int mid = in_id[root];
int tl = build_tree(pl, pl + mid - 1 - ml, ml, mid - 1, lv + 1);
int tr = build_tree(pl + mid - ml, pr - 1, mid + 1, mr, lv + 1);
l_tr[root] = tl; r_tr[root] = tr;
parent[tl] = root; parent[tr] = root;
return root;
}
bool check_full()
{
int res = true;
for (int i = 0; i < n; i++ ) {
int k = inorder[i];
if ((!l_tr[k] and r_tr[k]) or (l_tr[k] and !r_tr[k])) {
res = false;
break;
}
}
return res;
}
bool is_dit(string c)
{
bool res = true;
for (int i = 0; i < c.size(); i++ ) {
if (c[i] < '0' or c[i] > '9') {
res = false;
break;
}
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++ ) cin >> postorder[i];
for (int i = 0; i < n; i++ ) {
cin >> inorder[i];
in_id[inorder[i]] = i;
}
root = build_tree(0, n - 1, 0, n - 1, 0);
// for (int i = 0; i < n; i++) {
// int k = inorder[i];
// cout << k << ":l: " << l_tr[k] << " r: " << r_tr[k] << " p: " << parent[k] << " lv: " << level[k] << endl;
// }
cin >> m; cin.ignore();
int A = -1;
for (int round = 0; round < m; round++ ) {
if (round) cout << endl;
string order;
getline(cin, order);
stringstream sstm(order);
if (order == "It is a full tree") {
bool res = check_full();
if (res) cout << "Yes";
else cout << "No";
}
else {
sstm >> order;
A = to_int(order);
int B = -1;
sstm >> order; //fliter is/and
sstm >> order;
if (order != "the") {
B = to_int(order);
while (sstm >> order) {
if (order == "siblings") {
if (parent[A] and parent[B] and parent[A] == parent[B] and A != B) cout << "Yes";
else cout << "No";
}
if (order == "same") {
if (level[A] == level[B]) cout << "Yes";
else cout << "No";
}
}
}
else {
sstm >> order;
if (order == "root") {
if (!parent[A]) cout << "Yes";
else cout << "No";
}
else if (order == "parent") {
while (sstm >> order) {
if (is_dit(order)) {
B = to_int(order);
if (parent[B] == A) cout << "Yes";
else cout << "No";
}
}
}
else if (order == "left") {
while (sstm >> order) {
if (is_dit(order)) {
B = to_int(order);
if (l_tr[B] == A) cout << "Yes";
else cout << "No";
}
}
}
else if (order == "right") {
while (sstm >> order) {
if (is_dit(order)) {
B = to_int(order);
if (r_tr[B] == A) cout << "Yes";
else cout << "No";
}
}
}
}
}
}
//string s = "It is a nice day";
//stringstream sstrm(s);
//while (sstrm >> s) {
// cout << s << endl;
//}
return 0;
}