初赛总结
1.进制转换
十 转其他 进制
整数 部分
短除法
每次除进制 取整数 ,除到0为止,再把余数从下往上 组起即可
小数 部分
连乘法
每次乘进制 取小数 ,除到0为止,再把整数从上往下 组起即可
其他 转十 进制
每一位的数乘进制的位权次方 ,每位加起即可
其他 转其他 进制
把十进制 当跳板
先转十进制 ,再转为其他进制
优点 屡试不爽
缺点 累
按倍率 直接转
后者进制 是前者进制 的几倍 ,结果这位 就取几位 的和
如 二进制 101001 为八进制 101 为5 ;001 为1 :51
优点 快
缺点 限制大
注意
不忘组起顺序
2.位运算技巧
先转二进制
正数
正常进制转换
负数
先正常进制转换转原码,再转反码,最后加一转补码
再按照不同运算符 进行运算
<<左移,>>右移,&与,^异或 ,|或等
最后转回十进制
正数
正常进制转换
负数
先减一转补码 ,再转反码 ,最后正常进制转换转十进制
注意
不忘转反码补码
3.数据结构
图
基本概念
顶点/节点 简称点。
边 节点之间的连线。
完全图 任意两点都有边相连
简单路径 两点之间通过不重复的边相连。
连通图 任意两点都可以直接/间接到达
注意 别于完全图,完全图属于连通图,连通图不一定属于完全图
有向图 边是有方向的
无向图 边是无方向的
环 一个顶点能绕回到自己为环
注意 如果环只有一个点,则被称为“自环”
入度 以一个顶点为终点的边的条数为该节点的入度
出度 以一个顶点为起点的边的条数为该节点的出度
树
基本概念
树 一个相当于倒过来的树,上面为根,下面为叶子
父节点 一个节点的上面那个节点
子节点 一个节点的下面那个节点
根节点 树的起始节点 没有父节点
叶子结点 树的末尾节点,没有子节点
祖先 为父亲或父亲的父亲等
树的宽度 树的每层节点总数的最大值
树的深度 到根节点的路径边数
树的高度 指树的层数(有时根节点为1,有时为0)
二叉树 子节点最多只有2个
等等等…
高精度
高精加减
加法
cin>>s1>>s2;
int l1=s1.size(),l2=s2.size();
int mx=max(l1,l2);
for(int i=0;i<l1;i++)a[i]=s1[l1-i-1]-'0';
for(int i=0;i<l2;i++)b[i]=s2[l2-i-1]-'0';
for(int i=0;i<mx;i++){
n=a[i]+b[i]+l;
if(n>=10)l=1,n-=10;
else l=0;
s[i]=n;
}
for(int i=mx;i>=0;i--){
if(o==1&&s[i]==0){
o=0;
continue;
}
cout<<s[i];
}
减法
cin>>s1>>s2;
int l1=s1.size(),l2=s2.size();
int mx=max(l1,l2);
for(int i=0;i<l1;i++)a[i]=s1[l1-i-1]-'0';
for(int i=0;i<l2;i++)b[i]=s2[l2-i-1]-'0';
if(l1<l2){
swap(a,b);
cout<<"-";
}
for(int i=0;i<mx;i++){
n=a[i]-b[i]-l;
if(n<0)l=1,n+=10;
else l=0;
s[i]=n;
}
for(int i=mx;i>=0;i--){
if(o==1&&s[i]==0){
o=0;
continue;
}
cout<<s[i];
}
高精乘除
乘法
cin>>a>>b;
if(a=="0"||b=="0"){
cout<<0;
return 0;
}
int l1=a.size(),l2=b.size(),l3=l1+l2;
for(int i=0;i<l1;i++)t[i]=a[l1-i-1]-'0';
for(int i=0;i<l2;i++)o[i]=b[l2-i-1]-'0';
for(int i=0;i<l1;i++)for(int j=0;j<l2;j++)s[j+i]+=t[i]*o[j];
for(int i=0;i<l3;i++)s[i+1]+=s[i]/10,s[i]%=10;
while(s[l3]==0)l3--;
for(int i=l3;i>=0;i--)cout<<s[i];
除法
cin>>n>>a>>b;
if(a=="0"){
cout<<0;
return 0;
}
for(int i=0;i<n;i++)t[i]=a[i]-'0';
for(int i=0;i<n;i++)s[i]=t[i]/b,t[i+1]+=(t[i]%b)*10;
while(s[o]==0)o++;
for(int i=o;i<n;i++)cout<<s[i];