1116 判斷素數(shù) STL

題目大意： 冠軍會得到 "Mystery Award" 父晶，排名為素數(shù)的人得到 the Minions 。其他人得到 chocolates履羞。給你比賽排名以及參賽者的id，請你找出大家都的什么獎。

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<iomanip>
using namespace std;

bool isprime(int num){
    if(num == 2 || num == 3){
        return true;
    }
    for(int i = 2; i*i <= num; i++){
        if(num % i == 0){
            return false;
        }
    }
    return true;
}

int main(){
    int n; // <=10000 參賽者數(shù)量
    cin>>n;
    map<int, int> mp;
    string award[4] = {"Are you kidding?", "Mystery Award", "Minion", "Chocolate"};
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(i == 1){
            mp[x] = 1;
        }else if(isprime(i)){
            mp[x] = 2;
        }else{
            mp[x] = 3;
        }
    } 
    int k;
    cin>>k;
    set<int> name;
    for(int i=0;i<k;i++){
        int x;
        cin>>x;
        if(mp[x] != 0){
            if(name.find(x) == name.end()){
                cout<<setw(4)<<setfill('0')<<x<<": "<<award[mp[x]]<<endl;
                name.insert(x);
            }else{
                cout<<setw(4)<<setfill('0')<<x<<": Checked"<<endl;
            }
        }else{
            cout<<setw(4)<<setfill('0')<<x<<": "<<award[mp[x]]<<endl;
        }
    }
    return 0;
}

1117 邏輯題

題目大意： 找到最大的整數(shù)E桥帆，使得有E天（不一定連續(xù)）騎車超過E英里赖淤。給你一個人N天每天走的公里數(shù)蜀漆，找到E .
思路： 首先將公里數(shù)從大到小進行排序，找到第一個公里數(shù)<天數(shù) 的值咱旱。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
    return a >= b;
}
int main(){
    int n, i; //n<=10^5
    cin>>n;
    vector<int> v(n);
    for(i=0;i<n;i++){
        cin>>v[i];  
    }
    sort(v.begin(), v.end(),cmp);
    i = 0;
    while(i<n && v[i] > i+1) i++;
    /* 錯誤 
    for(int i = 0; i<n; i++){
        if( v[i] < i+1){
            break;
        }
    }
    */
    cout<<i;
    return 0;
}

1118 并查集

題目大意： 給出一些鳥的集合确丢，計算其并查集，輸出總共有多少個集合和多少只鳥吐限。再判斷輸入的兩只鳥是不是屬于同一個集合鲜侥。

#include<iostream>
using namespace std;

int a[10005];
int n; // <= 10^4
bool visit[10005];

int find(int x){
    if(a[x] == -1) return x;
    return a[x] = find(a[x]); // 路徑壓縮 
}

int main(){
    
    cin>>n;
    fill(a, a+10005, -1);
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        int s,t;
        cin>>s;
        visit[s] = true;
        for(int j=1;j<k;j++){
            cin>>t;
            visit[t] = true;
            int ss = find(s);
            int tt = find(t);
            if(ss != tt){
                a[ss] = tt;
            }
            s = t;
        }
    }
    
    int sum = 0, birdnum = 0;
    for(int i=0;i<10005;i++){
        if(visit[i] == true && a[i] == -1){
            sum++;
        }
        if(visit[i] == true){
            birdnum++;
        }
    }

    cout<<sum<<" "<<birdnum<<endl;
    
    int q; // <= 10^4
    cin>>q;
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        if(find(a) == find(b)){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

1119 二叉樹

題目大意： 給出后序和先序，輸出中序诸典。若不唯一描函，輸出任何一個可能值。
思路： 根據(jù)后序和先序，遞歸構成中序舀寓，若有多種情況胆数，則當作右子樹處理。
以下方法是錯的：

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int n; //<=30
vector<int> pre;
vector<int> post;
vector<int> in;
bool flag = true; // 標記是否唯一 
stack<int> s;

void reverse(int prep, int preq, int postp, int postq){
    if(prep > preq || postp > postq || prep<0 || preq>=n || postp<0 || postq >=n){
        return;
    }
    if(prep == preq){
        in.push_back(pre[prep]);
        if(s.size()!=0){
            in.push_back(s.top());
            s.pop();
        }
        return;
    }
    s.push(pre[prep]);//將根節(jié)點放入棧 
    if(pre[prep+1] == post[postq-1]){
        flag = false;
        reverse(prep+1, preq, postp, postq-1);
    }else{
        //尋找根節(jié)點 
        int rroot;
        for(int i = prep+2; i<=preq; i++){
            if(pre[i] == post[postq-1]){
                rroot = i;
                break;
            }
        }
        reverse(prep+1, rroot-1, postp, postp + rroot - prep -1 -1);
        reverse(rroot, preq, postp + rroot - prep -1, postq-1);
    }
}

int main(){
    
    cin>>n;
    
    pre.resize(n+1);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        pre[i] = x; 
    }
    post.resize(n+1);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        post[i] = x; 
    }
    //in.resize(n+1); 因為之前用的push_back所以初始化之后是在0后面添加 
    reverse(0,n-1,0,n-1);
    while(s.size()!=0){
        in.push_back(s.top());
        s.pop();
    }
    if(flag){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    for(int i=0;i<in.size();i++){
        if(i != 0){
            cout<<" ";
        }
        cout<<in[i];
    }
    return 0;
}

正確方法是這樣的：

#include <iostream>
#include <vector>
using namespace std;
vector<int> in, pre, post;
bool unique = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight) {
    if(preLeft == preRight) {
        in.push_back(pre[preLeft]);
        return;
    }
    if (pre[preLeft] == post[postRight]) {
        int i = preLeft + 1;
        while (i <= preRight && pre[i] != post[postRight-1]) i++;
        if (i - preLeft > 1)
            getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
        else
            unique = false;
        in.push_back(post[postRight]);
        getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n), post.resize(n);
    for (int i = 0; i < n; i++) 
        scanf("%d", &pre[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &post[i]);
    getIn(0, n-1, 0, n-1);
    printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);
    for (int i = 1; i < in.size(); i++)
        printf(" %d", in[i]);
    printf("\n");
    return 0;
}

PAT A 1116 1117 1118 1119

PAT A 1116 1117 1118 1119

1116 判斷素數(shù) STL

1117 邏輯題

1118 并查集

1119 二叉樹