2014-03-01 春季PAT 1073-1076解题报告

今天下午的PAT考试状态不理想，回来怒刷了一遍，解题报告如下：

基本模拟题，将一长串的科学计数转换为普通的数字表示方式。思路是是数组存储输入，然后找到指数位置，并根据指数的大小和正负对前面的小数进行针对性的处理。

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

class PAT{

public:

    enum { N = , };

    char num[N];

    int finger,epos,length;

    void run();

};

void PAT::run()

{

    scanf("%s", &num);

    length = strlen(num);

    epos = find(num, num + length, 'E') - num;

    sscanf(num + epos + , "%d", &finger);

    if (num[epos + ] == '-') finger = - * finger;

    if(num[]=='-')printf("%c", num[]);

    int i, j;

    if (finger >= )

    {

        printf("%c", num[]);

        for (i = ; i < epos && finger > ; i++,finger--) printf("%c", num[i]);

        if (i < epos) { printf("."); for (; i < epos; i++)printf("%c", num[i]); }

        else if (finger > ) while (finger > ){ printf(""); finger--; }

    }

    else

    {

        printf("0."); finger++;

        while (finger < ) {printf(""); finger++;}

        printf("%c", num[]);

        for (int i = ; i < epos; i++)printf("%c", num[i]);

    }

}

int main()

{

    //freopen("input.txt", "r", stdin);

    PAT *p = new PAT;

    p->run();

    return ;

}

PAT 1074. Reversing Linked List (25)

这个题不难，关键是要细心，首先要看懂题意。题目说的逆转排序是指每隔K个节点就将这k个节点的顺序颠倒过来，而如果最后不足K个节点的话，是不进行颠倒的，我下午考试的时候把这个意思弄错了，以为最后的节点也要进行颠倒，结果当然不对。这个题可以用map来做，不过据我同学说，用map查询会超时，我没有这样试过，不知道究竟如何，我使用的是hash的办法，直接在数组里面存储，速度会快点。

另外，这个题跟前面1052题的链表排序一样，有一个陷阱，就是不是所有给出的节点都属于此链表，需要判断，最后一个测试点是这个陷阱，不过这个点只有1分，姥姥出题的时候还是很人道。不过很多人这个点都没过。

#include <iostream>

using namespace std;

class PAT

{

public:

    enum{N=};

    struct Node

    {

        int addr, data, next;

    };

    Node node[N];

    int hash[N];//addr->index

    int addr[N];//index->addr

    int n,k,head;

    void run();

};

void PAT::run()

{

    scanf("%d%d%d", &head, &n, &k);

    for (int i = ; i < n; i++)

    {

        scanf("%d%d%d", &node[i].addr, &node[i].data, &node[i].next);

        hash[node[i].addr] = i;

    }

    int cur = head,c=;

    while (cur != -)

    {

        addr[c] = node[hash[cur]].addr;

        cur = node[hash[cur]].next;

        c++; //节点计数

    }

    n = c; //排除不在链表中的节点

    for (int i = ; i < n; i = i + k)

    {

        int r = (i + k<= n) ? i + k -  : n - ;

        if (i + k <= n)

        {

            for (int j = r; j > i; j--)

            {

                node[hash[addr[j]]].next = node[hash[addr[j - ]]].addr;

            }

            if (r == n - ) node[hash[addr[i]]].next = -;

            else node[hash[addr[i]]].next = (i +  * k <= n) ? node[hash[addr[i + *k -]]].addr : node[hash[addr[i+k]]].addr;

            if (r!=n-)

                for (int j = r; j >= i; j--) printf("%05d %d %05d\n", node[hash[addr[j]]].addr, node[hash[addr[j]]].data, node[hash[addr[j]]].next);

            else

            {

                for (int j = r; j > i; j--) printf("%05d %d %05d\n", node[hash[addr[j]]].addr, node[hash[addr[j]]].data, node[hash[addr[j]]].next);

                printf("%05d %d -1\n", node[hash[addr[i]]].addr, node[hash[addr[i]]].data);

            }

        }

        else

        {

            for (int j = i; j < n-; j++) printf("%05d %d %05d\n", node[hash[addr[j]]].addr, node[hash[addr[j]]].data, node[hash[addr[j]]].next);

            printf("%05d %d -1\n", node[hash[addr[n-]]].addr, node[hash[addr[n-]]].data);

        }

    }

}

int main()

{

    //freopen("input.txt", "r", stdin);

    PAT *p = new PAT;

    p->run();

    return ;

}

1075. PAT Judge （25）

这个题是一个常规的排序题，排序的时候仔细点。有一个要注意的地方是，如果提交了没有编译通过，submit里面显示的分数是-1，但是最终输出要输出为0。

#include <iostream>

#include <algorithm>

using namespace std;

struct User

{

    int id, total, score[], rank, solved;

    bool onlist;

};

class PAT

{

public:

    enum{N=};

    User user[N];

    int fullscore[N];

    int n, k, m;

    void run();

    void printscore(const User &u);

};

bool cmp(const User &u1, const User &u2)

{

    if (u1.total != u2.total) return u1.total > u2.total;

    else if (u1.solved != u2.solved) return u1.solved > u2.solved;

    else return u1.id < u2.id;

}

void PAT::printscore(const User &u)

{

    for (int i = ; i <= k; i++)

    {

        if (u.score[i] == -) printf(" -");

        else if (u.score[i] == -) printf("");

        else printf(" %d", u.score[i]);

    }

}

void PAT::run()

{

    scanf("%d%d%d", &n, &k, &m);

    for (int i = ; i<n; i++)

    {

        user[i].id = i+;

        user[i].total = ;

        user[i].solved = ;

        user[i].onlist = false;

        for (int j = ; j <= k; j++)

            user[i].score[j] = -;

    }

    for (int i = ; i <= k; i++) scanf("%d", &fullscore[i]);

    int tid, tpid, tscore;

    while (m-- > )

    {

        scanf("%d%d%d", &tid, &tpid, &tscore);

        if (user[tid-].score[tpid] < tscore) user[tid-].score[tpid] = tscore;

    }

    for (int i = ; i < n; i++)

    {

        for (int j = ; j <= k; j++)

        {

            if (user[i].score[j] >= )

            {

                user[i].total += user[i].score[j]; user[i].onlist = true;

            }

            if (user[i].score[j] == fullscore[j]) user[i].solved++;

        }

    }

    sort(user, user + n, cmp);

    user[].rank = ;

    for (int i = ; i < n; i++)

    {

        if (user[i].total == user[i - ].total) user[i].rank = user[i - ].rank;

        else user[i].rank = i+;

    }

    for (int i = ; i < n; i++)

    {

        if (user[i].onlist)

        {

            printf("%d %05d %d", user[i].rank, user[i].id, user[i].total);

            printscore(user[i]);

            printf("\n");

        }

        else break;

    }

}

int main()

{

    //freopen("input.txt", "r", stdin);

    PAT *p = new PAT;

    p->run();

    return ;

}

1076. Forwards on Weibo (30)

这个题直接用BFS搜索遍历即可。

#include <iostream>

#include <vector>

using namespace std;

class PAT

{

public:

    enum{N=};

    vector<int> fans[N];

    vector<int> curfans;

    int vis[N];

    int n, level, k;

    void run();

    void bfs(int);

    int maxforward;

};

void PAT::run()

{

    scanf("%d%d", &n, &level);

    int tnum,tfol;

    for (int i = ; i <= n; i++)

    {

        scanf("%d", &tnum);

        while (tnum-- > )

        {

            scanf("%d", &tfol);

            fans[tfol].push_back(i);

        }

    }

    scanf("%d", &k);

    int qnum;

    while (k-- > )

    {

        scanf("%d", &qnum);

        fill(vis, vis + N, );

        curfans.clear();

        maxforward = ;

        vis[qnum] = ;

        int fansize = fans[qnum].size();

        for (int i = ; i < fansize; i++)

        {

            curfans.push_back(fans[qnum][i]);

            vis[fans[qnum][i]] = ;

        }

        bfs(level);

        printf("%d\n", maxforward);

    }

}

void PAT::bfs(int l)

{

    if (l == ) return;

    if (curfans.empty()) return;

    int fansize = curfans.size();

    maxforward += fansize;

    vector<int> tmp;

    for (int i = ; i < fansize; i++)

    {

        int fansize2 = fans[curfans[i]].size();

        vector<int> &cur = fans[curfans[i]];

        for (int j = ; j < fansize2; j++)

        {

            if (vis[cur[j]] == ) {

                tmp.push_back(cur[j]); vis[cur[j]] = ;

            }

        }

    }

    curfans.clear();

    curfans.resize(tmp.size());

    copy(tmp.begin(), tmp.end(), curfans.begin());

    bfs(l-);

}

int main()

{

    //freopen("input.txt", "r", stdin);

    PAT *p = new PAT;

    p->run();

    return ;

}

巴特西

2014-03-01 春季PAT 1073-1076解题报告

最新文章

热门文章