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

前提

10月份报了PAT甲级,顺便报了Acwing的PAT甲级辅导课,在考试之前汇总下自己刷题的感觉加上必须掌握的知识点
原文链接:PAT甲级备考总结C++

站在用户的角度思考问题,与客户深入沟通,找到连平网站设计与连平网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、成都网站建设、企业官网、英文网站、手机端网站、网站推广、空间域名、雅安服务器托管、企业邮箱。业务覆盖连平地区。几个小总结
  1. 速度问题
    在输入输出数据量大于1e5时,尽量不要怕麻烦用 scanf 与 printf。
    当数据量比较大时,可以使用ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);来提高输入输出速度。但需要避免cin cout 与 scanf printf 的混用
  2. 当题目中要存字符串,卡时间时,需要将string替换成char[]数组来存储。
  3. 格式化时间处理问题,算打电话价钱的等等问题,可以考虑的是将时间转换为秒,可方便操作。
  4. 当模拟区间,如求进制的话,范围比较大,看是否可以二分,枚举区间比较大时,就可以考虑是否可以二分
  5. 判断是否高精度,当数据超过 int 大1e9 long long 1e18 超过则用。
  6. stringstream可用于字符串的处理,当作输入流来分别处理字符串与数字
  7. 模拟题,如求学生成绩等等之类,数据量比较大,如求几所学校学校学生的平均成绩,最后转化为int做比较,当数据量比较大的时候,double会出现精度问题的误差,如最后为89.9999999999999最终结果应为90.可以加个很小的数eps = 1e-8,再取整
    如:A1141 PAT Ranking of Institutions
链表

考的链表题一般为要求反转,排序等等之类,最好用数组模拟链表,用链表实现反而麻烦。

栈、队列、哈希表

以上可以灵活使用 STL即可解题

树 存储方式
  1. 利用数组 l[ ],r[ ]存储左孩子右孩子,N为结点个数。

  2. 如果题目要求回溯,如判断两个结点是否是兄弟结点等等的题,可以多创建个数组p[ ],表示存储第 i 个下标结点的父亲是p[i]。方便回溯

  3. depth[ ]数组可记录结点 i 的深度,如用于判断两个结点是否属于同一层

  4. floor_num[ ]数组可记录第i层共有多少个结点,在判断完全二叉树或完美二叉树的题目可利用完全二叉树性质 来解题
    如该题 A1159 Structure of a Binary Tree

const int N = 1e5;//结点个数
int l[N],r[N];//下标为i 的左儿子为 l[i] 右儿子为r[i]
int p[N];//下标为 i 的父节点为p[i]
int depth[N];//记录结点i的深度
int floor_num[N];//记录第i层共有多少个结点

void init()
{memset(l,-1,sizeof l);
	memset(r,-1,sizeof r);
	memset(p,-1,sizeof p);
}
建树

当题目给权重而非下标序列,如前中序遍历建树,可以将权重映射为下标,再利用下标会简单一些

映射过程
#includeunordered_mappos;//记录权重为w的结点的下标为i
int in[N],pre[N],seq[N];//seq存储的是中序遍历的序列 可通过i直接找到权值
int n;//点数
void convert()
{for(int i=0;iin[i] = i;
        pos[seq[i]] = i;
    }
    for(int i=0;i
前序 + 中序
//il为中序遍历左端点 ir为右端点 pl为前序遍历左端点 pr为右端点
int build(int il,int ir,int pl,int pr)
{if(pl >pr) return -1;
    int k = pre[pl];//k既为root 又为下标
    if(il< k) l[k] = build(il,k-1,pl+1,pl+1+k-1-il);
    if(k< ir) r[k] = build(k+1,ir,pl+1+k-1-il+1,pr);
    return k;
}
中序 + 后序
//il为中序遍历左端点 ir为右端点 pl为后序遍历左端点 pr为右端点
int build(int il, int ir, int pl, int pr, int d){if(pl >pr) return -1;
    int k = post[pr];
    if(il< k) l[k] = build(il, k - 1, pl, pl + k - il - 1, d + 1);
    if(k< ir)  r[k] = build(k + 1, ir, pl + k - il, pr - 1, d + 1);
    return root;
}
遍历 前序遍历 中序遍历 后序遍历

通过递归即可

层序遍历
void bfs(int root)
{queueq;
    vectorv;
    q.push(root);
    while(q.size())
    {int t=q.front();
        q.pop();
        v.push_back(t);
        if(l.count(t))  q.push(l[t]);
        if(r.count(t))  q.push(r[t]);
    }
    for(int i=0;iif(i)   cout<<' ';
        cout<
AVL

数据结构 —— 图解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);
}
二叉搜索树BST

二叉搜索树的性质
通常考的是二叉搜索树的建树与判断是否为二叉搜索树,给前序遍历或者后序遍历来要求你建树。根据性质可以直接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;
}
LCA

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

1143 Lowest Common Ancestor

图 建图

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

Dijkstra算法

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

朴素版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];
}
堆优化的Dijkstra算法

利用邻接表存储

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)<
筛质数–求1~N的所有质数

利用欧拉筛法

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;
        }
    }
}
判断是否为质数

如求A1096 Consecutive Factors连续因子或分解质因数的题会用到。
注意循环过程最好使用 i<= x / i,用i * i<= x在i很大的时候可能会爆 int,用sqrt(x) 时每次都需要开次方速度反而慢

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;
}
常用库函数
  • round() 四舍五入函数
  • floor() 不大于自变量的大整数
  • ceil() 不小于自变量的大整数

均在cmath库里

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前标题:PAT甲级备考总结C++-创新互联
文章起源:http://myzitong.com/article/dpjids.html