【2025小白版】计算复试/保研机试模板（个人总结非GPT生成）附代码

一、编程语言选择

很多高校在机试中对编程语言都有明确规定，像复旦大学计算机学院就说明可选择 C、C++ 或 Java 语言答题，还支持 C11（gcc5.4），C++14（g++5.4），Java (openjdk1.8）等编译环境。这里强烈建议大家使用 C/C++，因为几乎所有高校都支持，通用性超强👍。

二、准备好模板是至关重要的

一般来说，机试都可以带书和纸质资料进入考场。所以提前把那些函数的用法和算法的模板准备好是很重要的，一方面是增加自己的信心，万一没记住还可以翻开来看一下。另外说不定考到原题或者类似的题，就可以直接秒杀了。
机试模板PDF详细代码自取

常见头文件

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
cout << abs(a);
memset(a,-1,sizeof(a));  #include <string.h>

int转字符串

string intToString(long long x){string s;while(x){s += (x % 10) + '0';x = x / 10;} 	reverse(s.begin(),s.end());return s;
}

日期模板

int daytab[2][13] = {
{0,31,28,31,30,31,30,31,31,30,31,30,31
},
{0,31,29,31,30,31,30,31,31,30,31,30,31,
}
};bool IsLeapYear(int x){return (x % 4 == 0&& x % 100 != 0) || (x % 400 ==0);
}
=====================================================算天数while(cin >> y >> m >> d){int sum = 0;for(int i = 0;i < m ;i ++){sum += daytab[isLeapYear(y)][i];}sum += d;cout << sum << endl;}
======================================================scanf("%04d%02d%02d",&y1,&m1,&d1);
======================================================
// 第n天后是什么日期cin >> y >> m >> d >> n;n = n + d;d = 0;while(n >= daytab[IsLeapYear(y)][m]){n -= daytab[IsLeapYear(y)][m];if(m == 12){y ++;m = 1;}else{m ++;}}d = d + n;if(d == 0 && m != 1){m --;d = daytab[IsLeapYear(y)][m];}else if(d == 0 && m == 1){m = 12;d = daytab[IsLeapYear(y)][m];}printf("%04d-%02d-%02d\n",y,m,d);}

二分查找（在已经有序的情况下）

bool BinarySearch(int n,int x){int l = 0,r = n - 1;while(l <= r){int m = (r + l) / 2;if(a[m] < x){l = m + 1;}else if(a[m] > x){r = m - 1;}else{return true;}}return false;
}

sort排序，重写CMP函数

bool cmp(Student x,Student y){if(x.score == y.score){return x.num < y.num; }else{return x.score < y.score;}
} stable_sort(&stu[0],&stu[n],cmp); //重点：sort是不稳定排序，stable_sort才是稳定排序 

快速排序

void quick_sort(int q[],int l,int r){if(l >= r)return ;int x = q[(l + r) >> 1], i = l - 1,j = r + 1;while(i < j){do i ++;while(q[i] < x);do j --;while(q[j] > x);if(i < j)swap(q[i],q[j]);} quick_sort(q,l,j);quick_sort(q,j + 1,r);
}

归并排序 + 逆序数对

void merge_sort(int q[],int l,int r){if(l >= r)return ;int mid = (l + r) >> 1;merge_sort(q,l,mid);merge_sort(q,mid + 1,r);int i = l ,j = mid + 1,k = 0;// 左右指针进行比较 while(i <= mid && j <= r){if(q[i] < q[j])temp[k ++] = q[i ++];else temp[k ++] = q[j ++];}// 没有分完的 while(i <= mid)temp[k ++] = q[i ++];while(j <= r)temp[k ++] = q[j ++];for(int i = l,j = 0;i <= r;i ++,j ++)q[i] = temp[j];
}
============================================================
逆序数
while(i <= mid && j <= r){if(q[i] > q[j]){temp[k ++] = q[j ++];sum += mid - i + 1;}else temp[k ++] = q[i ++];}
cout << sum << endl;

字符串处理

int index = str.find('a');string newstr = str.substr(startIndex,count);

向量vector map queue stack

vector<int> vectore;vectore.push_back('i');
vectore.pop_back();for(int i = 0;i < vectore.size();i ++)// map自带对键排序，进行迭代
map<int,string>::iterator it;
for(it = str.begin();it != str.end();it ++){cout << it->second << endl;
}queue<Animal> cats;
dogs.front().numberstack<int> s;
s.push(i);
s.pop();
s.top();
s.empty();

最大公约数、最小公倍数

int gcd(int a,int b){return b ? gcd(b,a % b):a;
}// 最小公倍数
min =  (a * b) / gcd;

最长子序列和问题 + 最长公共序列

for(int i=1;i<n;i++){a[i]=max(a[i],a[i-1]+a[i]);answer=max(answer,a[i]);}cout<<answer<<endl;for (int i = 1; i <= a.size(); i++) {for (int j = 1; j <= b.size(); j++) {if (a[i - 1] == b[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}
}

背包问题

const int N = 1010;
int n,m;//物品数量和背包容积
int v[N],w[N];
int f[N];int main(){cin >> n >> m;for(int i = 1;i <= n;i ++){cin >> v[i] >> w[i];}for(int i = 1;i <= n;i ++){for(int j = m;j >= v[i];j --){//2种情况f[j] = max(f[j],f[j - v[i]] + w[i]);//背包有空间}}cout << f[m] << endl;return 0;
}
// 完全
for(int i = 1;i <= n;i ++){for(int j = v[i];j <= m;j ++){f[j] = max(f[j],f[j - v[i]] + w[i]);}}

进制转化

======================================================================================数比较小
void convert(int n,int b){while(n){a[cnt ++] = n % b;n = n / b;}
}cin >> n >> b;convert(n,b);for(int i = cnt - 1;i >= 0;i --)cout << a[i];
=====================================================================================高精度:s原字符串，m是原进制，b是转换后的进制
string convert(string s, int m, int b) {string ans; while (!s.empty()) {int k = 0; // 余数bool leadingZero = true; // 用于去除前导零string temp;for (int i = 0; i < s.size(); i++) {// 如果是字母字符（用于大于10的进制），则转换为对应的值，如'A' -> 10, 'B' -> 11int digit = (isdigit(s[i]) ? s[i] - '0' : s[i] - 'A' + 10);int t = (k * m + digit) % b;int quotient = (k * m + digit) / b;k = t;if (quotient != 0 || !leadingZero) {temp += (quotient < 10 ? quotient + '0' : quotient - 10 + 'A');leadingZero = false;}}ans += (k < 10 ? k + '0' : k - 10 + 'A');s = temp;}reverse(ans.begin(), ans.end());return ans.empty() ? "0" : ans;
}
====================================================================================16进制到10进制
int CharToInt(char c){if(c >= '0' && c <= '9')    return c - '0';else return c - 'A' + 10;
}
int main() {string str;while (cin >> str) {int x = 0;for(int i = 2; i < str.length(); i ++){x = x * 16 + CharToInt(str[i]);}cout << x << endl;}return 0;
}

单词替换（字符串）

    getline(cin,s);cin >> a >> b;for(int i = 0;i < s.size();i ++){int j = i;string word;// s[j]不为空格时把他加到单词序列中，相当于split while(j < s.size() && s[j] != ' ')word += s[j ++];i = j;if(word == a)cout << b << ' ';else cout << word << ' ';}

结构体应用

// 定义一个结构体 `point`，用来存储字符的相关信息
struct point {int num; // 记录字符在字符串中出现的次数vector<int> AA; // 记录字符在字符串中出现的位置（索引）bool flag = false; // 用来判断是不是该字符第一次被输出
};int main() {string s; // 用来存储输入的字符串map<char, point> mapp; // 定义一个映射，用来存储每个字符及其对应的 `point` 结构体while (cin >> s) { // 逐行读取输入的字符串// 第一次遍历字符串，统计每个字符的出现次数for (int i = 0; i < s.size(); i++) {mapp[s[i]].num++;}// 第二次遍历字符串，记录每个字符的出现位置（如果出现次数大于1）for (int i = 0; i < s.size(); i++) {if (mapp[s[i]].num > 1) {mapp[s[i]].AA.push_back(i);}}// 第三次遍历字符串，输出每个出现次数大于1且还未被输出的字符及其出现的位置for (int i = 0; i < s.size(); i++) {if (mapp[s[i]].num > 1 && mapp[s[i]].flag == false) {for (int j = 0; j < mapp[s[i]].AA.size(); j++) {if (j == 0)printf("%c:%d", s[i], mapp[s[i]].AA[j]);elseprintf(",%c:%d", s[i], mapp[s[i]].AA[j]);}cout << endl;mapp[s[i]].flag = true; // 标记该字符已被输出}}}return 0;
}

约瑟夫环问题

int main() {int n, p, m; // n多少人，p从哪里开始，m经过多少人淘汰 while (cin >> n >> p >> m && (n || p || m)) {queue<int> children;for (int i = 1; i <= n; ++i) {children.push(i);}// 将队列旋转到第p个小孩开始for (int i = 1; i < p; ++i) {children.push(children.front());children.pop();}while (!children.empty()) {// 报数到第m个for (int i = 1; i < m; ++i) {children.push(children.front());children.pop();}// 输出当前出圈的小孩编号cout << children.front();children.pop();if (!children.empty()) {cout << ",";}}cout << endl;}return 0;
}

素数

bool isPrime(int n)
{if(n == 1 || n == 0 || n < 0)return false;  for(int i = 2; i <= sqrt(n); i++) {if(n % i ==0)return false;}return true;
}埃氏筛法
const int maxn = 10000000;
int prime[maxn];
bool IsPrime[maxn] = {0};//0代表都是素数
void Find_Prime(){IsPrime[1] = 1;//1不是素数int pNum = 1;for(int i = 2; i <= maxn; i++){if(!IsPrime[i])prime[pNum++] = i;for(int j = i * i; j <= maxn; j += i){IsPrime[j] = true;}}
}printf("%d\n", prime[k]);

质因数+约数

    int ret = 0;// 从 2 开始尝试每个可能的因数，直到 sqrt(n)for (int i = 2; i <= sqrt(n); i++) {// 如果 i 是 n 的一个因数while (n % i == 0) {ret++;  // 计数器加一n /= i;  // 用 i 除去 n 的这个因数}// 如果 n 已经被完全分解，提前退出循环if (n <= 1) break;}// 如果存在大于 sqrt(n) 的质因数，则它只能是 n 本身if (n > 1) ret++;return ret;
约数
int Counter(int x){int count = 0; int i = 1;for(i = 1;i * i < x;i ++){if(x % i == 0)count += 2;}if(i * i == x) count ++;return count;
}

快速幂

typedef long long LL;
LL a,n;LL ksm(LL a, LL n){LL ans = 1;while(n){if(n & 1)ans *= a;//如果n的最后一位是1 a *= a;n >>= 1; //二进制去掉最后一个1，*2 }return ans;
} int main(){cin >> a >> n;cout << ksm(a,n);

高精度加减乘除

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{vector<int> C;int t = 0;for (int i = 0; i < A.size() || t; i ++ ){if (i < A.size()) t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{vector<int> C;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

KMP

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;
}// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m){j = ne[j];// 匹配成功后的逻辑}
}

BFS走迷宫

#include <iostream>
#include <queue>#define x first
#define y secondusing namespace std;typedef pair<int,int> PII;const int N = 1e3 + 10;int n,m;
int g[N][N];
int d[N][N];
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};void bfs(int u){queue<int> q;q.push({1,1});memset(d,-1,sizeof(d));d[1][1] = 0;while(q.size()){PII t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.x +dx[i];int b = dy[i] + t.y;if(a < 1 || a > n || b < 1 || b > m)continue;if(g[a][b] == 1)continue;if(d[a][b] != -1)continue;d[a][b] = d[t.x][t.y] + 1;q.push({a,b});}}
}int main(){cin >> n >> m;for(int i = 0;i < n;i ++){for(int j = 0;j < n;j ++){cin >> g[i][j];}}bfs();cout << d[n][m] << endl;return 0;
}

N皇后问题DFS

#include <iostream>using namespace std;const int N = 20; // 对角线元素2n-1取20防止越界
int n;
char g[N][N]; // 存储图
bool col[N],dg[N],udg[N]; // udg副对角线 diagonal  
int cnt;void dfs(int x){if(x == n){ // 如果找到方案的话 for(int i = 0;i < n;i ++){puts(g[i]); // puts输出二维数组 输出每一行就会自动换行}puts("");cnt ++;return; // 返回调用函数进行执行 }// x : 行 y : 列for(int y = 0;y < n;y ++){// 按行枚举 因为每一行都需要放皇后 相当于剪枝 // 判断皇后是否放在这格if(!col[y] && !dg[x + y] && !udg[y - x + n]){g[x][y] = 'Q';col[y] = dg[x + y] = udg[y - x + n] = true;dfs(x + 1); // 找下一行// 回溯的时候恢复现场col[y] = dg[x + y] = udg[y - x + n] = false;g[x][y] = '.'; } } 
}
int main(){cin >> n;for(int i = 0;i < n;i ++){for(int j =0;j < n;j ++){g[i][j] = '.';}} dfs(0); // 从第一行开始找[0:下标] return 0;
}

链表类型

链表反转

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *cur = head, *pre = nullptr;while(cur != nullptr) {ListNode* tmp = cur->next; // 暂存后继节点 cur.nextcur->next = pre;           // 修改 next 引用指向pre = cur;                 // pre 暂存 curcur = tmp;                 // cur 访问下一节点}return pre;}
};

回文链表

class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> vals;while (head != nullptr) {vals.emplace_back(head->val);head = head->next;}for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {if (vals[i] != vals[j]) {return false;}}return true;}
};

环形链表

public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> seen = new HashSet<ListNode>();while (head != null) {if (!seen.add(head)) {return true;}head = head.next;}return false;}
}

排序链表

class Solution {
public:ListNode* sortList(ListNode* head) { return mergeSort(head);}/*** 对给定的链表进行归并排序*/ListNode* mergeSort(ListNode* head){// 如果链表为空或只有一个节点，无需排序直接返回if(!head || !head->next){return head;    }// 获取链表的中间节点，分别对左右子链表进行排序ListNode* mid = getMid(head);ListNode* rightSorted = mergeSort(mid->next);   // 排序右子链表if(mid)mid->next = nullptr;                     // 断开两段子链表ListNode* leftSorted = mergeSort(head);         // 排序左子链表return mergeTwoLists(leftSorted, rightSorted);  // 两个子链表必然有序，合并两个有序的链表}/*** 获取以head为头节点的链表中间节点* 如果链表长度为奇数，返回最中间的那个节点* 如果链表长度为偶数，返回中间靠左的那个节点*/ListNode* getMid(ListNode* head){if(!head)return head;   ListNode* slow = head, *fast = head->next;          // 快慢指针，慢指针初始为while(fast != nullptr && fast->next != nullptr)     {fast = fast->next->next;    // 快指针每次移动两个节点slow = slow->next;          // 慢指针每次移动一个节点}return slow;    // 快指针到达链表尾部时，慢指针即指向中间节点}/*** 合并两个有序链表list1和list2*/ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy = new ListNode();   // 伪头节点，用于定位合并链表的头节点ListNode* node = dummy;             // 新链表当前的最后一个节点，初始为伪头节点// 直到两个链表都遍历完了，合并结束while(list1 != nullptr || list2 != nullptr){int val1 = list1 == nullptr ? 50001 : list1 -> val;   // 如果链表1已经遍历完，val1取最大值，保证链表2的节点被选择到       int val2 = list2 == nullptr ? 50001 : list2 -> val;   // 如果链表2已经遍历完，val2取最大值，保证链表1的节点被选择到 if(val1 < val2){// 链表1的节点值更小，加入到合并链表，并更新链表1指向的节点node -> next = list1;list1 = list1 -> next;}else{// 链表2的节点值更小，加入到合并链表，并更新链表2指向的节点node -> next = list2;list2 = list2 -> next;}node = node -> next;    // 更新合并链表当前的最后一个节点指向}return dummy -> next;       // 伪头节点的下一个节点即为合并链表的头节点}
};

合并两个有序链表

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) {return l2;} else if (l2 == nullptr) {return l1;} else if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

是否含有子链表

struct Link {int data;struct Link *next;
};
#include <stdio.h>
void subList(Link *a,Link *b) {struct Link *la = a ,*pA = la->next, *pB = b->next;while (pA&&pB) {if (pA->data==pB->data) {//相等继续对比下一个pA = pA->next;pB = pB->next;}else {pB = b->next;//pb从头开始与pa对比la = la->next;//失败一次，la往后移动一个节点pA = la->next;//pa从下一个节点又开始}}pB == NULL ? printf("true") : printf("false");//如果pb为NULL，说明已比对完成
}
int main() {struct Link *a, *b;Link *createLink(int);a = createLink(0);b = createLink(0);subList(a,b);return 0;
}

合并链表

    /*有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2连接到h1之后，要求连接后的链表仍保持循环链表形式。*/struct Link {int data;struct Link *next;};void linkTwoLists(Link *h1,Link *h2) {struct Link *p1 = h1->next, *p2 = h2->next;while (p1->next != h1) p1 = p1->next;//这里要去判断p1->next是否等于h1，进而判断出是否到达尾结点p1->next = p2;while (p2->next != h2) p2 = p2->next;p2->next = h1;free(h2);//释放h2}int main() {struct Link *h1, *h2,*p;Link *createSinLoopLink();h1 = createSinLoopLink();h2 = createSinLoopLink();linkTwoLists(h1,h2);p = h1->next;while (p!=h1) {printf("%d ",p->data);p = p->next;}return 0;}

输出链表倒数第K个结点

ListNode *findKthTail(ListNode *pHead, int K) {ListNode *p1(pHead), *p2(pHead);for(int i=0; i<K; ++i){p1 = p1-> next;if(!p1){return nullptr;}}while(p1){p1 = p1-> next;p2 = p2-> next;}return p2;
}

两数相加

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* first = new ListNode(0);  // 哑结点ListNode* last = first;int carry = 0;while(l1 or l2 or carry){// 相加int bitsum = 0;if(l1){bitsum += l1->val;l1 = l1->next;}if(l2){bitsum += l2->val;l2 = l2->next;}if(carry){bitsum += carry;}// 结果int digit = bitsum % 10;carry = bitsum / 10;// 链表存储ListNode* node = new ListNode(digit);last->next = node;last = node;}last = first->next;delete first;return last;}
};

计算循环链表中环的长度

int getLoopLength(ListNode *pHead) {ListNode *fast(pHead), *slow(pHead);while (fast && fast->next) {fast = fast->next->next;slow = slow->next;if (fast == slow) {break;}}if (!fast || !fast->next) return -1;int length = 1;  // 从1开始while (slow->next != fast) {slow = slow->next;length++;}return length;
}

先序遍历

void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}res.push_back(root->val);preorder(root->left, res);preorder(root->right, res);}vector<int> preorderTraversal(TreeNode *root) {vector<int> res;preorder(root, res);return res;}

层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;

完全二叉树的节点个数

int countNodes(TreeNode* root) {if(!root)return 0;return countNodes(root -> left) + countNodes(root -> right) + 1;}

每个人戴不同帽子的方案数

using LL = long long;class Solution {
private:static constexpr int mod = 1000000007;public:int numberWays(vector<vector<int>>& hats) {int n = hats.size();// 找到帽子编号的最大值，这样我们只需要求出 $f[maxhatid][2^n - 1]$ 作为答案int maxHatId = 0;for (int i = 0; i < n; ++i) {for (int h: hats[i]) {maxHatId = max(maxHatId, h);}}// 对于每一顶帽子 h，hatToPerson[h] 中存储了喜欢这顶帽子的所有人，方便进行动态规划vector<vector<int>> hatToPerson(maxHatId + 1);for (int i = 0; i < n; ++i) {for (int h: hats[i]) {hatToPerson[h].push_back(i);}}vector<vector<int>> f(maxHatId + 1, vector<int>(1 << n));// 边界条件f[0][0] = 1;for (int i = 1; i <= maxHatId; ++i) {for (int mask = 0; mask < (1 << n); ++mask) {f[i][mask] = f[i - 1][mask];for (int j: hatToPerson[i]) {if (mask & (1 << j)) {f[i][mask] += f[i - 1][mask ^ (1 << j)];f[i][mask] %= mod;}}}}return f[maxHatId][(1 << n) - 1];}
};

同构字符串

bool isIsomorphic(string s, string t) {if(s.size() != t.size())return false;unordered_map<char,char> s1;unordered_map<char,char> s2;for(int i = 0;i < s.size();i ++){char x = s[i],y = t[i];if((s1.count(x) && s1[x] != y) || (s2.count(y) && s2[y] != x))return false;s1[x] = y;s2[y] = x;}return true;}

因篇幅受限，如需查看完整版内容，请点击“上述的link”.