锐客网

  1. 首页 > 睿知 > it技术 > >

PAT甲级|PAT甲级备战-高精度和排序

c++PAT甲级

高精度 多项式

  • 怎么用数组表示多项式
将数组的索引作为指数
将数组中的内容作为多项式的系数
  • 多项式乘法
double a[N],b[N],c[2*N]; for(int i=0; i

在向量b中逆序存放向量a
vector b(a.rbegin(), a.rend());

高精度加法模板（vector）
vector add(vector u,vector v){ vector uu(u.rbegin(),u.rend()); vector vv(v.rbegin(),v.rend()); vector c; for(int i=0,t=0; i


进制转换（将r进制转换成十进制）(秦九韶算法)
int get(char c) { if (c <= '9') return c - '0'; return c - 'a' + 10; }LL calc(string n, LL r) { LL res = 0; for (auto c : n) { if ((double)res * r + get(c) > 1e16) return 1e18; res = res * r + get(c); } return res; }

一直输入n直到n为负数截止
while(cin>>n,n>0){}

秦九韶算法 z = z*d+y d为需要向十进制转换的进制 y为此进制下的每一项
  • 对于读入的数据，如果需要根据数据类型进行不同的运算，比如读入的是数字就加1，如果是字母就返回ascii，那么我们可以先把数据存放到 **stringstream **里，然后再保存到其他数据类型中。
string s; cin>>s; stringstream ss(s); int a; string b; ss>>a; ss>>b;

排序 技巧
对于模拟题，我们只需要考虑两个事情，1 怎么存数据 2 怎么模拟
round()四舍五入
count() 哈希表中查找是否存在，存在为1
【PAT甲级|PAT甲级备战-高精度和排序】容器中升降序排序
sort(Array.begin(),Array.end(),greater<类型>()); //降序 sort(Array.begin(),Array.end(),less<类型>()); //升序或者自定义cmp函数 bool cmp(int a,int b){ return a>b; } sort(p[i].begin(),p[i].end(),cmp);

当使用getline读入一行时，如果前面有cin，需要使用getchar()吞掉上一个回车
getline配合stringstream可以遍历以空格为分隔的一串字符串
输入a b c d string line; getline(cin,line); string key; stringstream ss(line); while(ss>>key)

s = ss.substr(index); 截取ss字符串index位置后的字符串给s
结构体排序 重载操作符
struct Student{ string id; int score; int position; int localrank,allrank; bool operator<(const Student& t)const{ if(score!=t.score) return score>t.score; else return id

定义结构体后记得写 ;
堆排序
如何手撸一个堆？
首先，堆是一个完全二叉树，且分为小根堆（子节点小于父母节点）和大根堆（子节点大于父母节点）。
那用什么来存入一个堆呢？一维数组！
对于一个一维数组a[] ，n[1]表示根节点，a[2n]和a[2n+1]分别为a[n]的左右子节点。
对于一个堆来说，我们有两个操作，down()操作和up()操作，这两个操作的组合（时间复杂度均为logn）可以实现对堆的一切修改。
对于小根堆:
**down()**操作：将某一个节点的值变大，堆重新调整，该节点下移
**up()**操作：将某一个节点的值变小，堆重新跳整，该节点上移
PAT甲级|PAT甲级备战-高精度和排序
文章图片

堆排序：每次输出堆顶
PAT甲级|PAT甲级备战-高精度和排序
文章图片

#include using namespace std; const int N = 100010; int h[N],size_; int n,m; void down(int u){ int t = u; if(2*u<=size_&&h[t]>h[2*u]) t = 2*u; if(2*u+1<=size_&&h[t]>h[2*u+1]) t = 2*u+1; //两个if找出三个节点中最小的节点，用这个节点和父节点交换 if(u!=t){ swap(h[u],h[t]); down(t); } } int main(){ cin>>n>>m; for(int i=1; i<=n; i++){ int k; cin>>k; h[i] = k; } size_ = n; for(int i=n/2; i; i--) down(i); while(m--){ cout<


二分
二分模板
1.循环必须是l < r
2.if判断条件看是不是不满足条件， 然后修改上下界
3.若if else后是r = mid - 1，则前面mid 语句要加1
4.出循环一定是l == r，所以l和r用哪个都可以
二分只有下面两种情况
1：找大于等于给定数的第一个位置 （满足某个条件的第一个数）
2：找小于等于给定数的最后一个数 （满足某个条件的最后一个数）
PAT甲级|PAT甲级备战-高精度和排序
文章图片

PAT甲级|PAT甲级备战-高精度和排序
文章图片

// 判断条件很复杂时用check函数，否则if后直接写条件即可 bool check(int mid) { ... return ...; }// 能二分的题一定是满足某种性质，分成左右两部分 // if的判断条件是让mid落在满足你想要结果的区间内// 找满足某个条件的第一个数即右半段 int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; }// 找满足某个条件的最后一个数即左半段 int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }注释： 模板2求mid时要加一，因为除以2默认是下取整 比如红色区域二分到l = 3， r = 4，目标位置是4，那么 若不加一,则mid永远无法到4

    推荐阅读


    上一篇：亿点点难的算法|PAT甲级备战-树（一）

    下一篇：PAT甲级|PAT甲级备战-String