Silent Wittgenstein

PAT知识点-二叉查找树 二叉查找树 定义 123456struct Node//代表树的一个结点{ int data;//数据域 Node *lchild;//左孩子 Node *rchild;//右孩子}; 结点的创建 123456789Node *newNode(int data){ Node *node=new Node(); node->data=data; node->lchild=NULL; node->rchild=NULL; return node;} 查找 1234567891011121314151617181920void search(Node *root,int data){ if(root==NULL)//递归边界，到达这里表示没有找到 { printf("Not Found!\n"); return; } if(data==root->data)//找 ...

PAT常用STL-set set容器内部不包含重复元素并且自动排序。 set常用操作 12345678910111213141516171819202122232425262728293031323334#include<cstdio>#include<set>//vector类型头文件using namespace std;//使用STL容器必须添加此句 int main(){ set<int> a; a.insert(3); a.insert(3); a.insert(1); a.insert(5); a.insert(2); a.insert(2); a.insert(9); a.insert(-1); for(set<int>::iterator it=a.begin();it!=a.end();it++) printf("%d ",*it); if(a.find(8)==a.end())//没找到 printf("\n没找到！\n"); if(a.find(2)! ...

PAT常用STL-vector vector一般用作变成数组，可以方便地实现PAT中结果最后一个地方不许有空格的要求。 vector常用操作 1234567891011121314151617181920212223242526#include<cstdio>#include<vector>//vector类型头文件using namespace std;//使用STL容器必须添加此句 int main(){ vector<int> a; vector<vector<int> > b; a.push_back(2);//从后面添加元素 printf("%d\n",a[0]);//通过下标访问元素 printf("%d\n",a.size());//获取元素个数 a.pop_back();//从后面删除元素 a.insert(a.begin(),5);//在迭代器指向的位置上添加元素5 a.insert(a.begin(),2); a.insert(a.begi ...

PAT常用STL-map map作为存储**<键-值>**映射关系的容器，可以很方便地根据键提取值，或者根据值来查找键。 map的常用操作 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<cstdio>#include<map>//map类型头文件#include<vector>//vector容器 using namespace std;//使用STL容器必须添加此句 int main(){ /* 声明形式：map<value,key> mp key/value既可以是普通数据类型，也可以是STL容器 */ map<int,int> a; map<int,vector<int> > b;//>>之间加空格防止被识别为移位符 /******************************************/ ...

PAT常见错误及原因总结 答案错误 因为解题思路不对而造成的答案错误暂且不说，除了解题思路不对还有可能是以下原因： 数值溢出 这个是最不容易注意到的地方，因为int的范围大概为20亿，以下的情形需要用long long代替： 要处理的数据大小可能大于20亿。此时，要处理的数据要用long long代替。 要处理的数据大小不会超过20亿，但这个数据在进行运算的过程中可能超过20亿。这时候，存储中间运算过程结果的数值类型如果为int，也可能会造成数值溢出，存储中间过程结果的这个数值类型要替换成long long。 边界条件 这个特别需要留意！一个程序必须保证能把给定的所有输入转换成正确的输出！当然包括一些边界情况，边界情况通常能在题目中挖掘到，就是输入的极端情况，最常见的是以下两种： 最小界。一般是数值的最小值，很多题目最小界为0，要视题目而定。 最大界。一般情况是输入数据的量的最大值，比如，你用int a[10]存储输入的数据，但输入的数据量如果大于10，便会造成答案错误，此时要对存储数据的空间进行扩增。 输出信息错误 输出信息错误是指没有按照题目给定的 ...

PAT中较难的固定操作 大整数的运算 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122#include<cstdio>#include<cstring>struct Bn//bignumber{ int n[50];//最大设为50位 int len;//数字的长度 Bn() { memset(n,0,sizeof(n));//全部设为0，是一个技巧，便于接下来的运算 }};Bn toBn(char s[])//将字符串转成大数，大数是倒过来的，方便运算
...

PAT中常用基本操作 在刷了100道题后，发现有些操作真的是反反复复被用到，在此总结一下，把这些基操练习足够熟，相信对编程基本能力提升有帮助。 数组的操作 寻找最大/最小值其下标 1234567891011121314151617181920212223242526#include<cstdio>int main(){ int a[5]={4,88,-12,1999,0}; //最大值的初始要尽量小，最小值的初始要尽量大 int max=-(1<<31),maxi;//max为最大值，maxi为最大值对应的下标 int min=(1<<31)-1,mini;//min为最小值，mini为最小值对应的下标 for(int i=0;i<5;i++) { if(a[i]>max)//如果有多个最大值，>筛出第一个，>=筛出最后一个 { max=a[i]; maxi=i; } if(a[i]<min) { min=a[i ...

PAT题目中常用的库函数 ctype.h isdigit(int ch) 是数字返回非零，否则返回0 isalpha(int ch) 是字母返回非零，否则返回0 isalnum(int ch) 是数字或字母返回非零，否则返回0 islower(int ch) 是小写字母返回非零，否则返回0 isupper(int ch) 是大写字母返回非零，否则返回0 int tolower(int ch) 返回大写字母的小写形式 int toupper(int ch) 返回小写字母的大写形式 cstring int strcmp(const char*s1,const char *s2) 比较字符串s1,s2，s1=s2时返回0，s1<s2时返回负值，s1>s2时返回正值 void memset(void *s,int ch,size_t n) 用ch填充s中的n个字节，用于对数组的快速初始化，通常初始化为0或1 char *strcpy(char *dest,const char *src) 将含有结束符的字符串src复制到dest中（dest要有足够的空间），并返回指向dest ...

PAT中测试数据的输入技巧 把测试数据给正确的输入程序中，是做题的开始。有时候在输入测试数据就费了很长时间，所以在此总结一些麻烦的地方及输入技巧。 1.空格的麻烦 在此说明几个知识点 用scanf输入int、long、long long、float、double忽略空格、回车 123456789#include<cstdio>int main(){ int a; scanf("%d",&a); printf("a = %d",a); return 0;} 12输入： 2 12输出：2 用scanf输入char[]、string，遇到空格和回车便结束，要想输入带空格的字符串可以如下 1234567891011#include<iostream>#include<string>using namespace std;int main(){ string a; getline(cin,a); cout<<a; return 0;} ...

PAT降低程序运行时间的办法(C/C++) 刷了100题左右，总结了一些用于降低程序运行时间的办法 0.解题的思路是简单的 解题思路想的好，对题目是降维打击，什么也抵不上一个简单解决问题的思路。 1.使用复杂度更低的算法 对于同一个思路可能有多种算法，选择时间复杂度低的算法。这得看自己有没有学过更好的算法了。 2.空间换时间 哈希表、打表，就是空间换时间的方法 3.输入/输出使用scanf/printf，避免cin/cout 前者要快一些，很多超时的测试点，换成scanf/printf就能通过了 4.使用复合运算符+=、-=、/=、*= 5.循环中巧妙运用break 6.不要写出来死循环 写出来死循环必超时，没得说，如果前面实在没招了，看看是不是写出来死循环了吧！