1095 解碼PAT準考證 （25 分）1153 Decode Registration Card of PAT （25 分）

PAT 準考證号由 4 部分組成：

• 第 1 位是級别，即 

  T

   代表頂級；

  A

   代表甲級；

  B

   代表乙級；
• 第 2~4 位是考場編号，範圍從 101 到 999；
• 第 5~10 位是考試日期，格式為年、月、日順次各占 2 位；
• 最後 11~13 位是考生編号，範圍從 000 到 999。

現給定一系列考生的準考證号和他們的成績，請你按照要求輸出各種統計資訊。

輸入格式：

輸入首先在一行中給出兩個正整數 N（≤10​4​​）和 M（≤100），分别為考生人數和統計要求的個數。

接下來 N 行，每行給出一個考生的準考證号和其分數（在區間 [0,100] 内的整數），其間以空格分隔。

考生資訊之後，再給出 M 行，每行給出一個統計要求，格式為：

類型 指令

，其中

• 類型

   為 1 表示要求按分數非升序輸出某個指定級别的考生的成績，對應的 

  指令

   則給出代表指定級别的字母；

• 類型

   為 2 表示要求将某指定考場的考生人數和總分統計輸出，對應的 

  指令

   則給出指定考場的編号；

• 類型

   為 3 表示要求将某指定日期的考生人數分考場統計輸出，對應的 

  指令

   則給出指定日期，格式與準考證上日期相同。

輸出格式：

對每項統計要求，首先在一行中輸出 

Case #: 要求

，其中 

#

 是該項要求的編号，從 1 開始；

要求

 即複制輸入給出的要求。随後輸出相應的統計結果：

• 類型

   為 1 的指令，輸出格式與輸入的考生資訊格式相同，即 

  準考證号 成績

  。對于分數并列的考生，按其準考證号的字典序遞增輸出（題目保證無重複準考證号）；

• 類型

   為 2 的指令，按 

  人數 總分

   的格式輸出；

• 類型

   為 3 的指令，輸出按人數非遞增順序，格式為 

  考場編号 總人數

  。若人數并列則按考場編号遞增順序輸出。

如果查詢結果為空，則輸出 

NA

。

輸入樣例：

8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999
           

輸出樣例：

Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA
           

 英文題：

A registration card number of PAT consists of 4 parts:

• the 1st letter represents the test level, namely, 

  T

   for the top level, 

  A

   for advance and 

  B

   for basic;
• the 2nd - 4th digits are the test site number, ranged from 101 to 999;
• the 5th - 10th digits give the test date, in the form of 

  yymmdd

  ;
• finally the 11th - 13th digits are the testee's number, ranged from 000 to 999.

Now given a set of registration card numbers and the scores of the card owners, you are supposed to output the various statistics according to the given queries.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤10​4​​) and M (≤100), the numbers of cards and the queries, respectively.

Then N lines follow, each gives a card number and the owner's score (integer in [0,100]), separated by a space.

After the info of testees, there are M lines, each gives a query in the format 

Type Term

, where

• Type

   being 1 means to output all the testees on a given level, in non-increasing order of their scores. The corresponding 

  Term

  will be the letter which specifies the level;

• Type

   being 2 means to output the total number of testees together with their total scores in a given site. The corresponding 

  Term

   will then be the site number;

• Type

   being 3 means to output the total number of testees of every site for a given test date. The corresponding 

  Term

   will then be the date, given in the same format as in the registration card.

Output Specification:

For each query, first print in a line 

Case #: input

, where 

#

 is the index of the query case, starting from 1; and 

input

 is a copy of the corresponding input query. Then output as requested:

• for a type 1 query, the output format is the same as in input, that is, 

  CardNumber Score

  . If there is a tie of the scores, output in increasing alphabetical order of their card numbers (uniqueness of the card numbers is guaranteed);
• for a type 2 query, output in the format 

  Nt Ns

   where 

  Nt

   is the total number of testees and 

  Ns

   is their total score;
• for a type 3 query, output in the format 

  Site Nt

   where 

  Site

   is the site number and 

  Nt

   is the total number of testees at 

  Site

  . The output must be in non-increasing order of 

  Nt

  's, or in increasing order of site numbers if there is a tie of 

  Nt

  .

If the result of a query is empty, simply print 

NA

.

Sample Input:

8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999
           

Sample Output:

Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA
           

分析：

      給出一組學生的準考證号和成績，準考證号包含了等級(乙甲頂)，考場号，日期，和個人編号資訊，并有三種查詢方式

      類型一：給出考試等級，找出相應等級的考生，輸出按照分數降序，準考證升序排序

      類型二：給出考場号，統計該考場的考生人數和總分統計，輸出按人數 總分格式

      類型三：給出指定考試日期，查詢該日期下所有考場的考生人數，輸出按照人數降序，考場号升序排序

先把所有考生的準考證和分數用結構體存儲下來

類型一：按照等級查詢，枚舉選取比對的學生，然後排序即可

類型二：按照考場查詢，枚舉選取比對的學生，然後計數、求和

類型三：按日期查詢每個考場人數，用unordered_map存儲，最後排序彙總

代碼如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct  node {
    string  id;
    int value;
};

bool cmp (const node &a,const node &b)
{
    return a.value!=b.value?a.value>b.value:a.id<b.id;
}

int main()
{
    int N,M,type;
    string s;
    cin>>N>>M;
    vector<node> v(N);
    for (int i=0;i<N;i++)
    {
        cin>>v[i].id>>v[i].value;
    }
    for (int i=1;i<=M;i++)
    {
        cin>>type>>s;
        printf("Case %d: %d %s\n",i,type,s.c_str());
        vector<node> ans;
        int cnt=0,sum=0;
        if (type==1){
            for (int j=0;j<N;j++)
                if (v[j].id[0]==s[0])  ans.push_back(v[j]);
        }
        else if (type==2){
            for (int j=0;j<N;j++){
            if (v[j].id.substr(1,3)==s){
                cnt++;
                sum=sum+v[j].value;
            }
        }
        if(cnt!=0)  printf ("%d %d\n",cnt,sum);
    }
    else if (type==3) {
         unordered_map<string, int> m;
        for (int j=0;j<N;j++){
            if(v[j].id.substr(4,6)==s)
                m[v[j].id.substr(1,3)]++;
        }
        for (auto it : m)
            ans.push_back({it.first, it.second});
    }
    sort (ans.begin(),ans.end(),cmp);
    for (int j=0;j<ans.size();j++)
        printf ("%s %d\n",ans[j].id.c_str(),ans[j].value);
    if(((type==1||type==3)&&ans.size()==0)||(type==2&&cnt==0))
        cout<<"NA"<<endl;
    }
 return 0;
}
           

其他：

     map： map内部實作了一個紅黑樹（紅黑樹是非嚴格平衡二叉搜尋樹，而AVL是嚴格平衡二叉搜尋樹），紅黑樹具有自動排序的功能，是以map内部的所有元素都是有序的，紅黑樹的每一個節點都代表着map的一個元素。是以，對于map進行的查找，删除，添加等一系列的操作都相當于是對紅黑樹進行的操作。map中的元素是按照二叉搜尋樹（又名二叉查找樹、二叉排序樹，特點就是左子樹上所有節點的鍵值都小于根節點的鍵值，右子樹所有節點的鍵值都大于根節點的鍵值）存儲的，使用中序周遊可将鍵值按照從小到大周遊出來。

     unordered_map: unordered_map内部實作了一個哈希表（也叫散清單，通過把關鍵碼值映射到Hash表中一個位置來通路記錄，查找的時間複雜度可達到O(1)，其在海量資料進行中有着廣泛應用）。是以，其元素的排列順序是無序的。