计算机专业保研本校机考,GitHub - Lambert-hpx/cs-baoyan-kaoyan-jikao-zhengli: 计算机保研考研上机考试复习整理，制作不易，还请给个star噢~...

微生翼

2023-12-01

复习目录

常用函数：STL等常用数据结构(树、栈、队列、优先队列、向量、散列表、集合、字符串)和函数

数学问题(最小公倍数、最大公因数、快速幂、进制转换、质因数、大数)

搜索(BFS & DFS)

图论(并查集、最小生成树、最短路径、拓扑排序、关键路径)

动态规划

常用函数

memset-对数组中每个元素赋值0/-1

#include

int a[5];

memset(a,0,sizeof(a));

getchar/putchar && gets/puts

#include

getchar(); //输入单个字符有时候还可以用来吸收换行符

putchar(); //输出单个字符

gets(); //输入一行字符串，识别\n作为输入结束

puts(); //输出一行字符串，并输出\n 若是字符串末尾没有\0则会乱码

string.h

#include

strlen(str);

strcmp(str1,str2);

//比较字典序，小于返回负整数，等于返回0，大于返回正整数

strcpy(str1,str2); //把str2复制给str1

strcat(str1,str2); //把str2接到str1后面

math.h

#include

fabs(-12.56); //12.56

floor(-5.2); //-6 向下(小)取整

ceil(-5.2); //5 向上(大)取整

double db = pow(2.0,3.0); //8.000000

sqrt(2.0); //1.414214

log(1.0); //0.000000 以自然对数为底的对数

//log(a)b=logb/loga 必须用换底公式

const double pi = acos(-1.0);

sin(pi*45/180);

cos(pi*45/180);

tan(pi*45/180); //弧度制！！

asin(1);

acos(-1.0);

atan(0);

round(3.5); //4 四舍五入

printf

#include

%5d; //宽为5的整数，超过5位按实际输出，不够5位右对齐输出

%05d; //宽为5的整数，超过5位按实际输出，不够5位前置补0右对齐

%5.2f; //宽为5的浮点数，小数点有2位，小数点占一位, 不够5位右对齐输出

%6.9s; //表示显示一个长度不小于6且不大于9的字符串。若大于9, 则第9个字符以后的内容将被删除。

%ld; //表示输出long整数

%lf; //表示输出double浮点数

%-7d; //表示输出7位整数左对齐空位补齐

%-10s; //表示输出10个字符左对齐

/*按整型输出，默认右对齐*/

printf("%d\n",PrintVal);

/*按整型输出，补齐4位的宽度，补齐位为空格，默认右对齐*/

printf("%4d\n",PrintVal);

/*按整形输出，补齐4位的宽度，补齐位为0，默认右对齐*/

printf("%04d\n",PrintVal);

/*按16进制输出，默认右对齐*/

printf("%x\n",PrintVal);

/*按16进制输出，补齐4位的宽度，补齐位为空格，默认右对齐*/

printf("%4x\n",PrintVal);

/*按照16进制输出，补齐4位的宽度，补齐位为0，默认右对齐*/

printf("%04x\n",PrintVal);

/*按8进制输出，默认右对齐*/

printf("%o\n",PrintVal);

/*按8进制输出，补齐4位的宽度，补齐位为空格，默认右对齐*/

printf("%4o\n",PrintVal);

/*按照8进制输出，补齐4位的宽度，补齐位为0，默认右对齐*/

printf("%04o\n",PrintVal);

常用模板代码

日期转换

闰年判断

bool IsLeapYear(int year){

return (year%4==0 && year%100!=0) || (year%400==0);

}

反序数

int Reverse(int x){

int revx=0;

while(x != 0){

revx*=10;

revx+=x%10;

x/=10;

}

return revx;

}

最大公约数 & 最小公倍数

//最大公约数求法

int GCD(int a,int b){ //辗转相除法 a大b小

if(b==0){

return a;

}else{

return GCD(b,a%b);

}

//最小公倍数求法

a * b / GCD(a,b);

质数和分解质因数

1. 质数判定：若到sqrt(n)的整数，所有正整数均不能整除n，则可以判断n为素数(小于2必定不是素数)

2. 某范围内的素数筛法

const int MAXN = 10001;

vector prime; //保存质数

bool isPrime[MAXN]; //标记数组

void Initial(){

//初始化

for(int i=0;i

isPrime[i] = true;

}

isPrime[0]=false;

isPrime[1]=false;

//素数筛法

for(int i = 2;i

if(!isPrime[i]){ //非质数跳过

continue;

}

prime.push_back(i);

for(int j=i*i;j

isPrime[j]=false; //质数的倍数必为非质数

}

3. 分解质因数：先用素数筛法,然后不断试除

快速幂

求指数的二进制数

求底数幂然后累乘

矩阵快速幂，初始化为单位矩阵

int FastExp(int a,int b,int mod){

int answer = 1; //初始化为1

while(b!=0){ //不断将b转换为二进制数

if (b%2==1){ //若位为1，累乘a的2^k次幂

answer *= a;

//answer %= mod; //求后三位，依题目而定

}

b/=2; //b不断转换

a*=a; //a不断平方

//a%=mod; //求后三位，依题目而定

}

return a

同余模定理

(a*b)%c=((a%c)*(b%c))%c;

(a+b)%c=((a%c)+(b%c))%c;

BFS

#include

#define SIZE 1000

using namespace std;

queue q_x, q_y, q_pos;

int step[4][2] = {

{1,0},{0,1},{-1,0},{0,-1}

};

int m, n, board[SIZE][SIZE], start_x, start_y, target_x, target_y;

bool vis[SIZE][SIZE];

void bfs() {

bool flag = false; //判断是否成功的标志

while (!q_x.empty() && !q_y.empty()) { //判断队是否为空

for (int k = 0; k < 4; ++k) { //先遍历

int tx = q_x.front() + step[k][0]; //状态转移

int ty = q_y.front() + step[k][1];

if (tx < 1 || ty < 1 || tx > n || ty > m) //判断边界

continue;

if (!board[tx][ty] && !vis[tx][ty]) {

vis[tx][ty] = true; //标记

q_x.push(tx); //入队

q_y.push(ty);

q_pos.push(q_pos.front() + 1);

}

if (tx == target_x&&ty == target_y) { //判断到达目标的条件

flag = true;

break;

}

if (flag)

break;

q_x.pop(); //队首出队

q_y.pop();

q_pos.pop();

}

return;

}

int main()

{

while (cin >> m >> n) {

for (int i = 1; i <= m; ++i) {

for (int j = 1; j <= n; ++j) {

cin >> board[i][j];

}

cin >> start_x >> start_y >> target_x >> target_y;

q_x.push(start_x);

q_y.push(start_y); //初始入队

q_pos.push(0);

vis[start_x][start_y] = true;

bfs();

cout << q_pos.back() << endl;

}

return 0;

}

DFS

int check(参数)

{

if(满足条件)

return 1;

return 0;

}

void dfs(int step)

{

判断边界

{

相应操作

}

尝试每一种可能

{

满足check条件

标记

继续下一步dfs(step+1)

恢复初始状态(回溯的时候要用到)

}

并查集

用于判断图是否为连通图

求图的连通分量

#include

using namespace std;

const int MAXN = 1000;

int father[MAXN]; //父亲结点

int height[MAXN]; //结点高度

void Initial(int n){ //初始化

for(int i=0;i<=n;i++){

father[i]=i; //每个结点的父亲为自己

height[i]=0; //每个结点初始高度为0

}

int Find(int x){ //查找根节点

if(x!=father[x]){ //路径压缩

father[x]=Find(father[x]);

}

return father[x];

}

void Union(int x,int y){ //合并集合

x=Find(x);

y=Find(y);

if(x!=y){ //矮树作为高数的子树

if(height[x]

father[x]=y;

}else if (height[y]

father[y]=x;

}else{

father[y]=x;

height[x]++;

}

return ;

}

//先Initial 再一个一个输入 Union

//Find(i)==i; 说明有一个集合，即连通分量

最小生成树

连通所有结点的树中权值最小的即为最小生成树，实现同样用了并查集的思想：

Initial 后按边的权值排序

判断边的两个顶点是否同属一个集合 (用Find)

不同集合则合并(Union)，加上这条关键边的长度

#include

struct Edge{

int from; //边的起点

int to; //边的终点

int length; //边的长度

friend bool operator < (const Edge& e1,const Edge& e2) const {

return e1.length < e2.length;

}

};

Edge edge[MAXN*MAXN]; //边集

/*上边并查集的所有内容*/

void Kruskal(int n,int edgeNum){ //克鲁斯卡尔算法，n为点数，edgeNum为边数

Initial(n);

sort(edge,edge+edgeNum); //按权值排序，重载运算符，无需重写cmp

int sum=0; //初始化最小生成树长度

for(int i=0;i

Edge current = edge[i];

if (Find(current.from)!=Find(current.to)){ //边的两端结点不同属一个连通子集吗？

Union(current.from,current.to); //不同属的话就合并连通

sum+=current.length; //属于最小生成树的一部分了

}

return sum;

}

大数

定义类

#include

using namespace std;

#define MAXN 9999

#define MAXSIZE 10

#define DLEN 4

class BigNum

{

private:

int a[1500]; //可以控制大数的位数

int len; //大数长度

public:

BigNum(){ len = 1;memset(a,0,sizeof(a)); } //构造函数

BigNum(const int); //将一个int类型的变量转化为大数

BigNum(const char*); //将一个字符串类型的变量转化为大数

BigNum(const BigNum &); //拷贝构造函数

BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算

friend istream& operator>>(istream&, BigNum&); //重载输入运算符

friend ostream& operator<

BigNum operator+(const BigNum &) const; //重载加法运算符，两个大数之间的相加运算

BigNum operator-(const BigNum &) const; //重载减法运算符，两个大数之间的相减运算

BigNum operator*(const BigNum &) const; //重载乘法运算符，两个大数之间的相乘运算

BigNum operator/(const int &) const; //重载除法运算符，大数对一个整数进行相除运算

BigNum operator^(const int &) const; //大数的n次方运算

int operator%(const int &) const; //大数对一个int类型的变量进行取模运算

bool operator>(const BigNum & T)const; //大数和另一个大数的大小比较

bool operator>(const int & t)const; //大数和一个int类型的变量的大小比较

void print(); //输出大数

};

将一个int类型的变量转化为大数

BigNum::BigNum(const int b)

{

int c,d = b;

len = 0;

memset(a,0,sizeof(a));

while(d > MAXN)

{

c = d - (d / (MAXN + 1)) * (MAXN + 1);

d = d / (MAXN + 1);

a[len++] = c;

}

a[len++] = d;

}

将一个字符串类型的变量转化为大数

BigNum::BigNum(const char*s)

{

int t,k,index,l,i;

memset(a,0,sizeof(a));

l=strlen(s);

len=l/DLEN;

if(l%DLEN)

len++;

index=0;

for(i=l-1;i>=0;i-=DLEN)

{

t=0;

k=i-DLEN+1;

if(k<0)

k=0;

for(int j=k;j<=i;j++)

t=t*10+s[j]-'0';

a[index++]=t;

}

拷贝构造函数

BigNum::BigNum(const BigNum & T) : len(T.len)

{

int i;

memset(a,0,sizeof(a));

for(i = 0 ; i < len ; i++)

a[i] = T.a[i];

}

重载赋值运算符，大数之间进行赋值运算

BigNum & BigNum::operator=(const BigNum & n)

{

int i;

len = n.len;

memset(a,0,sizeof(a));

for(i = 0 ; i < len ; i++)

a[i] = n.a[i];

return *this;

}

重载输入运算符

istream& operator>>(istream & in, BigNum & b)

{

char ch[MAXSIZE*4];

int i = -1;

in>>ch;

int l=strlen(ch);

int count=0,sum=0;

for(i=l-1;i>=0;)

{

sum = 0;

int t=1;

for(int j=0;j<4&&i>=0;j++,i--,t*=10)

{

sum+=(ch[i]-'0')*t;

}

b.a[count]=sum;

count++;

}

b.len =count++;

return in;

}

重载输出运算符

ostream& operator<

{

int i;

cout << b.a[b.len - 1];

for(i = b.len - 2 ; i >= 0 ; i--)

{

cout.width(DLEN);

cout.fill('0');

cout << b.a[i];

}

return out;

}

两个大数之间的相加运算

BigNum BigNum::operator+(const BigNum & T) const

{

BigNum t(*this);

int i,big; //位数

big = T.len > len ? T.len : len;

for(i = 0 ; i < big ; i++)

{

t.a[i] +=T.a[i];

if(t.a[i] > MAXN)

{

t.a[i + 1]++;

t.a[i] -=MAXN+1;

}

if(t.a[big] != 0)

t.len = big + 1;

else

t.len = big;

return t;

}

两个大数之间的相减运算

BigNum BigNum::operator-(const BigNum & T) const

{

int i,j,big;

bool flag;

BigNum t1,t2;

if(*this>T)

{

t1=*this;

t2=T;

flag=0;

}

else

{

t1=T;

t2=*this;

flag=1;

}

big=t1.len;

for(i = 0 ; i < big ; i++)

{

if(t1.a[i] < t2.a[i])

{

j = i + 1;

while(t1.a[j] == 0)

j++;

t1.a[j--]--;

while(j > i)

t1.a[j--] += MAXN;

t1.a[i] += MAXN + 1 - t2.a[i];

}

else

t1.a[i] -= t2.a[i];

}

t1.len = big;

while(t1.a[len - 1] == 0 && t1.len > 1)

{

t1.len--;

big--;

}

if(flag)

t1.a[big-1]=0-t1.a[big-1];

return t1;

}

两个大数之间的相乘运算

BigNum BigNum::operator*(const BigNum & T) const

{

BigNum ret;

int i,j,up;

int temp,temp1;

for(i = 0 ; i < len ; i++)

{

up = 0;

for(j = 0 ; j < T.len ; j++)

{

temp = a[i] * T.a[j] + ret.a[i + j] + up;

if(temp > MAXN)

{

temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);

up = temp / (MAXN + 1);

ret.a[i + j] = temp1;

}

else

{

up = 0;

ret.a[i + j] = temp;

}

if(up != 0)

ret.a[i + j] = up;

}

ret.len = i + j;

while(ret.a[ret.len - 1] == 0 && ret.len > 1)

ret.len--;

return ret;

}

大数对一个整数进行相除运算

BigNum BigNum::operator/(const int & b) const

{

BigNum ret;

int i,down = 0;

for(i = len - 1 ; i >= 0 ; i--)

{

ret.a[i] = (a[i] + down * (MAXN + 1)) / b;

down = a[i] + down * (MAXN + 1) - ret.a[i] * b;

}

ret.len = len;

while(ret.a[ret.len - 1] == 0 && ret.len > 1)

ret.len--;

return ret;

}

大数对一个int类型的变量进行取模运算

int BigNum::operator %(const int & b) const

{

int i,d=0;

for (i = len-1; i>=0; i--)

{

d = ((d * (MAXN+1))% b + a[i])% b;

}

return d;

}

大数的n次方运算

BigNum BigNum::operator^(const int & n) const

{

BigNum t,ret(1);

int i;

if(n<0)

exit(-1);

if(n==0)

return 1;

if(n==1)

return *this;

int m=n;

while(m>1)

{

t=*this;

for( i=1;i<<1<=m;i<<=1)

{

t=t*t;

}

m-=i;

ret=ret*t;

if(m==1)

ret=ret*(*this);

}

return ret;

}

大数和另一个大数的大小比较

bool BigNum::operator>(const BigNum & T) const

{

int ln;

if(len > T.len)

return true;

else if(len == T.len)

{

ln = len - 1;

while(a[ln] == T.a[ln] && ln >= 0)

ln--;

if(ln >= 0 && a[ln] > T.a[ln])

return true;

else

return false;

}

else

return false;

}

大数和一个int类型的变量的大小比较

bool BigNum::operator >(const int & t) const

{

BigNum b(t);

return *this>b;

}

输出大数

void BigNum::print()

{

int i;

cout << a[len - 1];

for(i = len - 2 ; i >= 0 ; i--)

{

cout.width(DLEN);

cout.fill('0');

cout << a[i];

}

cout << endl;

}

使用

BigNum a,b,c;

char s1[1000];

char s2[1000];

int main(){

scanf("%s",s1);

scanf("%s",s2);

a = s1;

b = s2;

c = a + b;

cout<

a = s1;

b = s2;

c = a - b;

cout<

计算机专业保研本校机考,GitHub - Lambert-hpx/cs-baoyan-kaoyan-jikao-zhengli: 计算机保研考研上机考试复习整理，制作不易，还请给个star噢~...

相关阅读

相关文章

相关问答

相关文档