pat题型总结

2019-09-17

窗口排队模拟

eg1. 1017 Queueing at Bank (25 分)

题意：给出顾客数与窗口数，以及顾客的到达时间和处理时间；Bank的工作时间在8.-17.；在8.前到达需要等到8.后才开始办理，17.点及之后不办理，88了；计算平均等待时间；

思路：

输入；
按照到达时间排序；

先将空窗口填满（入队列）：即到即办理，或者等到8点，计算结束时间和等待时间；

//在8.以前到达
            if(Start>Customer[i].arr_time){
                Customer[i].wait_time=Start-Customer[i].arr_time;
                Customer[i].finish_time=Customer[i].p_time;
            }
            else {
                Customer[i].wait_time=0;
                Customer[i].finish_time=Customer[i].arr_time+Customer[i].p_time-Start;
            }

然后选取办理时间最早结束的出队列：它的结束时间与下一个候选顾客的到达时间作比较，到达之后就有空位置即办理，或者等到最先结束的完成后, 计算结束时间和等待时间；

//等待时间为前一个结束时间-到达时间
            //或者直接有空窗口，无需等待
            int temp=n.finish_time+Start-Customer[i].arr_time;
            if(temp>0){
                Customer[i].wait_time=temp;
            }
            else Customer[i].wait_time=0;

3、4步维护总等待时间，当当前顾客到达时间>=17.，结束啦！

注意点：

时间以s统一界定，以免逻辑上把自己给绕晕；
构造数据结构node，存放每个顾客的到达时间，等待时间，结束时间，以及处理时间；

构造优先队列priority_queue,重载<号，结束时间早的优先；

struct node
{
    int arr_time;
    int wait_time;//以s计算的等待时间
    int finish_time,p_time;//以s计算的结束时间与处理时间

    friend bool operator <(const node&a,const node&b){
        return a.finish_time>b.finish_time;
    };

}Customer[10005];
priority_queue <node> Lines;

eg2.1014 Waiting in Line (30 分)

题意：输入窗口数，黄线内每个队伍的最大人数，顾客数与查询数；输入顾客的处理时间，8.开始处理，17.后不接受处理，计算每个顾客处理结束的时间；
思路：

构造顾客数据结构，存放处理时间与结束时间；

queue[i]作为窗口，存放在黄线内的顾客；

struct node
{
    int pro_time;
    int fin_time;
    node(int _p,int _f)
    {
        pro_time=_p;
        fin_time=_f;
    }
};

queue<node> Lines[25];

flag_time[25]数组表示每个窗口队首的结束时间，wf_time[1005]存放K个顾客的结束时间；

填满黄线内窗口空位M*N，一旦进入黄线，结束顾客结束时间确定，即队列顾客back的结束时间+当前顾客的处理时间，更新flag_time与wf_time;

bool ff=true;
    for(int i=0;i<M&&ff;i++){
        for(int j=0;j<N;j++){
            int temp_time;
            if(Lines[j].size()==0)temp_time=0;
            else temp_time=Lines[j].back().fin_time;
            Lines[j].push(node(p_time[index],p_time[index]+temp_time));
            flag_time[j]=Lines[j].front().fin_time;
            if(temp_time>=540)wf_time[index]=-1;//开始的时间在17.及之后
            else wf_time[index]=p_time[index]+temp_time;
            index++;
            if(index>K){
                    ff=false;break;
            }
        }
    }

黄线外顾客进入队列,首先找到flag_time[]中的最小值，因为最小即该队列最先会有人结束，记录窗口值，队首顾客出队，下一个顾客进队，更新flag_time与wf_time;

for(int i=index;i<K;i++){
        //找到flag_time中的最小值
        int Min=flag_time[0];
        int Min_index=0;
        for(int w=1;w<N;w++){
            if(flag_time[w]<Min){
                Min=flag_time[w];
                Min_index=w;
            }
        }

        //第Min_index个窗口最先处理完
        int temp_time=Lines[Min_index].back().fin_time;
           // cout<<temp_time<<" "<<p_time[index]<<endl;
        Lines[Min_index].pop();
        Lines[Min_index].push(node(p_time[index],p_time[index]+temp_time));
        flag_time[Min_index]=Lines[Min_index].front().fin_time;
        if(temp_time>=540)wf_time[index]=-1;//开始的时间在17.及之后
        else wf_time[index]=p_time[index]+temp_time;
        index++;
    }

注意点：

if-else，当顾客的开始处理时间在17.及之后，直接忽略了；
eg3. 1026 Table Tennis (30 分)

多项式

eg1. 1002 A+B for Polynomials (25 分)

eg2. 1009 Product of Polynomials (25 分)

题意：输入指数与系数，求两个多项式的和（或乘积）；按指数从大到小输出非零项；
思路：map<int,double>a,b作为输入的A、B多项式；map<int,double,greater >作为结果（加入greater表示按key值从大到小排列）；
pair用法:make_pair(x,y);pair->first
map用法:每个key在map中只能出现一次；mp.insert(pair);mp.erase(iter);mp.size();

计算树的叶子结点

eg1. 1004 Counting Leaves (30 分)

题意：家谱树，计算每层没有孩子的成员，即计算树的每层叶子结点树；输入树中结点总数N，以及叶子结点数M；输出M个非叶子结点的K个孩子；输出各层叶子结点的个数；
思路：

数据结构树的结点使用vector存放孩子列表，层数以及当前index；

树的BFS queue;依次将树结点压入队列，同一层的拥有一样的父母结点，都会挤在一起；

void Layer_Tra()
{
    queue<node> q;
    int leavenum=0;
    q.push(Family[1]);
    while(!q.empty()){
        node n=q.front();
        q.pop();
        if(n.children.size()==0){
            leaves[n.level]++;
        }
        now_level=n.level;
       // cout<<now_level<<endl;
        for(int i=0;i<n.children.size();i++){
            Family[n.children[i]].level=n.level+1;
            //node temp=Family[n.children[i]];
            q.push(Family[n.children[i]]);
        }
    }
}

eg2. 1094 The Largest Generation (25 分)

题意：同上题，计算的是有最多成员的成员值以及层数；
思路：同样是使用BFS，用level更新孩子们所在层数，同时用数组[parent.level+1]来维护该层结点的个数；

计算最佳路径（图的DFS）

eg1. 1003 Emergency (25 分)

题意：输入城市数N、路径数M、in and save city,N个城市的rescue数，M条路径；找出最短路径的长度，以及在路上可以收集的最大rescue teams；输出最短路径的数量以及最大值；
思路：

构建一张有权无向图，求路径最短及节点上值和最大的路径；

DFS(start,end)

if(index==End){
    ...
    return;
}
for(int i=0;i<N;i++){
                if(Map[index][i]!=0&&flag[i]==false){
                    flag[i]=true;
                    length+=Map[index][i];
                    rescueSum+=rescueNum[i];
                    DFS(i,End);
                    flag[i]=false;
                    length-=Map[index][i];
                    rescueSum-=rescueNum[i];
                }
            }

注意点：
1.在进入DFS函数前初始化，将起点flag[C1]置为true等：

1
2
3

rescueSum+=rescueNum[C1];
flag[C1]=1;
DFS(C1,C2);

时间的比较

题意：输入记录：ID+到达时间+离开时间，分别找到最早到与最晚离开的同学，输出ID；
思路：
pair的妙用:first存时间，second存学号；max与min比较的是first字段；时间字符串直接按字典序比较；

typedef pair<string,string> tlog;
tlog ear = tlog(b,a),las = tlog(c,a); 
	for (int i=1;i<n;i++)
	  {
	  	cin >> a >> b >> c;
	    ear = min(ear,tlog(b,a));//# include <algorithm>
	    las = max(las,tlog(c,a));
	  }
cout << ear.second << ' ' << las.second << endl;

大数+二分查找

题意：输入2个数以及其中一个数的进制，找到使这两个数相等的另一个数的进制；
思路：

字符串输入，转换成10进制比较；
二分查找；

注意点：

转换成10进制时，有可能溢出，需要判断；
二分查找的范围是当前值各个位数中的最大值+1，已知进制值的这个数+1（不可能比这个数更大了，因为这时表示为10）；
数据结构
Stack
1051 Pop Sequence (25 分)
判断pop序列是否正确

思路:

模拟1~N的入栈，以current指向序列首位；遇到相同的则出栈，current后移；

当超出栈容量或者全入栈后，current不为N时，则序列不正确；

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int main(){
    int M,N,K;// stack的最大容量，push长度，数量
    vector<int> popList;// pop序列
    vector<int> myStack;// 栈
    scanf("%d%d%d",&M,&N,&K);
    while(K--){
        int num;
        popList.clear();
        myStack.clear();
        // 输入pop序列
        for(int i=0;i<N;i++){
            scanf("%d", &num);
            popList.push_back(num);
        }
        int current=0;// 指向popList当前位置
        bool flag=true;// 标记
        for(int i=1;i<=N;i++){
            myStack.push_back(i);// 入栈
            // 超过最大容量
            if(myStack.size()>M){
                flag=false;
                break;
            }
            // 当发现当前栈元素与popList头部元素相似
            while(!myStack.empty()&&myStack.back()==popList[current]){
                myStack.pop_back();
                current++;
            }
        }
        //当popList没有遍历完全或者超出最大容量
        if(current!=N||flag==false){
            cout<<"NO"<<endl;
        }
        else cout<<"YES"<<endl;
    }
    return 0;
}

Queue

1056 Mice and Rice (25 分)

思路:

题目看了很久才理解;
使用一个队列存放参赛者名单，pop首部来模拟小组比赛，将获胜者push到队列尾巴，知道队列中只剩一个笑到最后的玩家;

注意在模拟每一局比赛时，固定初始队列大小，而不是动态获取；

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;
const int MAX=1010;
struct node
{
    int Weight;
    int Rank;
    int Pos;
}Input[MAX];

int main(){
    int NP,NG;//参赛者数，小组人数
    queue<node> mice;// 存放参加比赛的老鼠
    cin>>NP>>NG;
    for(int i=0;i<NP;i++){
        cin>>Input[i].Weight;
        Input[i].Pos=i;
    }
    //将初始比赛序列放入队列
    int p;
    for(int i=0;i<NP;i++){
        cin>>p;
        mice.push(Input[p]);
    }
    while(!mice.empty()){
        //当队列中只剩一个
        if(mice.size()==1){
            node temp=mice.front();
            Input[temp.Pos].Rank=1;
            break;
        }
        int groupNum=mice.size()/NG;//比赛数
        if(mice.size()%NG!=0)groupNum+=1;//剩余的归于一组
        int oneTimeNum=mice.size();//记录本轮参与者数量
                                   //直接使用mice.size()会在一组比赛结束后发生变化(得到获胜者，插入到队列中后
        for(int i=0;i<groupNum;i++){
            int winPosition;
            int maxW=-1;
            int memberNum=NG;
            // 最后一组特殊情况考虑
            if(i==groupNum-1&&oneTimeNum%NG!=0){
                memberNum=oneTimeNum%NG;
            }
            for(int j=0;j<memberNum;j++){
                node temp=mice.front();
                mice.pop();
                if(maxW<temp.Weight){
                    maxW=temp.Weight;
                    winPosition=temp.Pos;
                }
                Input[temp.Pos].Rank=groupNum+1;
            }
            mice.push(Input[winPosition]);
        }
    }
    // 输出
    for(int i=0;i<NP;i++){
        if(i!=0)cout<<" ";
        cout<<Input[i].Rank;
    }
    return 0;
}

LinkList

1052 Linked List Sorting (25 分)

思路：

按order排序，按序输出；
有效node的order为key值，无效node的order设为最大值，则在排序时会排到后面去；

注意：需要对原链表遍历处理，清除无效结点；当有效结点值为空的输出；

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX = 100010;
struct node {
    int add,key,next;
    int order;

}myList[MAX];
int N,head;

bool cmp(node a,node b)
{
    return a.order<b.order;
}

int main(){
    // 初始化，使空结点值排到后面
    for(int i=0;i<MAX;i++){
        myList[i].order=MAX;
    }
    scanf("%d%d",&N,&head);
    // 输入N个结点
    int address,key,nextadd;
    for(int i=0;i<N;i++){
        scanf("%d%d%d",&address,&key,&nextadd);
        myList[address].add=address;
        myList[address].key=key;
        myList[address].next=nextadd;
    }
    int temp=head;
    int vaild=0;
    while(temp!=-1){
        vaild++;
        myList[temp].order=myList[temp].key;
        temp=myList[temp].next;
    }
    N=vaild;
    if(N==0){
        printf("%d %d\n",N,-1);
        return 0;
    }
    sort(myList,myList+MAX,cmp);
    printf("%d %05d\n",N,myList[0].add);
    for(int i=0;i<N-1;i++){
        printf("%05d %d %05d\n",myList[i].add,myList[i].key,myList[i+1].add);
    }
    printf("%05d %d %0d\n",myList[N-1].add,myList[N-1].key,-1);
    return 0;
}

贪心

1033 To Fill or Not to Fill (25 分)

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;
const double MAX=10000000000;
struct node
{
    double price;
    double dis;
}gasStation[505];

bool cmp(node a,node b)
{
    return a.dis<b.dis;
}

int main(){
    double Cmax,D,Davg;//车的最大储油量
                      //出发地与目标地之间的距离
                      //每单位油可走的距离
    int N;//N个gas station

    scanf("%lf%lf%lf%d",&Cmax,&D,&Davg,&N);
    for(int i=0;i<N;i++){
        scanf("%lf%lf",&gasStation[i].price,&gasStation[i].dis);
    }
    gasStation[N].dis=D;
    gasStation[N].price=0;
    sort(gasStation,gasStation+N+1,cmp);
    /*for(int i=0;i<=N;i++){
        cout<<i<<" "<<gasStation[i].dis<<" "<<gasStation[i].price<<endl;
    }
    cout<<"*********************"<<endl;*/
    //贪心策略
    //在每一油站判断
    //找到比当前油站price更小的最近可达的油站，加油加到刚好到达该站即可；
    //否则在该站加满油,然后前往可达范围内油价最低的油站；
    double maxLen=Cmax*Davg;//满油状态下的最大里程
    int pos=0;//车到达位置
    double nowGas=0;//当前油量
    double totalPrice=0;//总油价
    double totalLen=0;//总里程
    //当起点没有油站时
    if(gasStation[0].dis!=0){
        cout<<"The maximum travel distance = 0.00"<<endl;
        return 0;
    }
    while(pos<N){
        double lowPrice=MAX;
        int i,tempPos=pos;
        bool flag=false;
        for(i=pos+1;i<=N && gasStation[i].dis-gasStation[pos].dis<=maxLen;i++){
            if (gasStation[i].price < gasStation[pos].price) {//发现可达范围内存在比当前油价低的油站
                double needGas=(gasStation[i].dis-gasStation[pos].dis)/Davg;
                if(nowGas>=needGas){//本来剩余油可达，无需加油啦
                    nowGas-=needGas;
                }
                else {
                    totalPrice+=(needGas-nowGas)*gasStation[pos].price;
                    nowGas=0;
                }
                pos=i;//去往i油站
                totalLen=gasStation[pos].dis;
                flag=true;
                break;
            }
            if(gasStation[i].price < lowPrice){
                lowPrice=gasStation[i].price;
                tempPos=i;
            }
        }
        if(gasStation[pos+1].dis-gasStation[pos].dis>maxLen){//满油也无法到达最近的油站
            printf("The maximum travel distance = %.2lf",totalLen+maxLen);
            return 0;
        }
        if(flag==false){//说明可达范围内没有比当前更便宜的了，充满
            totalPrice+=(Cmax-nowGas)*gasStation[pos].price;
            nowGas=Cmax-(gasStation[tempPos].dis-gasStation[pos].dis)/Davg;
            pos=tempPos;
            totalLen=gasStation[pos].dis;
        }
    }
    printf("%.2lf",totalPrice);
    return 0;
}

1067 Sort with Swap(0, i) (25 分)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <algorithm>
#include <string.h>

using namespace std;
int N;
vector<int>permutation;
void outPut()
{
    for(int i=0;i<N;i++){
        cout<<permutation[i]<<" ";
    }
    cout<<endl;
}

int main(){
    map<int,int>myMap;//存储值与位置关系
    cin>>N;
    int input;
    for(int i=0;i<N;i++){
        cin>>input;
        permutation.push_back(input);
        myMap[input]=i;

    }
    int num=0;
    int j=1;//将j提到前面来，避免不必要的循环判断
    //贪心
    //0当前在哪个位置上，就去找最终应该在这个位置上的值，swap
    while(true&&N!=0){
        int pos=myMap[0];
        //当0在0位置上时，实际上序列还没有完成排序
        //与第一个未呆在正确位置的值swap
        if(pos==0){
            for(j;j<N;j++){//从左到右找到第一个不在本位的值
                if(permutation[j]!=j){
                       // cout<<j;
                    swap(permutation[j],permutation[0]);
                    myMap[0]=j;
                    myMap[permutation[0]]=0;//0与j已交换
                    break;
                }
            }
            if(j==N)break;
        }
        else {
            swap(permutation[myMap[0]],permutation[myMap[pos]]);
            myMap[0]=myMap[pos];
        }
        //outPut();
        num++;
    }
    cout<<num<<endl;
    return 0;
}

树

二叉树的遍历

1020 Tree Traversals (25 分)
1086 Tree Traversals Again (25 分)
已知树的中序遍历、后序(先序)遍历，建树；
思路：(以先序为例)

先序遍历的首位结点为当前数的根结点;
在中序遍历中找到首位结点的位置，将该树分为左子树与右子树2部分;

递归求左右子树，直到当前结点为空;

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;
vector<int>preOrder,inOrder,tempOrder,postOrder;
int N;
struct node
{
    int data;
    node* left;
    node* right;
};

node* CreateTree(int prel,int prer,int inl,int inr)
{
    if(prel<=prer){
        int k;
        //postr即为当前根节点值
        //找到中序排列中根节点的位置
        for(k=inl;k<=inr;k++){
            if(inOrder[k]==preOrder[prel]){
                break;
            }
        }
        //左子树的结点值
        int numLeft=k-inl;
        node* root=new node;
        root->data=inOrder[k];
        root->left=CreateTree(prel+1,prel+numLeft,inl,k-1);
        root->right=CreateTree(prel+numLeft+1,prer,k+1,inr);
        return root;
    }
    return NULL;
}

//后序遍历
void postTraversals(node* root)
{
    if(root==NULL)return;
    postTraversals(root->left);
    postTraversals(root->right);
    postOrder.push_back(root->data);
}

int main(){
    int input;
    char oper[5];
    cin>>N;
    for(int i=0;i<2*N;i++){
        getchar();
        scanf("%s",&oper);
        if(!strcmp(oper,"Push")){
            cin>>input;
            preOrder.push_back(input);
            tempOrder.push_back(input);
        }
        else {
            int in=tempOrder.back();
            tempOrder.pop_back();
            inOrder.push_back(in);
        }
    }
    node* root=CreateTree(0,N-1,0,N-1);
    postTraversals(root);
    for(int i=0;i<N;i++){
        if(i!=0)cout<<" ";
        cout<<postOrder[i];
    }
    return 0;
}

树的遍历

1079 Total Sales of Supply Chain (25 分)

思路:DFS

求供应链中产品从供应商到零售商流动后，得到最终的总价格；

即DFS遍历求每个叶子结点的深度；
1090 Highest Price in Supply Chain (25 分)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;

struct node
{
    int products;
    vector<int> child;
}supplyChain[100001];

int N;//结点数
double P,r;//根节点的初始价格，每层增加的百分比
double sum=0;

void DFS(int root,int level)
{
    if(supplyChain[root].child.size()==0){//到达根节点
        sum+=pow(r,level)*supplyChain[root].products*P;
        return;
    }
    for(int i=0;i<supplyChain[root].child.size();i++){
        DFS(supplyChain[root].child[i],level+1);
    }
}

int main(){
    scanf("%d%lf%lf",&N,&P,&r);
    r=(double)1+r/100;
    int k,input;
    //输入
    for(int i=0;i<N;i++){
        cin>>k;
        if(k==0){
            cin>>supplyChain[i].products;
        }
        else {
            for(int j=0;j<k;j++){
                cin>>input;
                supplyChain[i].child.push_back(input);
            }
        }
    }
    //DFS求层数
    DFS(0,0);
    printf("%.1lf",sum);
    return 0;
}

The Largest Generation (25 分)
求拥有最大结点数的level
1004 Counting Leaves (30 分)
求树的每层叶子结点数,可用DFS或BFS；

思路:（BFS）

使用一个queue做BFS，一个level[i]数组存储i结点所在的层数,一个res[i]数组存储i层的叶子节点数;
pop出当前结点;for循环得出当前结点的孩子结点，此时设置孩子结点的level为当前结点level+1;

当当前结点孩子数为空，则为叶子结点，res[level]++;

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

using namespace std;

int N,M;//总结点数，非叶子结点数

vector<int> myTree[105];
int res[105]={0};
int level[105]={0};//各结点所处的层号
int maxlevel=-1;

void BFS(int root)
{
    queue<int>myQueue;
    myQueue.push(root);
    while(!myQueue.empty()){
        int temp=myQueue.front();
        myQueue.pop();
        maxlevel=max(maxlevel,level[temp]);
        if(myTree[temp].size()==0){
            res[level[temp]]++;
        }
        for(int i=0;i<myTree[temp].size();i++){
            level[myTree[temp][i]]=level[temp]+1;
            myQueue.push(myTree[temp][i]);
        }
    }
}

int main(){
    cin>>N>>M;
    int id,k;//结点id，子节点数
    int input;
    memset(res,0,sizeof(res));
    for(int i=0;i<M;i++){
        cin>>id>>k;
        for(int j=0;j<k;j++){
            cin>>input;
            myTree[id].push_back(input);
        }
    }
    level[1]=1;
    BFS(1);
    for(int i=1;i<=maxlevel;i++){
        if(i!=1)cout<<" ";
        cout<<res[i];
    }
    return 0;
}

二叉搜索树BST

1043 Is It a Binary Search Tree (25 分)
判断给定序列是否为BST，或者BST的镜像;

思路:

边输入值，边构建二叉搜索树,判断当前插入在root的左子树或右子树;

构建完树后进行先序遍历与镜像先序遍历，判断是否与输入初始序列相同;

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

using namespace std;

int N;
struct node
{
    int data;
    node* left;
    node* right;
};
node* myRoot=NULL;
int original[1005],pre[1005],preMirror[1005],post[1005],postMirror[1005];
int iindex=0;

void CreatBST(node* &root,int data)
{
    if(root==NULL){//当根结点为空
        root=new node;
        root->data=data;
        root->left=NULL;
        root->right=NULL;
        return;
    }
    if(data>=root->data){//插入到右子树中
        CreatBST(root->right,data);
    }
    else {//插入到左子树
        CreatBST(root->left,data);
    }
}

void preOrder(node* root)
{
    if(root==NULL){
        return;
    }
    pre[iindex++]=root->data;
    preOrder(root->left);
    preOrder(root->right);
}

void preMirrorOrder(node* root)
{
    if(root==NULL){
        return;
    }
    preMirror[iindex++]=root->data;
    preMirrorOrder(root->right);
    preMirrorOrder(root->left);
}

bool isSame(int a[],int b[])
{
    for(int i=0;i<N;i++){
        if(a[i]!=b[i])return false;
    }
    return true;
}

void postOrder(node* root)
{
    if(root==NULL){
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    post[iindex++]=root->data;
}

void postMirrorOrder(node* root)
{
    if(root==NULL){
        return;
    }
    postMirrorOrder(root->right);
    postMirrorOrder(root->left);
    postMirror[iindex++]=root->data;
}

int main(){
    cin>>N;
    int data;
    for(int i=0;i<N;i++){
        cin>>data;
        CreatBST(myRoot,data);
        original[i]=data;
    }
    //先序遍历
    preOrder(myRoot);
    //镜像BST的先序遍历
    iindex=0;
    preMirrorOrder(myRoot);
    if(isSame(original,pre)){
        cout<<"YES"<<endl;
        iindex=0;
        postOrder(myRoot);
        for(int i=0;i<N;i++){
            if(i!=0)cout<<" ";
            cout<<post[i];
        }
    }
    else if(isSame(original,preMirror)){
        cout<<"YES"<<endl;
        iindex=0;
        postMirrorOrder(myRoot);
        for(int i=0;i<N;i++){
            if(i!=0)cout<<" ";
            cout<<postMirror[i];
        }
    }
    else cout<<"NO"<<endl;
    return 0;
}

完全二叉排序树CBST

1064 Complete Binary Search Tree (30分)
构建一棵CBST

思路：CBST的特点：如果使用数组存放完全二叉树（即层序存放的结果），那么对于x结点，其左孩子结点为2x，右孩子结点为2x+1（假设存在）;

#include <iostream>
#include <algorithm>

using namespace std;
int data[1001],tree[1001];
int pos=1;
int N;//N<=1000
//使用中序遍历方法构建CBST
void CreateCBST(int root)
{
    if(root>N)return;
    int l=2*root;
    int r=2*root+1;
    CreateCBST(l);
    tree[root]=data[pos++];
    CreateCBST(r);
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>data[i];
    }
    sort(data+1,data+N+1);
    CreateCBST(1);
    for(int i=1;i<=N;i++){
        if(i!=1)cout<<" ";
        cout<<tree[i];
    }
    return 0;
}

平衡二叉树AVL

1066 Root of AVL Tree (25 分)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

using namespace std;
int N;//结点数
struct node
{
    int data;
    int height;//当前结点高度
    node* left;
    node* right;
};

//获取以root为根结点的树的高度
int getHeight(node* root)
{
    if(root==NULL)return 0;
    return root->height;
}

//更新高度
void updateHeight(node* &root)
{
    root->height=max(getHeight(root->left),getHeight(root->right))+1;
}

//获取以root为根结点的树的平衡因子
//左子树高度-右子树高度
int getBF(node* root)
{
    return getHeight(root->left)-getHeight(root->right);
}

//左旋(逆时针
void L(node* &root)
{
    node* temp=root->right;//temp为旋转后的根结点
    root->right=temp->left;//temp结点的左子树放在root结点的右子树位置
    temp->left=root;//temp的左子树改为root
    //更新高度
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}

//右旋(顺时针
void R(node* &root)
{
    node* temp=root->left;//temp为旋转后根节点
    root->left=temp->right;//temp的右子树放在root结点的左子树位置
    temp->right=root;
    //更新高度
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}

void insertNode(node* &root,int data)
{
    if(root==NULL){
        root=new node;
        root->data=data;
        root->left=NULL;
        root->right=NULL;
        updateHeight(root);
        return;
    }
    if(data<root->data){//插入左子树
        insertNode(root->left,data);
        updateHeight(root);
        if(getBF(root)==2){
            if(getBF(root->left)==1){
                R(root);
            }
            else if(getBF(root->left)==-1){
                L(root->left);
                R(root);
            }
        }
    }
    else {
        insertNode(root->right,data);
        updateHeight(root);
        if(getBF(root)==-2){
            if(getBF(root->right)==-1){
                L(root);
            }
            else if(getBF(root->right)==1){
                R(root->right);
                L(root);
            }
        }
    }
}

int main(){
    cin>>N;
    int data;
    node* myRoot=NULL;
    for(int i=0;i<N;i++){
        cin>>data;
        insertNode(myRoot,data);
    }
    cout<<myRoot->data;
    return 0;
}

并查集

1107 Social Clusters (30 分)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

using namespace std;
int pre[1005];
int hobby[1005];
int isRoot[1005];//每个门派中人数
int N,K;//总人数，爱好数
//初始化,将所有的掌门人设为本身
void init()
{
    for(int i=1;i<=N;i++){
        pre[i]=i;
        hobby[i]=0;
        isRoot[i]=0;
    }
}

int findRoot(int root)
{
    int son,temp;
    son=root;
    //找到最上层掌门人
    while(root!=pre[root]){
        root=pre[root];
    }
    //路径压缩
    //将这条路上遇到的结点pre[x]都直接设置为root
    while(son!=root){
        temp=pre[son];
        pre[son]=root;
        son=temp;
    }
    return root;
}

void Union(int a,int b)
{
    int root1=findRoot(a);
    int root2=findRoot(b);
    if(root1!=root2){
        pre[root1]=root2;
    }
}

bool cmp(int a,int b)
{
    return a>b;
}

int main(){
    int h;
    cin>>N;
    init();
    for(int i=1;i<=N;i++){
        scanf("%d:",&K);
        for(int j=0;j<K;j++){
            cin>>h;
            if(hobby[h]==0){//目前没有人有这个爱好
                hobby[h]=i;
            }
            Union(i,hobby[h]);
        }
    }
    //统计属于同一门派的人数
    for(int i=1;i<=N;i++){
        isRoot[findRoot(i)]++;
    }
    //统计门派数量
    int ans=0;
    for(int i=1;i<=N;i++){
        if(isRoot[i]!=0)ans++;
    }
    cout<<ans<<endl;
    //从大到小排序
    sort(isRoot+1,isRoot+N+1,cmp);
    //输出
    for(int i=1;i<=ans;i++){
        if(i!=1)cout<<" ";
        cout<<isRoot[i];
    }
    return 0;
}

1013 Battle Over Cities (25分)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

using namespace std;

vector<int> myMap[1050];// map
int N,M,K;// number of cities < 1000
          // number of remaining highways
          // checked cities
int father[1050];// 存放掌门结点
int rootSet[1050];// 存放i掌门人所处派别人数

// 初始化
// 将所有结点的掌门人设为本身
void init(int num)
{
    for(int i=1;i<=num;i++){
        father[i]=i;
        rootSet[i]=0;
    }
}

int findRoot(int son)
{
    int root=son;
    while(root!=father[root]){
        root=father[root];
    }
    int temp;
    //路径压缩
    while(son!=root){
        temp=father[son];
        father[son]=root;
        son=temp;
    }
    return root;
}

void Union(int x,int y)
{
    int rootx=findRoot(x);
    int rooty=findRoot(y);
    if(rootx!=rooty){
        father[rootx]=rooty;
    }
}

// 并查集法求连通块数
int main(){
    cin>>N>>M>>K;
    int x,y;
    int block=0;
    for(int i=0;i<M;i++){
        cin>>x>>y;
        myMap[x].push_back(y);
        myMap[y].push_back(x);
    }
    int concern;
    for(int index=0;index<K;index++){
        init(N);
        block=0;
        cin>>concern;
        // 枚举每条边
        for(int i=1;i<=N;i++){
            for(int j=0;j<myMap[i].size();j++){
                if(i==concern||myMap[i][j]==concern)continue;
                Union(i,myMap[i][j]);
            }
        }
        // 统计不同的门派人数
        for(int i=1;i<=N;i++){
            if(i==concern)continue;
            rootSet[findRoot(father[i])]++;
        }
        for(int i=1;i<=N;i++){
            if(rootSet[i]!=0)block++;
        }
        cout<<block-1<<endl;
    }
    return 0;
}

大数+二分查找

模拟题:
考虑数据结构
一般思路：从一般到特殊

窗口排队模拟

eg1. 1017 Queueing at Bank (25 分)

eg2.1014 Waiting in Line (30 分)

eg3. 1026 Table Tennis (30 分)

多项式

eg1. 1002 A+B for Polynomials (25 分)

eg2. 1009 Product of Polynomials (25 分)

计算树的叶子结点

eg1. 1004 Counting Leaves (30 分)

eg2. 1094 The Largest Generation (25 分)

计算最佳路径（图的DFS）

eg1. 1003 Emergency (25 分)

时间的比较

eg. 1006 Sign In and Sign Out (25 分)

大数+二分查找

数据结构

Stack

Queue

LinkList

贪心

树

二叉树的遍历

树的遍历

二叉搜索树BST

完全二叉排序树CBST

平衡二叉树AVL

并查集