本文共 55037 字，大约阅读时间需要 183 分钟。

排序

• C++中可以使用泛型算法 sort() / stable_sort() 进行排序，详细用法见

如果是多关键字排序，例如：

1. 如果两个学生分数不相同， 那么分数高的排在前面
2. 否则， 将姓名字典序小的排在前面

bool cmp(Student a, Student b) {   	if(a.score != b.score) 		return a.score > b.score;	else 		return strcmp(a.name, b.name) < 0;}

• 很多排序题都会要求在排序之后计算出每个个体的排名， 并且规则一般是：分数不同的排名不同，分数相同的排名相同但占用一个排位
  • 例如有五个学生的分数分别为 90 、88 、88、88 、86, 那么这五个学生的排名分别为 1 、2 、2 、2、5
• 对这种要求， 一般都需要在结构体类型定义时就把排名这一项加到结构体中。于是在数组排序完成后就有下面两种方法来实现排名的计算：

1. 先将数组第一个个体（假设数组下标从0开始）的排名记为1, 然后遍历剩余个体：如果当前个体的分数等于上一个个体的分数， 那么当前个体的排名等于上一个个体的排名；否则， 当前个体的排名等于数组下标加1。对应的代码如下：

stu[0].r = 1;for(int i = 1; i < n; i++) {   	if(stu[i].score == stu[i - 1].score) {   		stu[i].r = stu[i - 1].r;	} else {   		stu[i].r = i + 1;	}}

2. 而有时题目中不一定需要真的把排名记录下来，而是直接输出即可，那么也可以用这样的办法： 令int 型变量r 初值为1, 然后遍历所有个体： 如果当前个体不是第一个个体且当前个体的分数不等于上一个个体的分数， 那么令r 等于数组下标加1, 这时r 就是当前个体的排名， 直接输出即可

int r = 1;for(int i = 0; i < n; i++) {   	if(i > 0 && stu[i].score != stu[i - 1].score) {   		r = i + 1;	}	//输出当前个体信息， 或者令stu[i] .r = r 也行}

PAT (Advanced level) 1012 The Best Rank

• 有一个小 trick：比较平均分时直接比较总分即可
• 如本节开始所述，计算排名时，相同分数的排名一定相同！

#include <cstdio>#include <map>#include <vector>#include <string>#include <iterator>#include <algorithm>using namespace std;struct Stu {       char id[7];    int grade[4];   // A, C, M, E    char rank_mark;    int rank = 0;};map<string, pair<int, char>> rank_map;vector<Stu> stu;int n, m;void sort_func(int idx){       int rank = 1;    map<int, char> symbol_map = {    {   0, 'A'}, {   1, 'C'}, {   2, 'M'}, {   3, 'E'} };    sort(begin(stu), end(stu), [idx](const Stu& lhs, const Stu& rhs) -> bool {           return lhs.grade[idx] > rhs.grade[idx];        });    for (int i = 0; i != n; ++i)    {           if (i != 0 && stu[i].grade[idx] != stu[i - 1].grade[idx])        {               rank = i + 1;        }        pair<int, char>& rres = rank_map[string(stu[i].id)];        if (rank < rres.first || rres.first == 0)        {               rres.first = rank;            rres.second = symbol_map[idx];        }    }}int main(int argc, const char* argv[]) {       scanf("%d %d", &n, &m);    for(size_t i = 0; i != n; ++i)    {           Stu tmp;        scanf("%s %d %d %d", tmp.id, &tmp.grade[1], &tmp.grade[2], &tmp.grade[3]);        tmp.grade[0] = tmp.grade[1] + tmp.grade[2] + tmp.grade[3];        rank_map.insert({    string(tmp.id), {   0, 'A'} });        stu.push_back(std::move(tmp));    }    for (size_t i = 0; i != 4; ++i)    {           sort_func(i);    }    while (m--)    {           char id[7];        scanf("%s", id);        if (rank_map.find(string(id)) == rank_map.end())        {               printf("N/A\n");        }        else {               pair<int, char>& rres = rank_map[string(id)];            printf("%d %c\n", rres.first, rres.second);        }    }    return 0;}

PAT (Advanced level) 1016 Phone Bills

• 这道题中关于计算两个匹配记录的持续时间，我是用的分治法。书上用的方法是将起始时间不断加1，直至到达终点时间，写起来也比较简单

#include <cstdio>#include <vector>#include <algorithm>#include <string>#include <map>using namespace std;struct Rec {       int time[3];    // day, hour, min    int flag;       // 0: on-line   1: off-line     2: void};vector<int> toll(24);long long toll_a_day = 0;  // 打一天电话的费用long long min_a_day = 24 * 60;int N, Month;map<string, vector<Rec>> Data;pair<long long, long long> calc_cost_and_time(const Rec& beg, const Rec& end){       if (beg.time[0] != end.time[0])    {           Rec tmp1 = beg;        tmp1.time[1] = 23;        tmp1.time[2] = 60;        Rec tmp2 = end;        tmp2.time[1] = 0;        tmp2.time[2] = 0;        auto res1 = calc_cost_and_time(beg, tmp1);        auto res2 = calc_cost_and_time(tmp2, end);        return  {    res1.first + res2.first + toll_a_day * (end.time[0] - beg.time[0] - 1), res1.second + res2.second + min_a_day * (end.time[0] - beg.time[0] - 1) };    }    else {           if (beg.time[1] == end.time[1])        {               return {    toll[beg.time[1]] * (end.time[2] - beg.time[2]), end.time[2] - beg.time[2] };        }        else        {               long long cost = 0, time = 0;            for (int hour = beg.time[1] + 1; hour < end.time[1]; ++hour)            {                   cost += toll[hour] * 60;                time += 60;            }            return {    cost + toll[beg.time[1]] * (60 - beg.time[2]) + toll[end.time[1]] * end.time[2],                      time + (60 - beg.time[2]) + end.time[2] };        }    }}int main(int argc, const char* argv[]) {       for (int i = 0; i != 24; ++i)    {           scanf("%d", &toll[i]);        toll_a_day += toll[i] * 60;    }    scanf("%d", &N);    for (int i = 0; i != N; ++i)    {           Rec tmp;        char name[21], state[9];        scanf("%s %d:%d:%d:%d %s", name, &Month, &tmp.time[0], &tmp.time[1], &tmp.time[2], state, 9);        tmp.flag = (state[1] == 'n') ? 0 : 1;        Data[name].push_back(std::move(tmp));    }    for (auto& customer : Data)    {           const string& name = customer.first;        vector<Rec>& rec = customer.second;        double cost = 0;        sort(rec.begin(), rec.end(), [](const Rec& lhs, const Rec& rhs) -> bool {               return (lhs.time[0] * 1e4 + lhs.time[1] * 1e2 + lhs.time[2]) < (rhs.time[0] * 1e4 + rhs.time[1] * 1e2 + rhs.time[2]);            });        for (size_t i = 0; i != rec.size(); ++i)        {               if (rec[i].flag == 0 && i + 1 != rec.size() && rec[i + 1].flag == 1)            {                   // matched records                if (cost == 0)                {                       printf("%s %02d\n", name.c_str(), Month);                }                auto cost_and_time = calc_cost_and_time(rec[i], rec[i + 1]);                printf("%02d:%02d:%02d %02d:%02d:%02d %lld $%.2f\n", rec[i].time[0], rec[i].time[1], rec[i].time[2],                    rec[i + 1].time[0], rec[i + 1].time[1], rec[i + 1].time[2], cost_and_time.second, cost_and_time.first / 100.0);                cost += cost_and_time.first / 100.0;                rec[i + 1].flag = 2;            }        }        if (cost != 0)        {               printf("Total amount: $%.2f\n", cost);        }    }    return 0;}

PAT (Advanced level) 1025 PAT Ranking

• 这里我看了题目之后下意识就用 merge 来归并不同考场的考生了。其实还是应该把所有考生都存在一个容器里，再进行一次总的排序，这样更简单

#include <cstdio>#include <vector>#include <algorithm>#include <cstring>#include <iterator>using namespace std;struct Testee {       char id[14];    char score;    int loc_rank;    char loc_num;};int N;vector<Testee> all1, all2;bool cmp(const Testee& lhs, const Testee& rhs){       if (lhs.score == rhs.score)    {           return strcmp(lhs.id, rhs.id) < 0;    }    else {           return lhs.score > rhs.score;    }}int main(int argc, const char* argv[]) {       scanf("%d", &N);    for (int i = 1; i <= N; ++i)    {           int K;        scanf("%d", &K);        vector<Testee> loc;        while (K--)        {               Testee testee;            scanf("%s %d", testee.id, &testee.score);            testee.loc_num = i;            loc.push_back(std::move(testee));        }        sort(loc.begin(), loc.end(), cmp);        int rk = 1;        for (size_t j = 0; j != loc.size(); ++j)        {               if (j != 0 && loc[j].score != loc[j - 1].score)            {                   rk = j + 1;            }            loc[j].loc_rank = rk;        }        vector<Testee>& all_res = (all1.size() < all2.size()) ? all1 : all2;        vector<Testee>& all_merge = (all1.size() > all2.size()) ? all1 : all2;        all_res = vector<Testee>();        if (all_merge.size() == 0)        {               all_res = std::move(loc);        }        else {               merge(loc.begin(), loc.end(), all_merge.begin(), all_merge.end(), back_inserter(all_res), cmp);        }    }    vector<Testee>& all_res = (all1.size() > all2.size()) ? all1 : all2;    printf("%d\n", all_res.size());    int rk = 1;    for (size_t j = 0; j != all_res.size(); ++j)    {           if (j != 0 && all_res[j].score != all_res[j - 1].score)        {               rk = j + 1;        }        printf("%s %d %d %d\n", all_res[j].id, rk, all_res[j].loc_num, all_res[j].loc_rank);    }    return 0;}

PAT (Advanced level) 1062 Talent and Virtue

• 题目还是比较简单的。我是把类别单独分出来，一类存一个容器，之后按顺序输出。更好的思路是把类别这个属性也放到结构体中，例如sage标识为0，noble man标识为1…之后在排序函数中按类别号升序排序即可

#include <cstdio>#include <vector>#include <algorithm>#include <cstring>using namespace std;struct Man {       char id[9];    int grade[2];   // virtual, talent};int N, L, H;vector<Man> sages, nobel, fool, small;bool cmp(const Man& lhs, const Man& rhs){       int sumL = lhs.grade[0] + lhs.grade[1];    int sumR = rhs.grade[0] + rhs.grade[1];    if (sumL == sumR)    {           if (lhs.grade[0] == rhs.grade[0])        {               return strcmp(lhs.id, rhs.id) < 0;        }        else {               return lhs.grade[0] > rhs.grade[0];        }    }    else {           return sumL > sumR;    }}int main(int argc, const char* argv[]) {       scanf("%d %d %d", &N, &L, &H);    for (int i = 0; i != N; ++i)    {           Man tmp;        scanf("%s %d %d", tmp.id, &tmp.grade[0], &tmp.grade[1]);        if (tmp.grade[0] >= L && tmp.grade[1] >= L)        {               if (tmp.grade[0] >= H && tmp.grade[1] >= H)            {                   sages.push_back(std::move(tmp));            }            else if (tmp.grade[0] >= H && tmp.grade[1] < H)            {                   nobel.push_back(std::move(tmp));            }            else if (tmp.grade[0] < H && tmp.grade[1] < H && tmp.grade[0] >= tmp.grade[1])            {                   fool.push_back(std::move(tmp));            }            else {                   small.push_back(std::move(tmp));            }        }    }    printf("%d\n", sages.size() + nobel.size() + fool.size() + small.size());    sort(sages.begin(), sages.end(), cmp);    for (size_t i = 0; i != sages.size(); ++i)    {           printf("%s %d %d\n", sages[i].id, sages[i].grade[0], sages[i].grade[1]);    }    sort(nobel.begin(), nobel.end(), cmp);    for (size_t i = 0; i != nobel.size(); ++i)    {           printf("%s %d %d\n", nobel[i].id, nobel[i].grade[0], nobel[i].grade[1]);    }    sort(fool.begin(), fool.end(), cmp);    for (size_t i = 0; i != fool.size(); ++i)    {           printf("%s %d %d\n", fool[i].id, fool[i].grade[0], fool[i].grade[1]);    }    sort(small.begin(), small.end(), cmp);    for (size_t i = 0; i != small.size(); ++i)    {           printf("%s %d %d\n", small[i].id, small[i].grade[0], small[i].grade[1]);    }        return 0;}

PAT (Advanced level) 1075 PAT Judge

• 这道题不能说难，但题意特别细节，得多读几遍题
• 刚开始做的时候一直卡测试点 4，原因是这个测试点里有一个人多次提交了同一题的满分记录，这时就只能加一次满分题数而不能提交一次就加一次

#include <cstdio>#include <vector>#include <algorithm>#include <map>using namespace std;struct Rec {       int uid;        // 1 ~ N    int pid;        // 1 ~ K    int partial_score;};struct User {       int rank;    int uid;    int total_score = 0;    int s[5] = {   -1, -1, -1, -1, -1};    int perfect_cnt = 0;    bool flag = false;};int N, K, M;    // user, problem, submissionint P[5];       // full markmap<int, User> Data;vector<User> Users;int main(int argc, const char* argv[]) {       scanf("%d %d %d", &N, &K, &M);    for(int i = 0; i != K; ++i)    {           scanf("%d", &P[i]);    }    for (int i = 0; i != M; ++i)    {           Rec tmp;        scanf("%d %d %d", &tmp.uid, &tmp.pid, &tmp.partial_score);        tmp.pid -= 1;        User& user = Data[tmp.uid];        user.uid = tmp.uid;                if (tmp.partial_score >= 0)        {               user.flag = true;        }        tmp.partial_score = (tmp.partial_score > 0) ? tmp.partial_score : 0;                if (tmp.partial_score == P[tmp.pid]            && P[tmp.pid] != Data[tmp.uid].s[tmp.pid])        {               ++Data[tmp.uid].perfect_cnt;        }        if (Data[tmp.uid].s[tmp.pid] < tmp.partial_score)        {               Data[tmp.uid].s[tmp.pid] = tmp.partial_score;        }    }    for (auto& user_pair : Data)    {           User& user = user_pair.second;        if (user.flag)        {               for (int j = 0; j != K; ++j)            {                   user.total_score += (user.s[j] > 0) ? user.s[j] : 0;            }            Users.push_back(user);        }    }    sort(Users.begin(), Users.end(), [](const User& lhs, const User& rhs) -> bool {           if (lhs.total_score == rhs.total_score)        {               if (lhs.perfect_cnt == rhs.perfect_cnt)            {                   return lhs.uid < rhs.uid;            }            else {                   return lhs.perfect_cnt > rhs.perfect_cnt;            }        }        else {               return lhs.total_score > rhs.total_score;        }        });    int rank = 1;    for (size_t i = 0; i != Users.size(); ++i)    {           if (i != 0 && Users[i].total_score != Users[i - 1].total_score)        {               rank = i + 1;        }        printf("%d %05d %d ", rank, Users[i].uid, Users[i].total_score);        for (int j = 0; j != K; ++j)        {                if (Users[i].s[j] == -1)            {                   printf("-");            }            else {                   printf("%d", Users[i].s[j]);            }            if (j != K - 1)            {                   printf(" ");            }            else {                   printf("\n");            }        }    }    return 0;}

PAT (Advanced level) 1080 Graduate Admission

• 最后录取学生时，我用的方法还是复杂了，很容易超时。更好的做法是对应每个学校，记录该校的上一个录取者，如果当前判断的考生排名与上一个录取者相同，那么不论名额多少，可录取该考生

#include <cstdio>#include <vector>#include <algorithm>#include <unordered_set>using namespace std;struct Applicant {       int id;    int grade[2];    int final_grade;    int choice[5];    size_t same_rank_cnt = 0;    unordered_set<int> school_passed;};vector<Applicant> Applicants;int N, M, K;    // applicant, school, choicesize_t Quota[100];vector<vector<int>> Res(100);int main(int argc, const char* argv[]) {       scanf("%d %d %d", &N, &M, &K);    for (int i = 0; i != M; ++i)    {           scanf("%lu", &Quota[i]);    }    for (int i = 0; i != N; ++i)    {           Applicant tmp;        scanf("%d %d", &tmp.grade[0], &tmp.grade[1]);        tmp.id = i;        tmp.final_grade = tmp.grade[0] + tmp.grade[1];        for (int j = 0; j != K; ++j)        {               scanf("%d", &tmp.choice[j]);        }        Applicants.push_back(std::move(tmp));    }    sort(Applicants.begin(), Applicants.end(), [](const Applicant& lhs, const Applicant& rhs) -> bool {           if (lhs.final_grade != rhs.final_grade)        {               return lhs.final_grade > rhs.final_grade;        }        else if (lhs.grade[0] != rhs.grade[0])        {               return lhs.grade[0] > rhs.grade[0];        }        else {               return lhs.id < rhs.id;        }        });    for (size_t i = 0; i != Applicants.size(); ++i)    {           size_t& same_rank_cnt = Applicants[i].same_rank_cnt;        if (same_rank_cnt == 0)        {               same_rank_cnt = i + 1;            for (; same_rank_cnt != Applicants.size()                && Applicants[i].final_grade == Applicants[same_rank_cnt].final_grade                && Applicants[i].grade[0] == Applicants[same_rank_cnt].grade[0]; ++same_rank_cnt)            {               }            same_rank_cnt -= i;            for (size_t j = 1; j != same_rank_cnt; ++j)            {                   Applicants[i + j].same_rank_cnt = same_rank_cnt - j;            }        }        for (int k = 0; k != K; ++k)        {               if (Applicants[i].school_passed.find(Applicants[i].choice[k]) != Applicants[i].school_passed.end())            {                   Res[Applicants[i].choice[k]].push_back(Applicants[i].id);                break;            }            else if (Res[Applicants[i].choice[k]].size() < Quota[Applicants[i].choice[k]])            {                   Res[Applicants[i].choice[k]].push_back(Applicants[i].id);                for (size_t j = 1; j != same_rank_cnt; ++j)                {                       Applicants[i + j].school_passed.insert(Applicants[i].choice[k]);                }                break;            }        }    }    for (int i = 0; i != M; ++i)    {           sort(Res[i].begin(), Res[i].end());        for (size_t j = 0; j != Res[i].size(); ++j)        {               printf("%d", Res[i][j]);            if (j + 1 != Res[i].size())            {                   printf(" ");            }            else {                   printf("\n");            }        }        if (Res[i].size() == 0u)        {               printf("\n");        }    }    return 0;}

PAT (Advanced level) 1095 Cars on Campus

• 这题最开始我是这么做的，但就是无法通过测试点 2, 4，暂时没看出来问题出在哪，先保留代码以后可以继续看：

#include <cstdio>#include <vector>#include <algorithm>#include <string>#include <unordered_map>#include <set>using namespace std;struct Rec {       char plate_number[8];      int status;     // 1: in -1:out    int all_time;        int time[3];    // h m s};unordered_map<string, vector<Rec>> recs;unordered_map<string, int> Time;vector<Rec> valid_recs;vector<int> query;int N, K;   // record, queryint main(int argc, const char* argv[]) {       scanf("%d %d", &N, &K);    for (int i = 0; i != N; ++i)    {           Rec tmp;        char status[4];        scanf("%s %d:%d:%d %s", tmp.plate_number, &tmp.time[0], &tmp.time[1], &tmp.time[2], status);        tmp.all_time = tmp.time[0] * 10000 + tmp.time[1] * 100 + tmp.time[2];        tmp.status = (status[0] == 'i') ? 1 : -1;        recs[tmp.plate_number].push_back(tmp);    }    for (auto& rec_pair : recs)    {           vector<Rec>& rec = rec_pair.second;        sort(rec.begin(), rec.end(), [](const Rec& lhs, const Rec& rhs) -> bool {               return lhs.all_time < rhs.all_time;            });        for (size_t i = 0; i + 1 != rec.size(); ++i)        {               if (rec[i].status == 1 && rec[i + 1].status == -1)            {                   auto interval_calc = [](const Rec& lhs, const Rec& rhs) -> int {                       int ds = lhs.time[2] - rhs.time[2];                    int dm = lhs.time[1] - rhs.time[1];                    int dh = lhs.time[0] - rhs.time[0];                    if (ds < 0)                    {                           dm -= 1;                        ds += 60;                    }                    if (dm < 0)                    {                           dh -= 1;                        dm += 60;                    }                    return dh * 10000 + dm * 100 + ds;                };                Time[rec_pair.first] += interval_calc(rec[i + 1], rec[i]);                valid_recs.push_back(rec[i]);                valid_recs.push_back(rec[i + 1]);            }        }    }    sort(valid_recs.begin(), valid_recs.end(), [](const Rec& lhs, const Rec& rhs) -> bool {           return lhs.all_time < rhs.all_time;        });    for (int i = 0; i != K; ++i)    {           int time[3];        scanf("%d:%d:%d", &time[0], &time[1], &time[2]);        query.push_back(time[0] * 10000 + time[1] * 100 + time[2]);    }    size_t query_idx = 0;    int car_cnt = 0;    for (size_t i = 0; i != valid_recs.size() && query_idx != K; ++i)    {           if (valid_recs[i].all_time > query[query_idx])        {               printf("%d\n", car_cnt);            ++query_idx;        }        car_cnt += valid_recs[i].status;    }    for (; query_idx != K; ++query_idx)    {           printf("%d\n", car_cnt);    }    int max_time = 0;    set<string> max_plate_numbers;    for (const auto& time_pair : Time)    {           if (time_pair.second > max_time)        {               max_time = time_pair.second;            max_plate_numbers = set<string>{    time_pair.first };        }        else if (time_pair.second == max_time)        {               max_plate_numbers.insert(time_pair.first);        }    }    for (const auto& plate_number : max_plate_numbers)    {           printf("%s ", plate_number.c_str());    }    printf("%02d:%02d:%02d", max_time / 10000, (max_time % 10000) / 100, max_time % 100);    return 0;}

• 后来参考书上解法，更改了思路，能够 AC，代码也更简洁
  • 时间都转化成秒，方便处理
  • 先对所有记录排序，车牌号为主关键词，时间为次关键词。接着遍历排序后的所有记录，如果连续两条记录分别为 “in” 和 “out”，且车牌号相同，则为有效记录，加入 “有效记录” 中，并持续更新最长停车时间
  • 将有效记录按时间排序
  • 每读入一条查询请求，就利用有效记录进行查询，输出结果

#include <cstdio>#include <vector>#include <algorithm>#include <string>#include <unordered_map>#include <cstring>using namespace std;struct Rec {       char plate_number[8];      int status;     // 1: in -1:out    int time;       };unordered_map<string, int> Time;vector<Rec> recs;vector<Rec> valid_recs;int N, K;   // record, queryint Max_time = 0;int main(int argc, const char* argv[]) {       scanf("%d %d", &N, &K);    for (int i = 0; i != N; ++i)    {           Rec tmp;        int time[3];        char status[4];        scanf("%s %d:%d:%d %s", tmp.plate_number, &time[0], &time[1], &time[2], status);        tmp.time = time[0] * 3600 + time[1] * 60 + time[2];        tmp.status = (status[0] == 'i') ? 1 : -1;        recs.push_back(std::move(tmp));    }    sort(recs.begin(), recs.end(), [](const Rec& lhs, const Rec& rhs) -> bool {           int res = strcmp(lhs.plate_number, rhs.plate_number);        if (res != 0)        {               return res < 0;        }        else {               return lhs.time < rhs.time;        }        });    for (size_t i = 0; i + 1 != recs.size(); ++i)    {           if (recs[i].status == 1 && recs[i + 1].status == -1 && strcmp(recs[i].plate_number, recs[i + 1].plate_number) == 0)        {                Time[recs[i].plate_number] += recs[i + 1].time - recs[i].time;            valid_recs.push_back(recs[i]);            valid_recs.push_back(recs[i + 1]);            Max_time = max(Max_time, Time[recs[i].plate_number]);        }    }    sort(valid_recs.begin(), valid_recs.end(), [](const Rec& lhs, const Rec& rhs) -> bool {           return lhs.time < rhs.time;        });    size_t rec_idx = 0;    int car_cnt = 0;    for (int i = 0; i != K; ++i)    {           int tmp_time[3];        scanf("%d:%d:%d", &tmp_time[0], &tmp_time[1], &tmp_time[2]);        int time = tmp_time[0] * 3600 + tmp_time[1] * 60 + tmp_time[2];                for (; rec_idx != valid_recs.size() && valid_recs[rec_idx].time <= time; ++rec_idx)        {               car_cnt += valid_recs[rec_idx].status;        }        printf("%d\n", car_cnt);    }    vector<string> max_plate_numbers;    for (const auto& time_pair : Time)    {           if (time_pair.second == Max_time)        {               max_plate_numbers.push_back(time_pair.first);        }    }    sort(max_plate_numbers.begin(), max_plate_numbers.end());    for (const auto& plate_number : max_plate_numbers)    {           printf("%s ", plate_number.c_str());    }    printf("%02d:%02d:%02d", Max_time / 3600, (Max_time % 3600) / 60, Max_time % 60);    return 0;}

散列

PAT (Advanced Level) 1039 Course List for Student

• 我下面采用的是常规方法，采用 unordered_map<string, vector<int>> 记录信息；但是本题最后一个测试点数据量很大，很容易超时；我下面的代码也是提交了好几次才勉勉强强通过的
• 还要注意输出格式

#include <iostream>#include <vector>#include <unordered_map>#include <string>#include <algorithm>using namespace std;int N, K;unordered_map<string, vector<int>> Data;int main(void){   	scanf("%d %d", &N, &K);	while (K--)	{   		int i, ni;		scanf("%d %d", &i, &ni);		while (ni--)		{   			string name;			cin >> name;			Data[name].push_back(i);		}	}	while (N--)	{   		string name;		cin >> name;		vector<int>& clist = Data[name];		printf("%s %lu", name.c_str(), clist.size());		sort(clist.begin(), clist.end());				for (size_t i = 0; i != clist.size(); ++i)		{   			printf(" %d", clist[i]);		}        printf("\n");	}	return 0;};

• 解决方法是使用字符哈希，将姓名转化为数字，然后直接开一个大的 vector<int> selectCourse[26*26*26*10+1] 数组，用空间换时间; 这样修改后能轻松通过时间限制

#include <vector>#include <algorithm>#include <cstdio>using namespace std;int N, K;vector<int> Data[26*26*26*10+1];int str_hash(char name[]){   	int hash_res = 0;	for (int i = 0; i < 3; ++i)	{   		hash_res = hash_res * 26 + name[i] - 'A';	}	hash_res = hash_res * 10 + name[3] - '0';    return hash_res;}int main(void){   	scanf("%d %d", &N, &K);	while (K--)	{   		int i, ni;		scanf("%d %d", &i, &ni);		while (ni--)		{   			char name[5];			scanf("%s", name);			Data[str_hash(name)].push_back(i);		}	}	while (N--)	{   		char name[5];		scanf("%s", name);		vector<int>& clist = Data[str_hash(name)];				sort(clist.begin(), clist.end());		printf("%s %lu", name, clist.size());		for (size_t i = 0; i != clist.size(); ++i)		{   			printf(" %d", clist[i]);		}		printf("\n");	}	return 0;};

PAT (Advanced level) 1084 Broken Keyboard

• 感觉贼简单的题，没有一次 AC，是我太菜！(悔しい)

#include <iostream>#include <string>#include <unordered_set>using namespace std;string original;string actual;unordered_set<char> broken;int main(int argc, const char* argv[]) {       cin >> original >> actual;        size_t original_idx = 0;    for (size_t i = 0; i != actual.size(); ++i, ++original_idx)    {           while (original[original_idx] != actual[i])        {               if (original[original_idx] >= 'a' && original[original_idx] <= 'z')            {                   original[original_idx] += 'A' - 'a';            }            if (broken.find(original[original_idx]) == broken.end())            {                   cout << original[original_idx];                broken.insert(original[original_idx]);            }                        ++original_idx;        }    }    for (; original_idx != original.size(); ++original_idx)    {           if (original[original_idx] >= 'a' && original[original_idx] <= 'z')        {               original[original_idx] += 'A' - 'a';        }        if (broken.find(original[original_idx]) == broken.end())        {               cout << original[original_idx];            broken.insert(original[original_idx]);        }    }    return 0;}

贪心

PAT (Basic level) 1020 月饼

• 这题唯一的坑点是对于月饼存库量和总售价，题目中只说是正数，因此必须用浮点数存储。如果用整数存储，会有一个测试点通不过

#include <cstdio>#include <vector>#include <algorithm>using namespace std;// N 表示月饼的种类数 <= 1000 // D 表示市场最大需求量 <= 500int N;double D;int main(int argc, const char* argv[]) {   	scanf("%d %lf", &N, &D);	vector<pair<double, double>> Value(N);		// 价值、库存	double revenue = 0;	for (int i = 0; i != N; ++i)	{   		scanf("%lf", &Value[i].second);	}	for (int i = 0; i != N; ++i)	{   		double price;		scanf("%lf", &price);		Value[i].first = price / Value[i].second;	}	sort(Value.begin(), Value.end(), [](const pair<double, double>& lhs, const pair<double, double>& rhs) -> bool		{   			return lhs.first > rhs.first;		});;	for (int i = 0; i != N && D > 0; ++i)	{   		int valid_weight = min(Value[i].second, D);		D -= valid_weight;		revenue += valid_weight * Value[i].first;	}	printf("%.2f", revenue);    return 0;}

PAT (Advanced Level) 1033 To Fill or Not to Fill

个人感觉这道题的解题方法用分治的思想更容易理解

• 步骤 1: 将所有加油站按离起点的距离从小到大进行排序。排序完毕后，如果离起点最近的加油站的距离不是 0, 则表示汽车无法出发, 输出 “The maximum travel distance= 0.00” (测试点 2 就是这种情况); 否则进入步骤 2
• 步骤 2: 假设当前所处的加油站编号为 now, 接下来将从满油状态下能到达的所有加油站中选出下一个前往的加油站， 策略如下：
  • (1) 寻找距离当前加油站最近的油价低于当前油价的加油站 (记为 $k$), 加恰好能够到达加油站 $k$ 的油， 然后前往加油站 $k$ (即优先前往更低油价的加油站)
    • 证明：设到达加油站 now 时油箱还有 gas 单位的油，到达 $k$ 需要 dgas 单位的油，下面分两种情况：若 gas $\ge$ dgas, 则最佳策略肯定是不加油开到 $k$；若 gas $<$ dgas，则易知最佳策略肯定是把油加到 dgas，然后开到 $k$
  • (2) 如果找不到油价低于当前油价的加油站，
    • 若从 now 能直接开到终点，那么只需要加能到达终点的油 (测试点 4 就是这种情况)
    • 否则寻找油价最低的加油站 $k$，在当前加油站加满油， 然后前往加油站 $k$ (即在没有更低油价的加油站时， 前往油价尽可能低的加油站)
      • 证明：这种情况下，满油航程内都找不到低于当前油价的加油站且到不了终点，那么最优的加油方案肯定是在满油航程内都使用当前加油站以及原有的油，因此肯定得直接加满油；同时考虑在满油航程之外还要走一段距离，在最优规划中，这一段距离必然用的是加油站 $k$ 的油，因此必须要到加油站 $k$，进一步考虑易知，一定是直接到加油站 $k$ 而不经过其他加油站
  • (3) 如果在满油状态下都找不到能到达的加油站，则最远能到达的距离为当前加油站的距离加上满油状态下能前进的距离， 结束算法（即没有加油站可以到达时结束算法)

• 如果测试点 4 过不了，试下下面这组测试数据，正确答案为 1108.33：

50 1300 12 5 7.00 0 8.00 300 9.00 600 10.00 900 11.00 1200

#include <cstdio>#include <algorithm>#include <vector>using namespace std;double FullTankCapacity;double TotalDistance;double DAvg;size_t N;struct Station {   	double price;	double distance;};vector<Station> Stations;double FullTankCapacityDis;double CheapestPrice = 0;double NowGasVolume = 0;int main(int argc, const char* argv[]) {   	scanf("%lf %lf %lf %lu", &FullTankCapacity, &TotalDistance, &DAvg, &N);	FullTankCapacityDis = FullTankCapacity * DAvg;	for (size_t i = 0; i != N; ++i)	{   		Station tmp;		scanf("%lf %lf", &tmp.price, &tmp.distance);		if (tmp.distance >= TotalDistance)		{   			continue;		}		Stations.push_back(std::move(tmp));	}	N = Stations.size();	sort(Stations.begin(), Stations.end(), [](const Station& lhs, const Station& rhs) -> bool		{   			return lhs.distance < rhs.distance;		});	if (Stations[0].distance > 0)	{   		printf("The maximum travel distance = 0.00");		return 0;	}	size_t now = 0;	while (now + 1 < N)	// now 后肯定有一个加油站, 不断寻找 now 的下一个要到达的加油站	{   		if (Stations[now + 1].distance - Stations[now].distance > FullTankCapacityDis)		{   			break;		}		bool find_cheaper_station = false;		// 如果在加油站 now 开始，有一个加油站距离在 FullTankCapacityDis 内，且油价更便宜，那么直接开到该加油站		for (size_t next = now + 1; next != N && Stations[next].distance - Stations[now].distance <= FullTankCapacityDis; ++next)		{   			if (Stations[next].price <= Stations[now].price)			{   				double ddis = Stations[next].distance - Stations[now].distance;				if (NowGasVolume * DAvg < ddis)				{   					// 需要加油					double dgas = (ddis - NowGasVolume * DAvg) / DAvg;					NowGasVolume += dgas;					CheapestPrice += dgas * Stations[now].price;					now = next;				}				// 开到 next 加油站				NowGasVolume -= ddis / DAvg;				now = next;				find_cheaper_station = true;				break;			}		}		if(find_cheaper_station == false)		{   			if (TotalDistance - Stations[now].distance <= FullTankCapacityDis)			{   				// 可以一次到达终点，则直接开到终点即可，不用加满油				break;			}			// 不能一次到达终点，则油箱加满，开到 FullTankCapacityDis 内油价最便宜的加油站			double dgas = FullTankCapacity - NowGasVolume;				NowGasVolume = FullTankCapacity;			CheapestPrice += dgas * Stations[now].price;			int min_idx = now + 1;			double min_price = Stations[now + 1].price;			for (size_t next = now + 2; next < N && Stations[next].distance - Stations[now].distance <= FullTankCapacityDis; ++next)			{   				if (Stations[next].price < min_price)				{   					min_price = Stations[next].price;					min_idx = next;				}			}			NowGasVolume -= (Stations[min_idx].distance - Stations[now].distance) / DAvg;			now = min_idx;		}	}	// 往后走不会再碰到加油站，因此直接看能不能开到终点即可	if (TotalDistance > Stations[now].distance + FullTankCapacityDis)	{   		printf("The maximum travel distance = %.2f", Stations[now].distance + FullTankCapacityDis);	}	else {   		double ddis = TotalDistance - Stations[now].distance;		double gas_needed = ddis / DAvg;		if (NowGasVolume < gas_needed)		{   			// 加油			CheapestPrice += gas_needed * Stations[now].price;		}		printf("%.2f", CheapestPrice);	}    return 0;}

PAT (Advanced Level) 1038 Recover the Smallest Number

• 这道题我想的方法是按高位数字大小排序，小的排前面。如果高位数字都完全相同，即一个字符串是另一个字符串的子串，则比较较长字符串中短子串后的一个数字与最高位数字的大小，小的排前面
  • 我在做的时候遗漏了给的数字串全为 0 的情况
  • 但这种方法最大的问题在于，无法处理较长字符串中短子串后的一个数字与最高位数字大小相同的情况，例如

2 03 030     // 应该输出 3003 而非 3030，但如果按照我的方法，03 和 030 是分不出大小的

• 代码如下，测试点 5 无法通过

#include <cstdio>#include <algorithm>#include <vector>using namespace std;int N;vector<vector<char>> Segs;bool cmp(const vector<char>& lhs, const vector<char>& rhs){       size_t min_size = min(lhs.size(), rhs.size());    for (size_t i = 0; i != min_size; ++i)    {           if (lhs[i] != rhs[i])        {               return lhs[i] < rhs[i];        }    }    if (lhs.size() < rhs.size())    {           return rhs[0] < rhs[min_size];    }    else if (lhs.size() > rhs.size()) {           return lhs[min_size] < lhs[0];    }    else {         // 两个数字段完全相等        return false;    }}int main(int argc, const char* argv[]) {       scanf("%d", &N);    getchar();    while (N--)    {           vector<char> num;        char tmp;               while ((tmp = getchar()) != ' ' && tmp != '\n')        {               num.push_back(tmp);        }        Segs.push_back(num);    }        sort(Segs.begin(), Segs.end(), cmp);       bool zero_flag = true;    for (size_t i = 0; i != Segs.size(); ++i)    {           for (size_t j = 0; j != Segs[i].size(); ++j)        {               if (zero_flag && Segs[i][j] == '0')            {                   continue;            }            else if(zero_flag){                   zero_flag = false;            }            printf("%c", Segs[i][j]);        }    }    if (zero_flag)    {           printf("0");    }    return 0;}

• 书上给的方法要巧妙地多：对数字串 $S_1$ 与 $S_2$，如果 $S_1+S_2<S_2+S_1$ (加号表示拼接），那么把 $S_1$ 放在 $S_2$ 的前面： 否则，把 $S_2$ 放在 $S_1$ 的前面
  • 证明：假设有数字串 $S_1+..+S_i+...+S_j+...+S_n$, 其中 $S_j+S_i<S_i+S_j$, 那么易知 $S_1+..+S_j+...+S_i+...+S_n$ $<$ $S_1+..+S_i+...+S_j+...+S_n$。不断对不满足上述性质的字符串调换位置，最终即可得到最小数字串

#include <iostream>#include <algorithm>#include <string>#include <vector>using namespace std;int N;vector<string> Segs;string Res;int main(int argc, const char* argv[]) {       cin >> N;        while (N--)    {           string tmp;        cin >> tmp;        Segs.push_back(tmp);    }        sort(Segs.begin(), Segs.end(), [](const string& lhs, const string& rhs) -> bool {           return lhs + rhs < rhs + lhs;        });       for (size_t i = 0; i != Segs.size(); ++i)    {           Res += Segs[i];    }    bool zero_flag = true;    for (size_t i = 0; i != Res.size(); ++i)    {           if (zero_flag && Res[i] == '0')        {               continue;        }        else {               zero_flag = false;        }        cout << Res[i];    }    if (zero_flag)    {           cout << 0;    }    return 0;}

PAT (Advanced Level) 1067 Sort with Swap(0, i)

• 在循环中寻找一个不在本位上的数时，如果每次都从头开始枚举序列中的数，判断其是否在其本位上， 则会有两组数据超时（因为复杂度是二次方级的）。更合适的做法是利用每个移回本位的数在后续操作中不再移动的特点， 从整体上定义一个变量 $k$, 用来保存目前序列中除 0 以外不在本位上的最小数（初始为 1), 当交换过程中出现 0 回归本位的情况时， 总是从当前的 $k$ 开始继续增大寻找不在本位上的数， 这样就能保证复杂度从整体上是线性级别 ($k$ 在整个算法过程中最多只会从 0 增长到 $n$)

我在下面的代码中用的是 map 来记录所有错位数字及其位置，但感觉书上的方案更巧妙一些

#include <cstdio>#include <algorithm>#include <vector>#include <unordered_map>using namespace std;size_t N;vector<int> Perm;unordered_map<int, int> WrongPos;   // 错误排列的数字及其位置int SwapCnt = 0;int main(int argc, const char* argv[]) {       scanf("%lu", &N);    for(size_t i = 0; i != N; ++i)    {           size_t tmp;        scanf("%lu", &tmp);        Perm.push_back(tmp);        if (tmp != i)        {               WrongPos.insert({    tmp, i });        }    }    while (WrongPos.size() != 0)    {           if (WrongPos.find(0) == WrongPos.end())    // 0 在正确位置，则与另一个不在正确位置的数字互换位置        {               auto wrong_pair = *(WrongPos.begin());            swap(Perm[0], Perm[wrong_pair.second]);            ++SwapCnt;            WrongPos.insert({    0, wrong_pair.second });            WrongPos[wrong_pair.first] = 0;        }        else {     // 0 不在正确位置，则将 Perm[0] 与 Perm[Perm[0]] 互换，使数字 Perm[0] 交换到正确位置            WrongPos.erase(Perm[0]);            swap(Perm[0], Perm[Perm[0]]);            ++SwapCnt;            WrongPos[Perm[0]] = 0;            if (WrongPos[0] == 0)   // 正好 Perm[Perm[0]] 即为 0            {                   WrongPos.erase(0);            }        }    }        printf("%d", SwapCnt);    return 0;}

// 这里截取了书上代码的关键部分，明显比我写的更简洁int k = 1; // k 存放除 0 以外当前不在本位上的最小的数while (left > 0) {     // 只要还有数不在本位上    // 如果 0 在本位上， 则寻找一个当前不在本位上的数与 0 交换    if (pos[0] == 0) {           while (k < n) {               if (pos[k] != k) {             // 找到一个当前不在本位上的数 k                swap(pos[0], pos[k]);   // 将 k 与 0 交换位置                ans++;  // 交换次数加 1                break;  // 退出循环            }            k++;        // 判断 k + l 是否在本位        }    }    // 只要 0 不在本位， 就将 0 所在位置的数的当前所处位置与 0 的位置交换    while (pos[0] != 0) {           swap(pos[0], pos[pos[0]]);      // 将0与pos[O]交换        ans++;                          // 交换次数加1        left--;                         // 不在本位上的数的个数减1    }}

二分

寻找有序序列中第一个满足某条件的元素的位置

int solve(int left, int right) {   	int mid; 	while (left < right) {    		// 注意：这里是 < 而非 <=，结束时一定为 low == high		mid = (left + right) / 2;		if (条件成立) {   		// 条件成立，第一个满足条件的元素的位置 <=mid			right = mid; 	// 往左子区间 [left, mid] 查找		} else {    // 条件不成立，则第一个满足该条件的元素的位置 >mid			left = mid + 1; 	// 往右子区间 [mid+1, right] 查找		}	}	return left; 	// 返回夹出来的位置}

• 例如，给定一增序序列，对给定的欲查询元素 $x$, 求出序列中第一个大于等于 $x$ 的元素的位置 $L$ 以及第一个大于 $x$ 的元素的位置 $R$, 这样元素 $x$ 在序列中的存在区间就是左闭右开区间 $[L,R)$。其中求 $L$ 也就是找第一个 $\ge x$ 的元素位置，求 $R$ 也就是找第一个 $>x$ 的位置，因此求 $L$ 也就只要把上述条件改为 $A[mid]\ge x$，求 $R$ 则把条件改为 $A[mid]<x$
• 另外， 如果想要寻找最后一个满足 "条件 $C$" 的元素的位置， 则可以先求第一个满足 “条件$!C$” 的元素的位置， 然后将该位置减 1 即可

• 注意，上述代码其实有个 bug：考虑序列中最后一个元素都不满足条件的情况，这是上述代码一定返回的是 right 而非我们想要的 right + 1，因此需要多加一个判断语句：如果最后一个元素也不满足条件，那么直接返回尾后位置

int solve(int left, int right) {   	if (right 位置的元素不满足条件)	{   		return right + 1;	}	int mid; 	while (left < right) {    		// 注意：这里是 < 而非 <=，结束时一定为 low == high		mid = (left + right) / 2;		if (条件成立) {   		// 条件成立，第一个满足条件的元素的位置 <=mid			right = mid; 	// 往左子区间 [left, mid] 查找		} else {    // 条件不成立，则第一个满足该条件的元素的位置 >mid			left = mid + 1; 	// 往右子区间 [mid+1, right] 查找		}	}	return left; 	// 返回夹出来的位置}

二分搜索算法

• 也可以直接使用泛型算法库的二分搜索算法

• equal_range 、lower_bound 和 upper_bound 算法返回迭代器， 指向给定元素在序列中的正确插入位置----插入后还能保持有序。如果给定元素比序列中的所有元素都大， 则会返回尾后迭代器
• 每个算法都提供两个版本： 第一个版本用元素类型的小于运算符来检测元素；第二个版本则使用给定的比较操作。在下列算法中，"x 小于 y" 表示 x<y 或 comp(x,y) 成功

lower_bound(beg, end, val)lower_bound(beg, end, val, comp)

• 返回一个迭代器，表示第一个小于等于 val 的元素，如果不存在这样的元素，则返回 end

upper_bound(beg, end, val)upper_bound(beg, end, val, comp)

• 返回一个迭代器， 表示第一个大于 val 的元素， 如果不存在这样的元素， 则返回 end

equal_range(beg, end, val)equal_range(beg, end, val, comp)

• 返回一个 pair， 其 first 成员是 lower_bound 返回的迭代器， second 成员是 upper_bound 返回的迭代器

binary_search(beg, end, val)binary_search(beg, end, val, comp)

• 返回一个 bool 值， 指出序列中是否包含等于 val 的元素。对于两个值 $x$ 和 $y$，当 $x$ 不小于 $y$ 且 $y$ 也不小于 $x$ 时， 认为它们相等

木棒切割问题

• 给出 $N$ 根木棒， 长度均已知， 现在希望通过切割它们来得到至少 $K$ 段长度相等的木棒（长度必须是整数）， 问这些长度相等的木棒最长能有多长
  • 例如对三根长度分别为 10、24、15 的木棒来说， 假设 $K=7$, 即需要至少 $7$ 段长度相等的木棒， 那么可以得到的最大长度为 $6$, 在这种情况下， 第一根木棒可以提供 $10/6=1$ 段、第二根木棒可以提供 $24/6=4$ 段、第三根木棒可以提供 $15/6=2$ 段， 达到了 $7$ 段的要求
• 对这个问题来说， 首先可以注意到一个结论：如果长度相等的木棒的长度 $L$ 越长， 那么可以得到的木棒段数 $K$ 越少。从这个角度出发便可以想到本题的算法， 即二分答案（最大长度 $L$)
• 由于这个问题可以写成求解最后一个满足条件 “$k\ge K$” 的长度 $L$, 因此不妨转换为求解第一个满足条件 “$k<K$” 的长度 $L$, 然后减 $1$ 即可

#include <iostream>#include <algorithm>#include <vector>using namespace std;vector<int> limbs{   10, 24, 15};int K = 7;bool valid(int len){       int sum = 0;    for (const auto& limb : limbs)    {           sum += limb / len;    }    return sum < K;}int solve(int left, int right){       int mid;    while (left < right)    {           mid = (left + right) / 2;        if (valid(mid))        {               right = mid;        }        else {               left = mid + 1;        }    }    return left;}int main(int argc, const char* argv[]) {       cout << solve(0, *max_element(limbs.begin(), limbs.end())) - 1;            return 0;}

求凸多边形外接圆半径

参考：

• 给出 $N$ 个线段的长度， 试将它们头尾相接（顺序任意）地组合成一个凸多边形， 使得该凸多边形的外接圆（即能使凸多边形的所有顶点都在圆周上的圆） 的半径最大， 求该最大半径。其中 $N$ 不超过 $10^5$ , 线段长度均不超过 $100$, 要求算法中不涉及坐标的计算

#include <stdio.h>// 求弧度double getTotalRadian(double edges[],int n,double r){       double radian = 0.0;    for(int i = 0; i < n; i++)        radian += asin(edges[i] / 2 / r) * 2;   return radian;}// 二分查找求最大半径void maxR(){   	// 错误率	double error = 1e-5;	// 边的个数	int n;	// 边长数组	double edges[5000];	// 弧度 最大边 π	double radian, maxEdge = 0.0, pi = asin(-1);		// 初始化 edges	scanf("%d", &n);	for(int i = 0; i < n; i++)	{   		scanf("%lf", &edges[i]);		if(edges[i] > maxEdge)		    maxEdge = edges[i];	}	 	//若最长边为直径，则直接处理	radian = getTotalRadian(edges, n, maxEdge/2);	if(abs(radian-pi*2)<error)	{   	    printf("外接圆的最大半径是：%.2f",maxEdge/2);	    return;	}	    double left =0,right=10000000,mid;    //在误差范围内循环求解    while(right -left >error)    {   	    mid = (right + left) / 2;	    radian = getTotalRadian(edges, n, mid);	    if(radian > 2 * pi)			left = mid;		else 			right = mid;	    }		printf("外接圆的最大半径是：%.2f",mid);	}}

快速幂

• 给定三个正整数 $a、b、m$ ($a<10^9,b<10^{18},1<m<10^9$), 求 $a^b\%m$。直接求解，时间复杂度是 $O(b)$, 显然对于 $10^{18}$ 的量级来说，$O(b)$ 的复杂度不能解决这个问题:

typedef long long LL;LL pow(LL a, LL b, LL m) {   	LL ans= 1;	for(int i = 0; i < b; i++) {   		ans = ans * a % m;	}	return ans;}

• 这里要使用快速幂的做法， 它基于二分的思想， 因此也常称为二分幂：
  • (1) 如果 $b$ 是奇数， 那么有 $a^b=a\ast a^{b-1}$
  • (2) 如果 $b$ 是偶数， 那么有 $a^b=a^{b/2}\ast a^{b/2}$
• 显然， $b$ 是奇数的情况总可以在下一步转换为 $b$ 是偶数的情况， 而 $b$ 是偶数的情况总可以在下一步转换为 $b/2$ 的情况。这样， 在 $log(b)$ 级别次数的转换后， 就可以把 $b$ 变为 $0$,

typedef long long LL;// 递归写法LL binaryPow(LL a, LL b, LL m) {   	if (b == 0) 		return 1; 	// b 为奇数，转换为 b-1	if(b % 2 == 1) 		return a * binaryPow(a, b - 1, m) % m;	else (	// b 为偶数，转换为 b/2		LL mul = binaryPow(a, b / 2, m);		return mul * mul % m;	}}

• 另外， 可能有两个细节需要注意：
  • 如果初始时 $a$ 有可能大于等于 $m$, 那么需要在进入函数前就让 $a$ 对 $m$ 取模
  • 如果 $m$ 为 1, 可以直接在函数外部特判为 0, 不需要进入函数来计算

• 接下来研究一下快速幂的迭代写法
• 对 $a^b$ 来说， 如果把 $b$ 写成二进制， 那么 $b$ 就可以写成若干二次幕之和
  • 例如 $13$ 的二进制是 $1101$, 那么就可以得到 $13=2^3+2^2+2^0$, 所以 $a^{13}=a^8\ast a^4\ast a^1$
• 很容易想象，通过同样的推导， 我们可以把任意的 $a^b$ 表示成 $a^{2^k}$,…,$a^8,a^4,a^2,a^1$ 中若干项的乘积， 其中如果 $b$ 的二进制的 1 号位为 1, 那么项 $a^{2^i}$ 就被选中。于是可以得到计算 $a^b$ 的大致思路： 令 $i$ 从 0 到 $k$ 枚举 $b$ 的二进制的每一位， 如果当前位为 $1$, 那么累积 $a^{2^i}$。注意到序列 $a^{2^k}$,…,$a^8,a^4,a^2,a^1$ 的前一项总是等于后一项的平方， 因此具体实现的时候可以这么做：
  • (1) 初始令 ans 等于 1, 用来存放累积的结果
  • (2) 判断 b 的二进制末尾是否为 1， 如果是的话， 令 ans 乘上 a 的值
  • (3) 令 a 平方， 并将 b 右移一位
  • (4) 只要 b 大于 0, 就返回 (2)