Aczy156

Contest PAT-PTA刷题系统

[TOC]

PTA1001-1099

PTA 1001

题目大意：求a+b

  • 【易错】输出格式的标准化：每3位来一个逗号（利用循环+取余进行输出）
#include <iostream>
using namespace std;
int a, b, c, d, i;
string s = "";

int main() {
    scanf("%d%d", &a, &b);
    c = a+b;
    if (c < 0) d = 1, c = -c;
    if (c == 0) {printf("0");return 0;}
    while (c) {
        s += '0'+c%10;
        c /= 10;
        if (!(++i%3) && c) i=0, s += ',';
    }
    if (d) cout<<"-";
    for (int j = s.length()-1; j >= 0; --j) cout<<s[j];
    return 0;
}

PTA 1007

题目大意：最大子区间。和

  • 子区间中有可能穿插着负数。（因此不能一到负数就重置起终点，而是要等到当前临时的sum小于0了，再重置起终点）
  • 重置终点的情况为sum>ans，此时才是正确的重置起终点的时机。
  • 【易错】特殊情况考虑：对于全是负数的情况，此时ans为0，但是ans为0不一定全是负数，因为有可能存在0 0 0这样的子区间。
#include <iostream>
using namespace std;
int n, bg, ed, ans=-1, sum, a[10009], ansbg, ansed;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a+i);
        if (sum + a[i] < 0) {
            bg = i+1;sum = 0;
        } else {
            sum += a[i];
            if (sum > ans) ans = sum, ed = i, ansbg = bg,ansed = ed;
        }
    }
    if (ans == -1) printf("%d %d %d", 0, a[0], a[n-1]);
    else printf("%d %d %d", ans, a[ansbg], a[ansed]);
    return 0;
}

PTA 1008

题目大意：直接模拟楼层上下变化即可

#include <iostream>
using namespace std;
int n, t, ls, ans;

int main() {
    scanf("%d", &n);ans = 5*n;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t);
        if (t > ls) ans += 6*(t-ls);
        else ans += 4*(ls-t);
        ls = t;
    }
    printf("%d", ans);
    return 0;
}

PTA 1012

题目大意：给出n个人的平均成绩、c语言、数学、英语，输出所有人排名最高的科目以及排名。（如果有相同的按照平均成绩>c语言>数学>英语顺序输出）

  • 利用map进行string和struct结构体进行映射
  • 【易错】排序问题：排名时分数相同的话，就需要设置并列
#include <iostream>
using namespace std;
const int maxn = 2e3+9;
struct student {
    string id;
    int sc, sm, se, sa;
    int rc, rm, re, ra;
}as[maxn];
#include <map>
map<string, student> m;
int n, q, cnt;
#include <algorithm>
string nid;
char c;

bool cmp_average(student s1, student s2) {return s1.sa > s2.sa;}
bool cmp_c(student s1, student s2) {return s1.sc > s2.sc;}
bool cmp_math(student s1, student s2) {return s1.sm > s2.sm;}
bool cmp_english(student s1, student s2) {return s1.se > s2.se;}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        cin>>as[i].id>>as[i].sc>>as[i].sm>>as[i].se;
        as[i].sa = as[i].sc + as[i].sm + as[i].se;
        m[as[i].id] = as[i];
    }
    sort(as+1, as+1+n, cmp_average);
    for (int i = 1; i <= n; ++i)
        if (m[as[i].id].sa == m[as[i-1].id].sa && i!=1) m[as[i].id].ra = m[as[i-1].id].ra;
        else m[as[i].id].ra=i;
    sort(as+1, as+1+n, cmp_c);
    for (int i = 1; i <= n; ++i)
        if (m[as[i].id].sc == m[as[i-1].id].sc && i!=1) m[as[i].id].rc = m[as[i-1].id].rc;
        else m[as[i].id].rc=i;
    sort(as+1, as+1+n, cmp_math);
    for (int i = 1; i <= n; ++i)
        if (m[as[i].id].sm == m[as[i-1].id].sm && i!=1) m[as[i].id].rm = m[as[i-1].id].rm;
        else m[as[i].id].rm=i;
    sort(as+1, as+1+n, cmp_english);
    for (int i = 1; i <= n; ++i)
        if (m[as[i].id].se == m[as[i-1].id].se && i!=1) m[as[i].id].re = m[as[i-1].id].re;
        else m[as[i].id].re=i;
    for (int i = 1; i <= q; ++i) {
        cin>>nid;
        if (i != 1) printf("\n");
        if (!m.count(nid)) {printf("N/A");continue;}
        cnt = m[nid].ra;c = 'A';
        if (cnt > m[nid].rc) cnt = m[nid].rc, c = 'C';
        if (cnt > m[nid].rm) cnt = m[nid].rm, c = 'M';
        if (cnt > m[nid].re) cnt = m[nid].re, c = 'E';
        cout<<cnt<<" "<<c;
    }
    return 0;
}

PTA 1013

题目大意：给出n个城，m条路，k个查询，查询内容为，当排除掉输入的这个城（这个城+与这个城相连的连线都失效）之后，联通其他所有城所需要新增的路数

  • 利用kruskal的并查集维护点集思路，储存数据用线/链式前向星均可
  • 【易错】数据边界问题：容易RE，在这个题里边，他没有限定线的个数，所以线的个数的上限应该是点数*点数

PTA 1020

题目大意：给出二叉树中序后序，求层次遍历

  • 利用后序最后一个是根结点，然后从中序里边进行分割，分割出左右两块分别为这个根结点的左右儿子。
  • 递归建树的返回内容是一个节点。递归的参数要包括中序的左右区间节点以及后序的根结点，三个参数即可
  • 【易错】递归终点返回值问题：返回NULL的条件

PTA 1023

题目大意：给出一个数，看看这个数在乘了2之后，是否还满足和原来一样的各种数字的个数不变但是顺序变化

PTA 1040

题目大意：找到最大的回文子串

PTA 1143

题目大意：二叉搜索树，寻找最近公共祖先LCA。

  • 利用二叉搜索树BST的性质，中序遍历=>得到的必定是递增序列
  • 因为找最近公共祖先，所以可以从上往下找，通过当前节点x和uv进行比较
    • 如果x<u & x<v，根据BST性质，uv都在右子树上=>x通过右儿子往下爬
    • 如果x>u & x>v，根据BST性质，uv都在左子树上=>x通过左儿子往下爬
    • 如果u≤x≥v，根据BST性质，当前的节点就是LCA了（只不过当前的节点可能是左儿子，右儿子，也可能都不是）=>此时也再不需要往下爬了，因为根据性质第一个满足不等式的就是LCA
#include <iostream>
using namespace std;
const int maxn = 1e4+9;
int n, m, pre[maxn], u, nw, v;
#include <map>
map<int, int>mp;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {scanf("%d", pre+i);mp[pre[i]] = 1;}
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &u, &v);
        if (i!=1) printf("\n");
        if (!mp.count(u) && !mp.count(v)) printf("ERROR: %d and %d are not found.", u, v);
        else if (!mp.count(u) || !mp.count(v)) printf("ERROR: %d is not found.", mp.count(u)?v:u);
        else {
            for (int j = 1; j <= m; ++j) {
                nw = pre[j];
                if ((nw >= u && nw <= v) || (nw >= v && nw <= u)) break;
            }
            if (nw == u) printf("%d is an ancestor of %d.", u, v);
            else if (nw == v) printf("%d is an ancestor of %d.", v, u);
            else printf("LCA of %d and %d is %d.", u, v, nw);
        }
    }
    return 0;
}

PTA 1147

题目大意：判断是否是堆，如果是堆，是最大堆还是最小堆。

  • 利用堆的性质，进行判断：最大堆满足两个儿子节点都小于根节点，那么就从后往前遍历，如果存在a[i] > a[i>>1]=>表示儿子节点大于根节点，那么必定不是最大堆。反之，最小堆一样判断
#include <iostream>
using namespace std;
const int maxn = 1009;
int n, m, a[maxn], is_big, is_small;

void posttraverse(int x) {
    if (x > m) return;
    posttraverse(2*x);
    posttraverse(2*x+1);
    printf("%d%s", a[x], x == 1 ? "\n" : " ");
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        is_big = 1, is_small = 1;
        for (int j = 1; j <= m; ++j) scanf("%d", a+j);
        for (int j = 2; j <= m; ++j) {
            if (a[j] > a[j/2]) is_big = 0;
            else is_small = 0;
        }
        if (is_big) printf("Max Heap\n");
        else if (is_small) printf("Min Heap\n");
        else printf("Not Heap\n");
        posttraverse(1);
    }
    return 0;
}

PTA 1154

题目大意：问所有相邻的点的颜色是否都满足不同，如果存在有相同的，则输出no；如果都不相同，输出这是几色图

  • 简单的图遍历（用链式前向星存图）
  • 利用mp维护有多少种颜色
#include <iostream>
using namespace std;
const int maxn = 1e4+9;
int n, m, k, ta, tb, c[maxn], vis[maxn];
struct node {
    int to, nt;
}edges[maxn<<1];int head[maxn], tot;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))

void addedge(int from, int to) {
    edges[++tot].to = to;
    edges[tot].nt = head[from];
    head[from] = tot;
}

#include <queue>
queue<int> q;
bool solve() {
    while (!q.empty()) q.pop(); cl(vis, 0);
    for (int i = 0; i < n; ++i) {
        q.push(i);
        while (!q.empty()) {
            int nw = q.front();q.pop();
            if (!vis[nw]) {
                for (int j = head[nw]; j; j=edges[j].nt) {
                    int to = edges[j].to;
                    if (c[nw] == c[to]) return false;
                    q.push(to);
                }
                vis[nw] = 1;
            }
        }
    }
    return true;
}

#include <map>
map<int, int> mp;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        addedge(ta, tb);addedge(tb, ta);
    }
    scanf("%d", &k);
    for (int i = 0; i < k; ++i) {
        mp.clear();
        for (int j = 0; j < n; ++j) scanf("%d", c+j), mp[c[j]] = 1;
        if (solve()) printf("%d-coloring\n", mp.size());
        else puts("No");
    }

    return 0;
}
Posted on Apr 8, 2020