X01/2知识点,及常用函数(持续更新)
2023-08-19 09:13:14
发布于：浙江
7阅读
0回复
0点赞
最近更新时间:8/19
常用函数在下面
还有一些模板和模板题目
-
笔记部分
一,<cmath>
abs( ) 绝对值
floor( ) 向下取整
ceil( ) 向上取整
pow( , ) A的B次方
sqrt( ) 开方
二,格式化输出
头文件:<cstdio>
%d //相当于int
%ld //相当于long long
%md/%mld //数位对齐不足空格补位
%0md/%0mld //数位对齐不足0补
%f //相当于float
%lf //相当于double
%.nf //保留n位小数
三,字符串输入输出
1.输入
scanf,cin scanf("%s",a); //(输入"awa awa"只会读取"awa"cin同理)
gets gets(a) //(输入"awa awa"读取"awa awa"长度为7的字符串)
getline getline(cin,a) // 同上
2,输出
printf printf("%s",a);
puts puts(a)=printf("%s\n",a);
四,字符串
strlen(a); //a字符串(char)有效的长度\0以前
a.length( ); // 同上
a.size( ); //同上
string a; //定义字符串a
memcpy(a1,a,sizeof(a)); // 把字符串a的值付给a1
a.find(b); //b在a中第一次出现的位置没有就输出-1
a.rfind(b); //b在a中最后一次出现的位置没有输出-1
五,文件处理
freopen("文件名","r",stdin);
freopen("文件名","w",stdout);
fclose(stdin);
fclose(stdout);
六,sort排序
sort(起始,终止+1,排序方式);
//函数名(排序函数) 功能描述
sort //对给定区间所有元素进行排序
stable_sort //对给定区间所有元素进行稳定排序
partial_sort //对给定区间所有元素部分排序
partial_sort_copy // 对给定区间复制并排序
nth_element //找出给定区间的某个位置对应的元素
is_sorted //判断一个区间是否已经排好序
partition //使得符合某个条件的元素放在前面
stable_partition //相对稳定的使得符合某个条件的元素放在前面
用sort实现升序排列:
sort(n,n+a,cmp);
用sort实现降序排列:
bool cmp(int x,int y){
return x<y;
}
七,结构体
struct 结构体名{
成员名
}结构体变量;
八,算法/时间
log2(1024)=10; for(int i=1;i<=n;i*=2);
常用时间排名
o(1)
o(log2n)
o(n) 10^8
o(n*log2n) 10^5
o(n^2) 10^4
o(n^3) n<450
九,动态数组
vector<类型> n; 赋值n.push_back(a)
//可以定义n的范围让后直接输入 可用n.size()获取长度
set<类型> n; 赋值n.insert(a);
//访问:for(auto a:n)cout<<a<<endl; #auto更据数据改变类型
十,栈,队列
栈 stack<数据类型> a;
a.push(x); 存入数据
a.size(); 访问栈中元素数量
a.empty(); 判断栈中是否为空(空为1)
a.pop(); 弹出栈顶元素(删除并显示)(必须不为空)
a.top(); 访问栈顶元素(必须不为空)
while(!a.empty()) a.pop; 删除栈中所有元素
队列 queue<int> a;
a.push(x); 存入数据
a.size(); 访问队列中元素数量
a.empty(); 判断队列中是否为空(空为1)
a.pop(); 弹出队列顶元素(删除并显示)(必须不为空)
a.front(); 访问队列顶元素(必须不为空)
while(!a.empty()) a.pop; 删除队列中所有元素
十一,树,二叉树
原始点为根
每一个点称为节点节点的孩子数为度
度为0的节点称为叶子
1层 0 根节点
/ | \
2层 0 0 0
/ | | | \
3层 O O O O O 叶子(度为0)
数的最大层级为树的深度或高度
树的表示
1.双亲表示法
用数组记录其父亲
1
/ \
2 3
/ / \
4 5 6
/ | \
7 8 9
1 2 3 4 5 6 7 8 9 下标
0 1 1 2 3 3 4 4 4 数值
2.孩子表示法
技每个节点存储自己孩子的位置信息 选择使用动态数组vector进行存储
vector<int>tree[n];
tree[i].push_back(idx);
表示i是节点idx的双亲
二叉树
一种度数最大为2的树并且严格区分左右节点
除叶子结点以外所有节点的度都为2的二叉树称为满二叉树
除第k层以外上面的树为满二叉树并且靠左侧连续称为完全二叉树
性质一 , 二叉树每层有2^n-1个节点
性质二 , 深度为k的二叉树有2^k -1个节点
性质三 , 任意一棵二叉树,其叶子结点的数量为n0,度为2的节点数量为n2,则 n0=n2+1
性质四 , 具有n个节点的完全二叉树的深度为⌊log2(n)⌋
性质五,当前节点的左孩子编号为本身2右孩子为本身2-1其父亲节点为⌊本身/2⌋
树的存储
int three[n];
three[i]是three[i*2]和three[i*2+1]的父节点
数的遍历
先序遍历 根左右
中序遍历 左根右
后序遍历 左右根
十二,图
有向图:图的边有方向只能从一边到另一边
无向图:相反边没有方向只能从一边到另一边
节点的度:节点所连边的数目
回路:起点和终点相同的路径(也称环)
完全图:一个n阶的完全无向图有n(n-1)/2条边,有向图有n(n-1)条边**
疏密图:边数接近完全图
稀疏图:边数远远少于完全图
-
常用函数部分
下列是几个常用的函数,名字有点怪嘿嘿嘿awa
大小写转化函数
void Aa(string &x){
for(int i=0;i<x.size();i++){
if(x[i]>='A'&&x[i]<='Z')x[i]+=32;
else if(x[i]>='a'&&x[i]<='z')x[i]-=32;
}
}
//输入一个字符串完成所有英文字母大小写的转化
递归加法函数 本人觉得一点也没有用
int dg(int x){
if(x==1)return 1;
return (dg(x-1) + x);
}
//输入整数返回递归加法结果
归并排序函数
int n[114514],n1[114514];
void ddd(int l,int r){
if(l>=r)return;
int mid=(l+r)/2;
ddd(l,mid);
ddd(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(n[i]<=n[j])n1[k++]=n[i++];
else n1[k++]=n[j++];
}
while(i<=mid)n1[k++]=n[i++];
while(j<=r)n1[k++]=n[j++];
for(int i=l;i<=r;i++)n[i]=n1[i];
}
//给数组n实现归并排序
判断回文函数
int hw(int x){
int a=0,x1=x;
while(x1){
a+=x1%10;
x1/=10;
a*=10;
}
a/=10;
if(a==x)return 1;
return 0;
}
//输入一个数字判断其是(1)否(0)为回文数是 注意仅限int如果有需要可以自行更改
判断回文字符串函数
int zfhw(string a){
int c=0;
for(int i=0;i<a.size()/2;i++){
if(a[i]!=a[a.size()-1-i]){
c=1;
break;
}
}
if(c==0)return 1;
return 0;
}
//输入一个字符串判断其是(1)否(0)为回文数是
判断闰年函数
int rn(int a){
if(a%4==0&&(a%400==0||a%100!=0))return 1;
return 0;
}
//输入一个年份判断其是(1)否(1)为闰年
-
常用模板
高精度加法
#include<bits/stdc++.h>
using namespace std;
int n[114514],n1[114514],c[114514];
int main(){
string a,b;
cin>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int len=max(a.size(),b.size());
for(int i=0;i<a.size();i++){
n[i]=a[i]-'0';
}
for(int i=0;i<b.size();i++){
n1[i]=b[i]-'0';
}
int m=0;
for(int i=0;i<max(a.size(),b.size());i++){
c[i]+=n[i]+n1[i];
m++;
if(c[i]>=10){
c[i]-=10;
c[i+1]++;
}
}
m--;
if(c[len]!=0)m++;
for(int i=m;i>=0;i--){
cout<<c[i];
}
return 0;
}
高精度减法
#include<bits/stdc++.h>
using namespace std;
int n[114514],n1[114514],c[114514];
int main(){
string a,b,a1,b1;
cin>>a>>b;
a1=a;
b1=b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int len=max(a.size(),b.size());
for(int i=0;i<a.size();i++){
n[i]=a[i]-'0';
}
for(int i=0;i<b.size();i++){
n1[i]=b[i]-'0';
}
int m=0,qq=0,lkj=0;
if(b1.size()>a1.size())qq=1;
else if(b1.size()==a1.size()){
if(b1>a1)qq=1;
}
if(qq==0){
for(int i=0;i<max(a.size(),b.size());i++){
if(n[i]<n1[i]){
n[i+1]--;
n[i]+=10;
}
c[i]+=(n[i]-n1[i]);
m++;
}
}
else{
for(int i=0;i<max(a.size(),b.size());i++){
if(n1[i]<n[i]){
n1[i+1]--;
n1[i]+=10;
}
c[i]+=(n1[i]-n[i]);
m++;
lkj=1;
}
}
m--;
if(lkj==1)cout<<"-";
for(int i=m;i>=0;i--){
cout<<c[i];
}
return 0;
}
高精度乘法
#include<bits/stdc++.h>
using namespace std;
int n[114514],n1[114514],c[114514];
int main(){
string a,b;
cin>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
for(int i=0;i<a.size();i++){
n[i]=a[i]-'0';
}
for(int i=0;i<b.size();i++){
n1[i]=b[i]-'0';
}
int m=a.size()+b.size();
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
c[i+j]+=n[i]*n1[j];
c[i+j+1]+=c[i+j]/10;
c[i+j]%=10;
}
}
while(m>1&&c[m-1]==0)m--;
for(int i=m-1;i>=0;i--){
cout<<c[i];
}
return 0;
}
高精除以低精
#include<bits/stdc++.h>
using namespace std;
int main(){
string a;
long long b,n=0;
cin>>a>>b;
int len=a.size();
bool kk=0;
for(int i=0;i<len;i++){
n=n*10+(a[i]-'0');
if(kk==0&&n/b==0)continue;
kk=1;
cout<<n/b;
n%=b;
}
if(kk==0)cout<<0;
cout<<endl<<n;
return 0;
}
-
下面是模板题目
有帮助，赞一个