PAT甲级备考总结C++-创新互联

数据结构 —— 图解AVL树(平衡二叉树)
考的基本为建树，熟练不平衡时的判断以及调整即可
A1066 Root of AVL Tree
A1123 Is It a Complete AVL Tree

const int N = 30;
int l[N],r[N],v[N],h[N],idx;

void update(int u)
{h[u] = max(h[l[u]],h[r[u]])+1;
}
void R(int& u)
{int p = l[u];
    l[u] = r[p];
    r[p] = u;
    update(u),update(p);
    u = p;
}

void L(int& u)
{int p = r[u];
    r[u] = l[p];
    l[p] = u;
    update(u),update(p);
    u = p;
}
int get_balance(int u)
{return h[l[u]] - h[r[u]];
}
void insert(int& u,int w)
{if(!u)  u = ++idx, v[u] = w;
    else if(w< v[u])
    {if(!u)
        {u = ++idx;
            v[u] = w;
        }
        else if(w< v[u])
        {insert(l[u],w);
            if(get_balance(u) == 2)
            {if(get_balance(l[u] == 1))//LL型
                    R(u);
                else
                    L(l[u]),R(u);
            }
        }
        else
        {insert(r[u],w);
            if(get_balance(u) == -2)
            {if(get_balance(r[u] == -1))//RR型
                    L(u);
                else
                    R(r[u]),L(u);
            }
        }
    }
    update(u);
}

考的一般都是判断是否为二叉搜索树，可以利用递归判断，从root开始遍历，以左孩子为 2k，右孩子为 2k+1来存放遍历的结果，假设元素个数为n，当递归完二叉树，判断数组序列下标大值，如果大于n则证明该树并非完全二叉树
如该题：A1110 Complete Binary Tree

int maxk,maxid;

void dfs(int u,int k)
{if(u == -1)    return;
    
    if(k >maxk)
    {maxk = k;
        maxid =u;
    }
    dfs(l[u],k*2);
    dfs(r[u],k*2+1);
}

二叉搜索树的性质
通常考的是二叉搜索树的建树与判断是否为二叉搜索树，给前序遍历或者后序遍历来要求你建树。根据性质可以直接sort()给定的序列即得到该树的中序遍历，已经有了两个序列则转化为普通的二叉树建树过程。
最后依据性质来判断即可。

注意点：在find的过程中需要注意路径压缩，否则有一些题目卡测试点

int p[N];

int find(int x)
{if(x != p[x])   p[x] = find(p[x]);
    return p[x];
}
void Union(int a,int b)
{int pa = find(a),pb = find(b);
    if(pa != pb)    p[pa] = pb;
}

考的都比较最基本，如果考到了这种需要存储每个结点的父节点
做法：先初始化每个结点的高度，和每个结点的父节点，若两个查询的高度不一样，则先把最低点更新至与另一个结点的高度相同，然后不断向上走，走到公共点则结束
1151 LCA in a Binary Tree

1143 Lowest Common Ancestor

根据给定的顶点数来判断用哪种方式建图，当顶点数大于1e5时则用邻接表来建图

以下两种为基础，考难点的还有二维Dijkstra，或者记录路径

利用二维矩阵存储

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{memset(dist, 0x3f, sizeof dist);//在开始的时候需要将所有距离初始化为正无穷
    dist[1] = 0;

    for (int i = 0; i< n - 1; i ++ )
    {int t = -1;
        for (int j = 1; j<= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] >dist[j]))
                t = j;

        for (int j = 1; j<= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;//表示不可达
    return dist[n];
}

利用邻接表存储

int dij(int index){s[index] = 0;
    priority_queue,greater>hp;
    hp.push({0,index});//存储距离 当前点

    while(hp.size()){auto t = hp.top();
        hp.pop();

        int v = t.second;
        if(st[v]) continue;
        st[v] = true;
        for(int u = 0; u< g[v].size(); u ++ ){int c = g[v][u].first;
            int dis = g[v][u].second;
            if(!st[c] && s[v] + dis< s[c]){s[c] = s[v] + dis;
                hp.push({s[c],c});
            }
        }
    }
    if(s[n] == inf) return -1;
    return s[n];
}

如拓扑序列等等

例如在PAT甲级的一些题里面要求有理数加减乘除，分式加减乘除，化简的时候gcd是必不可少的。可以直接调用algorithm库里的gcd函数来求大公约数，同时可求出最小公倍数。

#include#include

using namespace std;

int lcm(int a, int b)
{return a * b / __gcd(a, b);
}
int main()
{int a,b;
	cin>>a>>b;
	cout<<__gcd(a,b)<

const int N= 1e6 + 10;

int primes[N], cnt;//primes[]存储的是1~N的所有质数
bool st[N];

void get_primes(int n)
{for(int i=2;i<=n;i++)
    {if(!st[i])
        {primes[cnt++]=i;
        }
        for(int j=0;primes[j] * i<= n ;j++)
        {st[primes[j] * i ] = true;
            if(i % primes[j]==0)    break;
        }
    }
}

bool is_prime(int x)
{if(x<2) return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
            return false;
    return true;
}