魔鬼PAT训练DAY2

3.6. 字符串处理

B1006.换个格式输出整数(15')

#include <iostream>
using namespace std;
int main() {
    int num;
    scanf("%d", &num);
    int g = num % 10;
    int s = num / 10 % 10;
    int b = num / 100;
    while(b--) putchar('B');
    while(s--) putchar('S');
    for(int i = 1; i <= g; i++) putchar(i + '0');
    return 0;
}

B1021.各位数统计(15')

#include <iostream>
using namespace std;
int main() {
    int cnt[10] = {0};
    string str;
    cin >> str;
    for(auto x: str) cnt[x - '0']++;
    for(int i = 0; i < 10; i++)
        if(cnt[i] != 0) printf("%d:%d\n", i, cnt[i]);
    return 0;
}

B1031.查验身份证(15')

#include <iostream>
using namespace std;
int weight[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
char m[] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
int main() {
    int N, vali, flag = 1;
    string tmp;
    scanf("%d", &N);
    while(N--) {
        vali = 0;
        cin >> tmp;
        for(int i = 0; i < 17; i++)
            vali = vali + (tmp[i] - '0') * weight[i];
        vali = vali % 11;
        if(m[vali] != tmp[17]) {
            cout << tmp << endl;
            flag = 0;
        }
    }
    if(flag) cout << "All passed" << endl;
    system("pause");
    return 0;
}

B1002.写出这个数 (20')

#include <iostream>
using namespace std;
string m[] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
int main() {
    int sum = 0;
    string str, str_sum;
    cin >> str;
    for(int i = 0; i < str.size(); i++)
        sum += (str[i] - '0');
    str_sum = to_string(sum);
    cout << m[str_sum[0] - '0'];
    for(int i = 1; i < str_sum.size(); i++)
        cout << " " << m[str_sum[i] - '0'];
    return 0;
}

B1009.说反话(20')

#include <iostream>
using namespace std;
int main() {
    string str[1000], tmp;
    int index = 0;
    while(cin >> tmp) str[index++] = tmp;
    while(index--)
        if(index == 0) cout << str[index];
        else cout << str[index] << " ";
    return 0;
}

B1014/A1061.福尔摩斯的约会(20')

#include <iostream>
using namespace std;
string week[] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
int main() {
    string a, b, c, d;
    getline(cin, a); getline(cin, b);
    getline(cin, c); getline(cin, d);
    int i = 0;
    while(!(a[i] >= 'A' && a[i] <= 'G' && a[i] == b[i])) i++;
    cout << week[a[i++] - 'A'];
    while(!((isdigit(a[i]) || (a[i] >= 'A' && a[i] <= 'N')) && a[i] == b[i])) i++;
    int h = isalpha(a[i]) ? a[i] - 'A' + 10: a[i] - '0' ;
    i = 0;
    while(!(isalpha(c[i]) && c[i] == d[i])) i++;
    printf(" %02d:%02d", h, i);
    return 0;
}

B1024/A1073.科学计数法(20')

#include <iostream>
#include <deque>
using namespace std;
int main() {
    string str, move;
    getline(cin, str);
    deque<char> de, xi;
    if(str[0] == '-') putchar('-');
    int i = 1;
    while(isdigit(str[i])) de.push_back(str[i++]);
    i++;
    while(isdigit(str[i])) xi.push_back(str[i++]);
    i++;
    move = str[i++] == '-' ? "left": "right";
    int num = 0; // move_num
    while(i < str.size()) num = num * 10 + (str[i++] - '0');
    while(num--) {
        if(move == "left") {
            if(de.size() != 0) {
                xi.push_front(de.back());
                de.pop_back();
            } else xi.push_front('0');
        }else {
            if(xi.size() != 0) {
                de.push_back(xi.front());
                xi.pop_front();
            } else de.push_back('0');
        }
    }
    if(de.size() != 0) for(auto x: de) putchar(x);
    else putchar('0');
    if(xi.size() != 0) putchar('.');
    for(auto x: xi) putchar(x);
    return 0;
}

B1048.数字加密(20')

#include <iostream>
#include <deque>
using namespace std;
char m[] = "0123456789JQK";
int main() {
    deque<char> d;
    string A, B;
    cin >> A >> B;
    if(A.size() < B.size()) while(A.size() != B.size()) A = "0" + A;
    else while(A.size() != B.size()) B = "0" + B;
    for(int i = A.size() -1, j = 1; i >= 0; i--, j++)
        if(j % 2 == 1) d.push_front(m[(A[i] - '0' + B[i] - '0') % 13]);
        else d.push_front(B[i] - A[i] < 0 ? (B[i] - A[i] + 10 + '0'): (B[i] - A[i] + '0'));
    for(auto x: d) putchar(x);
    return 0;
}

A1001.A+B Format(20')

#include <iostream>
#include <deque>
using namespace std;
int main() {
    int a, b, first = 0, index = 0;
    deque<char> deq;
    scanf("%d%d", &a, &b);
    string ans = to_string(a + b);
    for(int i = 0; i < ans.size(); i++) deq.push_back(ans[i]);
    if(deq[0] == '-') {
        putchar('-');
        deq.pop_front();
    }
    while(deq.size()) {
        putchar(deq[0]);
        deq.pop_front();
        if(deq.size() % 3 == 0 && deq.size()) putchar(',');
    }
    return 0;
}

A1005.Spell It Right(20')

#include <iostream>
using namespace std;
string m[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
int main() {
    int sum = 0;
    string str, str_sum;
    getline(cin, str);
    for(int i = 0; i < str.size(); i++)
        sum += (str[i] - '0');
    str_sum = to_string(sum);
    printf("%s", m[str_sum[0] - '0'].data());
    for(int i = 1; i < str_sum.size(); i++)
        printf(" %s", m[str_sum[i] - '0'].data());
    system("pause");
    return 0;
}

A1035.Password(20')

#include <iostream>
#include <map>
using namespace std;
map<char, char> m;
int main() {
    int N, modicoun = 0;
    string user, pw, res;
    scanf("%d", &N);
    m['l'] = 'L'; m['O'] = 'o'; m['1'] = '@'; m['0'] = '%';
    for(int j = 0; j < N; j++) {
        bool modi = false;
        cin >> user >> pw;
        for(int i = 0; i < pw.length(); i++){
            if(m[pw[i]] != 0) {
                pw[i] = m[pw[i]];
                modi = true;
            }
        }
        if(modi) {
            res = res + user + " " + pw + "\n";
            modicoun++;
        }
    }
    if(!modicoun) 
        if(N != 1) printf("There are %d accounts and no account is modified", N);
        else printf("There is 1 account and no account is modified");
    else printf("%d\n%s", modicoun, res.c_str());
    return 0;
}

A1077.Kuchiguse(20')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string tmp, ans;
vector<string> v;
int main() {
    int N;
    scanf("%d\n", &N);
    for(int i = 0; i < N; i++) {
        getline(cin, tmp);
        reverse(tmp.begin(), tmp.end());
        v.push_back(tmp);
    }
    for(int i = 0; i < v[0].size(); i++){
        int cnt = 0;
        for(int j = 0; j < N; j++)
            if(v[j][i] == v[0][i]) cnt++;
            else break;
        if(cnt == N) ans = v[0][i] + ans;
        else break;
    }
    if(ans != "") cout << ans;
    else cout << "nai";
    return 0;
}

A1082.Read Number in Chinese(25')

难改，注意1001(yi qian ling yi), 101(yi bai ling yi), 10010(yi wan ling yi shi)，策略：反复修bug。

#include <iostream>
using namespace std;
string ans;
bool bef = false;
string ge[] = {" ling", " yi", " er", " san", " si", " wu", " liu", " qi", " ba", " jiu"};
void show(int num) {
    bool flag = false;
    if(num / 1000 != 0) ans = ans + ge[num / 1000] + " Qian";
    else if(bef) {
        ans += ge[0];
        bef = true;
    }
    if(num % 1000 / 100 != 0) ans = ans + ge[num % 1000 / 100] + " Bai";
    if(num / 1000 != 0 && num % 1000 / 100 == 0) flag = true;
    if(num % 100 / 10 != 0) {
        if(flag) ans += ge[0];
        ans = ans + ge[num % 100 / 10] + " Shi";
    }
    if((num / 1000 != 0 || num % 1000 / 100 != 0) && num % 100 / 10 == 0) flag = true;
    if(num % 10 != 0) {
        if(flag) ans += ge[0];
        ans += ge[num % 10];
    }
}
int main() {
    int N;
    scanf("%d", &N);
    if(N < 0) ans = ans + " Fu";
    if(N == 0) ans += ge[0];
    N = abs(N);
    int yi = N / 100000000;
    int wan = N % 100000000 / 10000;
    int rel = N % 10000;
    if(yi != 0) {
        ans = ans + ge[yi] + " Yi";
        bef = true;
    }
    if(wan != 0) {
        show(wan);
        ans += " Wan";
        bef = true;
    }
    if(rel != 0) show(rel);
    cout << ans.substr(1);
    return 0;
}

B1015/A1062.德才论(25')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct peo {
    string id;
    int tal, vir, level, all;
};
bool cmp(peo& p1, peo& p2) {
    if(p1.level != p2.level) return p1.level < p2.level;
    if(p1.all != p2.all) return p1.all > p2.all;
    if(p1.vir != p2.vir) return p1.vir > p2.vir;
    return p1.id < p2.id;
}
int main() {
    int N, L, H;
    vector<peo> v;
    peo tmp;
    scanf("%d%d%d", &N, &L, &H);
    while(N--) {
        cin >> tmp.id >> tmp.vir >> tmp.tal;
        tmp.all  = tmp.tal + tmp.vir;
        if(tmp.tal >= L && tmp.vir >= L) {
            if(tmp.tal >= H && tmp.vir >= H) tmp.level = 1;
            else if(tmp.vir >= H) tmp.level = 2;
            else if(tmp.vir >= tmp.tal) tmp.level = 3;
            else tmp.level = 4;
            v.push_back(tmp);
        }
    }
    sort(v.begin(), v.end(), cmp);
    printf("%d\n", v.size());
    for(auto x: v) printf("%s %d %d\n", x.id.data(), x.vir, x.tal);
    return 0;
}

A1012.The Best Rank(25')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct stu {
    string id;
    int score[4],r[4];
};
int choice;
bool cmp(stu s1, stu s2) {
    return s1.score[choice] > s2.score[choice];
}
vector<stu> v;
int main() {
    int M, N;
    cin >> M >> N;
    stu tmp;
    for(int i = 0; i < M; i++) {
        cin >> tmp.id >> tmp.score[0] >> tmp.score[1] >> tmp.score[2];
        tmp.score[3] = tmp.score[0] + tmp.score[1] + tmp.score[2];
        v.push_back(tmp);
    }
    for(choice = 0; choice < 4; choice++) {
        sort(v.begin(), v.end(), cmp);
        v[0].r[choice] = 1;
        for(int i = 1; i < M; i++)
            if(v[i].score[choice] == v[i-1].score[choice]) v[i].r[choice] = v[i-1].r[choice];
            else v[i].r[choice] = i + 1;
    }
    while(N--) {
        cin >> tmp.id;
        int i;
        for(i = 0; i < M; i++) if(tmp.id == v[i].id) break;
        if(i == M) {
            printf("N/A\n");
            continue;
        }
        int a = v[i].r[3],c = v[i].r[0],m = v[i].r[1],e = v[i].r[2];
        if(a <= c && a <= m && a <= e) printf("%d A\n", a);
        else if(c <= a && c <= m && c <= e) printf("%d C\n", c);
        else if(m <= c && m <= a && m <= e) printf("%d M\n", m);
        else if(e <= c && e <= m && e <= a) printf("%d E\n", e);
    }
    return 0;
}

A1016.Phone Bills(25') 卡题

A1025.PAT Ranking(25')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct people {
    string id;
    int fr, ln, lr, score;
};
vector<vector<people>> v;
vector<people> res;
bool cmp(people& p1, people& p2){
    return p1.score == p2.score ? p1.id < p2.id: p1.score > p2.score;
}
int main(){
    int N, M;
    cin >> N;
    v.resize(N);
    people tmp;
    for(int i = 0; i < N; i++){
        cin >> M;
        tmp.ln = i + 1;
        while(M--) {
            cin >> tmp.id >> tmp.score;
            v[i].push_back(tmp);
        }
        sort(v[i].begin(), v[i].end(), cmp);
        if(v[i].size() != 0){
            v[i][0].lr = 1;
            for(int j = 2; j <= v[i].size(); j++)
                if(v[i][j-1].score != v[i][j-2].score) v[i][j-1].lr = j;
                else v[i][j-1].lr = v[i][j-2].lr;
        }
    }
    for(int i = 0;i < v.size(); i++)
        for(int j = 0;j < v[i].size(); j++)
            res.push_back(v[i][j]);
    sort(res.begin(), res.end(), cmp);
    res[0].fr = 1;
    for(int i = 2;i <= res.size(); i++)
        if(res[i-1].score != res[i-2].score) res[i-1].fr = i;
        else res[i-1].fr = res[i-2].fr;
    cout << res.size() << endl;
    for(int i = 0; i < res.size(); i++)
        cout << res[i].id << " " << res[i].fr << " "
            << res[i].ln << " " << res[i].lr << endl;
    return 0;
}

A1028.List Sorting(25')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int choose;
bool cmp(vector<string>& s, vector<string>& s2){
    return s[choose] == s2[choose] ? s[1] < s2[1]: s[choose] < s2[choose];
}
int main() {
    int M;
    cin >> M >> choose;
    vector<string> s[M];
    for(int  i= 0; i < M; i++){
        s[i].resize(4);
        cin >> s[i][1] >> s[i][2] >> s[i][3];
    }
    sort(s, s+M, cmp);
    for(int  i= 0; i < M; i++)
        printf("%s %s %s\n", s[i][1].data(),
               s[i][2].data(), s[i][3].data());
    return 0;
}

A1055.The World's Richest(25')

#include <iostream>
#include <algorithm>
using namespace std;
struct peo {
    string name;
    int age, net_worth;
}v[100005];
int N, K, M, after_m, _max, _min, p = 0;
bool cmp(peo p1, peo p2) {
    if(p1.net_worth != p2.net_worth) return p1.net_worth > p2.net_worth;
    if(p1.age != p2.age) return p1.age < p2.age;
    return p1.name < p2.name;
}
int main() {
    scanf("%d%d", &N, &K);
    while(N--) {
        v[p].name.resize(10);
        scanf("%s%d%d", v[p].name.c_str(), &v[p].age, &v[p].net_worth);
        p++;
    }
    sort(v, v + p, cmp);
    for(int i = 1; i <= K; i++) {
        scanf("%d%d%d", &M, &_min, &_max);
        printf("Case #%d:\n", i);
        after_m = M;
        for(int j = 0; j < p; j++)
            if(v[j].age >= _min && v[j].age <= _max)
                if(after_m--) printf("%s %d %d\n", v[j].name.c_str(), v[j].age, v[j].net_worth);
                else break;
        if(M == after_m) printf("None\n");
    }
    return 0;
}

A1075.卡

A1083.List Grades(25')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct peo {
    string name;
    int score;
};
vector<peo> v;
bool cmp(peo& p1, peo& p2) {
    return p1.score == p2.score ? p1.name < p2.name: p1.score > p2.score;
}
int main() {
    int N, low , high, flag = 0;
    string tmp1, tmp2;
    peo tmp;
    scanf("%d", &N);
    while(N--) {
        cin >> tmp1 >> tmp2 >> tmp.score;
        tmp.name = tmp1 + " " + tmp2;
        v.push_back(tmp);
    }
    scanf("%d%d", &low, &high);
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < v.size(); i++)
        if(v[i].score >= low && v[i].score <= high){
            cout << v[i].name << endl;
            flag = 1;
        }
    if(!flag) cout << "NONE" << endl;
    return 0;
}

A10800.Graduate Admission(30')

A1095.Cars on Carpus(30')

4.2.散列

B1029/A1084. 旧键盘

#include <iostream>
using namespace std;
int main() {
    string a, b, ans;
    cin >> a >> b;
    bool flag = false;
    for(int i = 0; i < a.length(); i++)
        if(b.find(a[i]) == b.npos && ans.find(toupper(a[i])) == a.npos)
            ans += toupper(a[i]);
    cout << ans;
    return 0;
}

B1033.旧键盘打字

#include <iostream>
using namespace std;
int main() {
    string bad, str;
    bool canUpper=true;
    getline(cin, bad); getline(cin, str);
    for(int i = 0; i < bad.length(); i++) bad[i] = toupper(bad[i]);
    if(bad.find('+')!=bad.npos) canUpper=false;
    if(canUpper){
       for(int i=0;i<str.length();i++)
            if(bad.find(toupper(str[i]))==bad.npos)
                cout<<str[i];
    }else{
        for(int i=0;i<str.length();i++)
            if(bad.find(toupper(str[i]))==bad.npos&&(islower(str[i])||!isalpha(str[i])))
                cout<<str[i];
    }
    printf("\n");
    return 0;
}

B1038.统计同成绩学生(20')

#include <iostream>
using namespace std;
int main() {
    int N, M, tmp, cnt[110] = {0};
    scanf("%d", &N);
    while(N--) {
        scanf("%d", &tmp);
        cnt[tmp]++;
    }
    scanf("%d", &M);
    while(M--) {
        scanf("%d", &tmp);
        printf("%d", cnt[tmp]);
        if(M != 0) putchar(' ');
    }
    return 0;
}

B1039/A1092.到底买不买

#include <iostream>
#include <map>
using namespace std;
map<char, int> m;
string str1, str2;
int main() {
    int q = 0;
    getline(cin, str1); getline(cin, str2);
    for(int i = 0; i < str1.size(); i++)
        m[str1[i]]++;
    for(int i = 0; i < str2.size(); i++)
        if(m[str2[i]] != 0) m[str2[i]]--;
        else q++;
    if(q != 0) cout << "No " << q;
    else{
        for(auto it = m.begin(); it != m.end(); it++)
            q += it->second;
        cout << "Yes " << q;
    }
    return 0;
}

B1042.字符统计(20')

#include <iostream>
using namespace std;
int a[200] = {0};
string str; char m; int mv=0;
int main() {
    getline(cin, str);
    for(int i = 0; i < str.length(); i++)
        if(isalpha(str[i])) a[tolower(str[i])]++;
    for(int i = 0;i < 200; i++)
    if(a[i] > mv){
        m = (char)i;
        mv = a[i];
    }
    cout << m << " " << mv;
    return 0;
}

B1043.输出PATest(20')

#include <iostream>
using namespace std;
int main() {
    string str = "PATest", tmp;
    int cnt[6] = {0};
    getline(cin, tmp);
    for(int i = 0; i < tmp.size(); i++)
        if(str.find(tmp[i]) != str.npos)
            cnt[str.find(tmp[i])]++;
    while(1) {
        int c = 0;
        for(int i = 0; i < 6; i++) {
            if(cnt[i] != 0) {
                cnt[i]--;
                putchar(str[i]);
            } else c++;
        }
        if(c == 6) break;
    }
    return 0;
}

B1047.编程团体赛(20')

#include <iostream>
using namespace std;
int main() {
    int N, a, b, c, mk, mv = 0;
    scanf("%d", &N);
    int m[1010] = {0};
    while(N--) {
        scanf("%d-%d %d", &a, &b, &c);
        m[a] += c;
    }
    for(int i = 0; i < 1000; i++)
        if(mv < m[i]) {
            mv = m[i];
            mk = i;
        }
    cout << mk << " " << mv;
    return 0;
}

A1041.Be Unique(20')

#include <iostream>
using namespace std;
int m[10000] = {0};
int main(){
    int N;
    cin >> N;
    int arr[N];
    for(int i = 0; i < N; i++){
        cin >> arr[i];
        m[arr[i]]++;
    }
    for(int i = 0; i < N; i++){
        if(m[arr[i]] == 1){
            cout << arr[i];
            return 0;
        }
    }
    cout << "None";
    return 0;
}

A1050.String Subtraction(20')

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<char, bool> m;
int main() {
    string str, pattern, res;
    getline(cin, str); getline(cin, pattern);
    for(int i = 0; i < pattern.length(); i++) m[pattern[i]] = 1;
    for(int i = 0; i < str.length(); i++)
        if(!m[str[i]]) res += str[i];
    cout << res;
    return 0;
}

B1005.继续3n+1猜想(25')

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, bool, greater<int>> m, m2;
vector<int> v;
void callatz(int N) {
    while(N != 1) {
        if(N % 2 == 0) N /= 2;
        else N = (3 * N + 1) / 2;
        m[N] = 0; m2[N] = 0;
    }
}
int main() {
    int N, tmp;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &tmp);
        m[tmp] = 1;
    }
    for(auto it = m.begin(); it != m.end(); it++)
        if(it->second) {
            m2[it->first] = 1;
            callatz(it->first);
        }
    for(auto x: m2) if(x.second) v.push_back(x.first);
    printf("%d", v[0]);
    for(int i = 1; i < v.size(); i++)
        printf(" %d", v[i]);
    return 0;
}

A1048.Find Coins(25')

#include <iostream>
#include <map>
using namespace std;
int main() {
    int N, M, tmp;
    map<int, int> m;
    scanf("%d%d", &N, &M);
    while(N--) {
        scanf("%d", &tmp);
        m[tmp]++;
    }
    for(auto it = m.begin(); it != m.end(); it++) {
        it->second--;
        if(m[M - it->first]) {
            printf("%d %d", it->first, M - it->first);
            return 0;
        }
    }
    printf("No Solution");
    return 0;
}