龙江手机网站建设,网站建设及推广培训,广东企业网站建设多少钱,天津软件优化公司排名前十专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客#xff0c;如有问题交流#xff0c;欢迎评论区留言#xff0c;一定尽快回复#xff01;#xff08;大家可以去看我的专栏#xff0c;是所有文章的目录#xff09; 文章字体风格#xff1a; 红色文字表示#…专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客如有问题交流欢迎评论区留言一定尽快回复大家可以去看我的专栏是所有文章的目录 文章字体风格 红色文字表示重难点★✔ 蓝色文字表示思路以及想法★✔ 如果大家觉得有帮助的话感谢大家帮忙 点赞收藏转发 本博客带大家一起学习我们不图快只求稳扎稳打。 由于我高三是在家自学的经验教训告诉我学习一定要长期积累并且复习所以我推出此系列。 只求每天坚持40分钟一周学5天复习2天 也就是一周学10道题 60天后我们就可以学完81道题相信60天后我们一定可以有扎实的代码基础我们每天就40分钟和我一起坚持下去吧 qq群878080619 【考研408-数据结构笔试】 一、排序1. 成绩排序清华大学考研机试题考点结构体排序在结构体中定义排序使用比较器定义排序 注意问题需要处理 值相等时 先后顺序 2. 成绩排序2( 清华大学考研机试题 ) 二、进位制1. 进制转换清华大学考研机试题本题考点1. 大数除法2. 十进制转二进制 步骤 2. 进制转换2清华大学考研机试题考点M进制转N进制和10进制转2进制 不一样的就是短除时的 进位一个是10而另一个是a仅此而已 三、链表1. 两个链表的第一个公共结点2. 筛选链表( 2015年全国硕士研究生招生考试 )考点删除节点需要两个指针一个前一个后删除所以比较的时候比较p-next-val比较好 3. 重排链表( 2019年全国硕士研究生招生考试 )考点1. 链表反转2. 链表合并 四、日期问题1. 日期累加 北京理工大学考研机试题 2. 打印日期 华中科技大学考研机试题 五、表达式求值1. 表达式求值 六、树的遍历 递归 1. 二叉树的带权路径长度2. 重建二叉树构建二叉树的两种情况 七、二叉搜索树与表达式树1. 二叉排序树中序遍历是有序的2. 表达式树 八、Huffman树1. 合并果子2. 荷马史诗考点 构建深度最小的哈夫曼树 利用pair考点 k进制哈夫曼树需要补零节点 八、拓扑排序1. 有向图的拓扑序列 九、最小生成树、最短路1. Prim算法求最小生成树和dijk算法差不多2. Dijkstra求最短路 I3. Floyd求最短路4. spfa求最短路 十、哈希表1. 模拟散列表开散列方法拉链法开放寻址法代码本质最多存1e5个数 2. 未出现过的最小正整数( 2018年全国硕士研究生招生考试 ) 十一、KMP十二、排序1. 快速排序2. 整数集合划分 十三、多路归并1. 三元组的最小距离2020年全国硕士研究生招生考试 十四、摩尔投票法1. 数组中出现次数超过一半的数字 十五、DFS1. 全排列( 北京大学考研机试题 )2. 八皇后 北京大学考研机试题 十六、模拟1. 反序输出 清华大学考研机试题 考点reverse(s.begin(), s.end()); 2. 特殊乘法 清华大学考研机试题 3. 众数 清华大学考研机试题 4. 糖果分享游戏 十七、递推1. 递推数列 清华大学考研机试题 2. 吃糖果 北京大学考研机试题 十八、BFS1. 玛雅人的密码2. 等差数列 十九、字符串处理1. 首字母大写2. 日志排序3. 字符串转换整数 二十、递归画图1. 重复者 二十一、背包问题1. 01背包2. 神奇的口袋( 体积恰好是 )3. 整数拆分 二十二、高精度1. N的阶乘做法预处理 2. 基本算术3. 整数查询 二十三、因式分解1. 质因数的个数2. 约数个数3. 阶乘的末尾0上海交通大学考研机试题4. 整除问题上海交通大学考研机试题 二十四、枚举1. 与7无关的数 北京大学考研机试题2. 打印极值点下标( 北京大学考研机试题 )3. 最简真分数( 北京大学考研机试题 ) 【真分数】4. 买房子 北京大学考研机试题 【算立方和平方】5. Special数北京邮电大学考研机试题 二十六、位运算1. 位操作练习北京大学考研机试题2. 二进制数北京邮电大学考研机试题 二十七、矩阵1. 旋转矩阵北京航空航天大学考研机试题2. 矩阵幂【矩阵相乘】北京邮电大学考研机试题两个矩阵相乘结果 3. C翻转北京邮电大学考研机试题 二十八、计算几何1. 球的计算2. 点的距离重新定义类的相减 3. 直角三角形 二十九、前缀和1. 最长平衡串北京邮电大学考研机试题 三十、推公式1. 数字台阶2. 整数和3. 弹地小球 三十一、最短路1. 我想回家北京大学考研机试题2. 最短路径3. 最短路径 三十二、思维题1. 棋盘遍历问题上海交通大学考研机试题 三十三、哈希表1. 子串计算北京大学考研机试题map自动排序 2. 查找北京邮电大学考研机试题unordered_set通过countx0判断是否存在 3. 单词识别北京理工大学考研机试题 三十四、双指针1. 最小面积子矩阵算法1二维前缀和算法2一维前缀和 双指针 三十五、序列型DP1. 最大序列和清华大学考研机试题2. 最长ZigZag子序列 三十六、红黑树和并查集1. 合并集合 一、排序
1. 成绩排序清华大学考研机试题 考点结构体排序
在结构体中定义排序
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1010;int n, m;
struct Person
{string name;int score;int id;bool operator (const Person t) const{if (score ! t.score) return score t.score;return id t.id;}bool operator (const Person t) const{if (score ! t.score) return score t.score;return id t.id;}
}q[N];int main()
{cin n m;for (int i 0; i n; i ){cin q[i].name q[i].score;q[i].id i;}if (!m) sort(q, q n, greaterPerson());else sort(q, q n);for (int i 0; i n; i )cout q[i].name q[i].score endl;return 0;
}使用比较器定义排序
#includebits/stdc.h
using namespace std;
struct node{int x,id;string name;
}a[1001];
bool cmp1(node a,node b){
//从小到大if(a.xb.x)return a.idb.id;return a.xb.x;
}
bool cmp2(node a,node b){
//从大到小if(a.xb.x)return a.idb.id;return a.xb.x;
}
int main()
{int n;bool ok;cinnok;for(int i1;in;i){cina[i].namea[i].x;a[i].idi;}if(ok)sort(a1,a1n,cmp1);if(!ok)sort(a1,a1n,cmp2);for(int i1;in;i)couta[i].name a[i].x\n;
}注意问题需要处理 值相等时 先后顺序
在结构体中定义一个id记录出现的顺序
// package Test;import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;/*** Author zh* Date 2023/8/8 19:10* PackageName:Test* ClassName: Main* Description: TODO* Version 1.0*/class Student{int grade;String name;public Student(int grade,String name){this.grade grade;this.name name;}
}class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt();int a scanner.nextInt();Student[] students new Student[N];for(int i 0; i N; i){String name scanner.next();int grade scanner.nextInt();students[i] new Student(grade,name);}if(a 1){Arrays.sort(students,(o1, o2) - {return o1.grade-o2.grade;});}else{Arrays.sort(students,(o1, o2) - {return o2.grade-o1.grade;});}for(Student x : students){System.out.println(x.name x.grade);}}
}
2. 成绩排序2( 清华大学考研机试题 ) #include iostream
#include cstring
#include algorithmusing namespace std;const int N 110;int n;
struct Person
{int id;int score;bool operator (const Person t) const{if (score ! t.score) return score t.score;return id t.id;}
}q[N];int main()
{cin n;for (int i 0; i n; i ) cin q[i].id q[i].score;sort(q, q n);for (int i 0; i n; i ) cout q[i].id q[i].score endl;return 0;
}import java.util.Arrays;
import java.util.Scanner;class Student{int id;int grade;public Student(int id,int grade){this.id id;this.grade grade;}
}class Main{public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();Student[] students new Student[n];for(int i 0; i n; i){int id scanner.nextInt();int grade scanner.nextInt();students[i] new Student(id,grade);}Arrays.sort(students,(o1, o2) - {if(o1.grade o2.grade){return o1.id-o2.id;}return o1.grade-o2.grade;});for (Student x : students){System.out.println(x.id x.grade);}}
}二、进位制
1. 进制转换清华大学考研机试题 本题考点
1. 大数除法
可以csdn搜索一下
关键就是vector的使用 和 除法步骤记得就好
就好比用 代码模拟出 草稿纸上的除法运算
2. 十进制转二进制 步骤 代码看不懂可以只需明白逻辑然后自己写即可
一定自己写出来才明白
#includeiostream
#includecstring
#includealgorithm
#includevectorusing namespace std;void div(vectorint tmp,vectorint ans)
{vectorint tmp2;int t 0;for(int i 0; i tmp.size(); i){t t*10 tmp[i];tmp2.push_back(t/2);t t%2;}ans.push_back(t);reverse(tmp2.begin(),tmp2.end());while(tmp2.size()!1 tmp2.back()0){tmp2.pop_back();}reverse(tmp2.begin(),tmp2.end());tmp tmp2;
}int main()
{string s;while(cin s){vectorint tmp;for(int i 0; i s.size(); i){tmp.push_back(s[i]-0);}vectorint ans; //什么时候停止if(s0){cout 0 endl;}else{while(tmp.size()1 || (tmp.size() 1 tmp.back() ! 0)){div(tmp,ans);}reverse(ans.begin(),ans.end());for(int i 0; i ans.size(); i){cout ans[i];}cout endl;}}return 0;
}2. 进制转换2清华大学考研机试题 考点M进制转N进制
和10进制转2进制 不一样的就是短除时的 进位一个是10而另一个是a仅此而已
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;int main()
{int a, b;string s;cin a b s;vectorint A;for (int i 0; i s.size(); i ){char c s[s.size() - 1 - i];if (c A) A.push_back(c - A 10);else A.push_back(c - 0);}string res;if (s 0) res 0;else{while (A.size()){int r 0;for (int i A.size() - 1; i 0; i -- ){A[i] r * a;r A[i] % b;A[i] / b;}while (A.size() A.back() 0) A.pop_back();if (r 10) res to_string(r);else res r - 10 a;}reverse(res.begin(), res.end());}cout res endl;return 0;
}三、链表
1. 两个链表的第一个公共结点 //cpp
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1 headA;ListNode *p2 headB;while (p1 ! p2) {if(p1 ! NULL)//p1没有走到结尾p1 p1-next;//p1指向下一个节点else//p1走到结尾p1 headB;//p1指向另一个链表头if(p2 ! NULL)//p2没有走到结尾p2 p2-next;//p2指向下一个节点else //p2走到结尾 p2 headA;//p2指向另一个链表头}return p1;}
};2. 筛选链表( 2015年全国硕士研究生招生考试 )
考点删除节点
需要两个指针一个前一个后删除所以比较的时候比较p-next-val比较好
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* filterList(ListNode* head) {bool st[10001] {};st[abs(head-val)] true;for (auto p head; p-next;) {int x abs(p-next-val);if (st[x]) {auto q p-next;p-next q-next;delete q;} else {p p-next;st[x] true;}}return head;}
};3. 重排链表( 2019年全国硕士研究生招生考试 ) 考点1. 链表反转2. 链表合并 class Solution {
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
public:void rearrangedList(ListNode* head) {// 若只有一个元素则不需要操作if (!head-next) {return;}// 计算链表长度int len 0;for (auto p head; p; p p-next) {len;}// 移动到链表中间处int mid (len 1) / 2;auto a head;for (int i 0; i mid - 1; i) {// 由于该链表没有设头结点head 就是具有值的结点因此到 mid - 1a a-next;}// 反转后半段链表b在前c在后auto b a-next, c b-next;// a-next 是为了从中间将链表截断b-next 是因为此时的 b 是反转后链表的结尾元素a-next b-next NULL;while (c) {auto temp c-next;c-next b;b c;c temp;}// 合并链表注意此时 b 指向反转链表头部c 指向 NULLfor (auto p head, q b; q;) {auto qq q-next;// 插入结点q-next p-next;p-next q;// 移动p和qp q-next;q qq; }}
};四、日期问题
1. 日期累加 北京理工大学考研机试题 #include bits/stdc.h
using namespace std;//平年每月的天数
const int months[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};//判断是否是闰年
bool is_leap(int y)
{if(y % 400 0 || (y % 100 y % 4 0)) return true;return false;
}//获得y年第m月的天数
int get_days(int y, int m)
{if(m 2) return months[m] is_leap(y);return months[m];
}//获得y年第m月--y 1年第m月的的天数
int get_year_days(int y, int m)
{if(m 2) return (365 is_leap(y));return (365 is_leap(y 1));
}int main()
{int t;cin t;int y, m, d, days;while(t -- ){cin y m d days;if(m 2 d 29){days --;m 3, d 1;}while(days get_year_days(y, m)){days - get_year_days(y, m);y ;}while(days --){d ;if(d get_days(y, m)){m , d 1;if(m 12) y , m 1;}}printf(%04d-%02d-%02d\n, y, m, d);}return 0;
}2. 打印日期 华中科技大学考研机试题 #include iostream
#include cstring
#include algorithmusing namespace std;const int months[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};int is_leap(int year) // 闰年返回1平年返回0
{if (year % 4 0 year % 100 || year % 400 0)return 1;return 0;
}int get_days(int y, int m) // y年m月有多少天
{if (m 2) return months[m] is_leap(y);return months[m];
}int main()
{int y, s;while (cin y s){int m 1, d 1;s -- ;while (s -- ){if ( d get_days(y, m)){d 1;if ( m 12){m 1;y ;}}}printf(%04d-%02d-%02d\n, y, m, d);}return 0;
}五、表达式求值
1. 表达式求值 #include iostream
#include stack
#include string
#include unordered_map
using namespace std;stackint num;
stackchar op;//优先级表
unordered_mapchar, int h{ {, 1}, {-, 1}, {*,2}, {/, 2} };void eval()//求值
{int a num.top();//第二个操作数num.pop();int b num.top();//第一个操作数num.pop();char p op.top();//运算符op.pop();int r 0;//结果 //计算结果if (p ) r b a;if (p -) r b - a;if (p *) r b * a;if (p /) r b / a;num.push(r);//结果入栈
}int main()
{string s;//读入表达式cin s;for (int i 0; i s.size(); i){if (isdigit(s[i]))//数字入栈{int x 0, j i;//计算数字while (j s.size() isdigit(s[j])){x x * 10 s[j] - 0;j;}num.push(x);//数字入栈i j - 1;}//左括号无优先级直接入栈else if (s[i] ()//左括号入栈{op.push(s[i]);}//括号特殊遇到左括号直接入栈遇到右括号计算括号里面的else if (s[i] ))//右括号{while(op.top() ! ()//一直计算到左括号eval();op.pop();//左括号出栈}else{while (op.size() h[op.top()] h[s[i]])//待入栈运算符优先级低则先计算eval();op.push(s[i]);//操作符入栈}}while (op.size()) eval();//剩余的进行计算cout num.top() endl;//输出结果return 0;
}六、树的遍历 递归
1. 二叉树的带权路径长度 class Solution {
public:int sum(TreeNode* root, int level) {if(!root) return 0;if(!root-left !root-right) {return root-val * level;}return sum(root-left, level 1) sum(root-right, level 1);}int pathSum(TreeNode* root) {return sum(root, 0);}
};2. 重建二叉树
构建二叉树的两种情况
构建二叉树的两种情况【根据前序遍历和中序遍历 构造树】【根据后序遍历和中序遍历 构造树】
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:unordered_mapint,int pos;TreeNode* buildTree(vectorint preorder, vectorint inorder) {int n preorder.size();for (int i 0; i n; i )pos[inorder[i]] i;return dfs(preorder, inorder, 0, n - 1, 0, n - 1);}TreeNode* dfs(vectorintpre, vectorintin, int pl, int pr, int il, int ir){if (pl pr) return NULL;int k pos[pre[pl]] - il;TreeNode* root new TreeNode(pre[pl]);root-left dfs(pre, in, pl 1, pl k, il, il k - 1);root-right dfs(pre, in, pl k 1, pr, il k 1, ir);return root;}
};七、二叉搜索树与表达式树
1. 二叉排序树中序遍历是有序的 解释一下删除操作的第三点
首先我们要清楚 二叉排序树的特点是 中序遍历左根右是有序的
所以如果删除的根节点有左右子树
那么我们为了保证有序
就要把 根节点左子树的最右边 赋值给根节点 因为根节点左子树的最右边是比根节点小中最大的点
只有这样才能保证删除根节点后
左子树比新的根节点都小 右子树比新的根节点都大
#include bits/stdc.husing namespace std;const int INF 2e9;struct TreeNode
{int val;TreeNode *left, *right;TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;// 插入操作
void insert(TreeNode* root, int x)
{/*1. 递归找到x的待插入的位置2. 如果x 当前root就递归到左子树反之递归到右子树。*/ if (!root) root new TreeNode(x);// 如果发现数值相同的话就判断一下;if (root-val x) return;else if (x root-val) insert(root-left, x);else insert(root-right, x);
}void remove(TreeNode* root, int x)
{/*1. 待删除的结点只有左子树。立即可推出左子树上的结点都是小于待删除的结点的我们只需要把待删除结点删了然后左子树接上待删除结点的父节点就可以了。2. 待删除的结点只有右子树。立即可推出右子树上的结点都是大于待删除的结点的我们只需要把待删除结点删了然后右子树接上待删除结点的父节点就可以了。3. 待删除的结点既有左子树又有右子树。这个比上两个情况麻烦一点但也不麻烦需要读者理解的是怎么能删除结点后还不改变中序遍历的结果并且操作代价最小显而易见我们根据待删除结点的左子树可以得到最右下角的最后结点满足$x$并且最接近x的结点把这个结点覆盖待删除的结点然后把这个结点删除就完成了我们的操作。*/// 如果不存在直接returnif (!root) return;if (x root-val) remove(root-left, x);else if (x root-val) remove(root-right, x);else{if (!root-left !root-right) root NULL;else if (!root-left) root root-right;else if (!root-right) root root-left;else{auto p root-left;while (p-right) p p-right;root-val p-val;remove(root-left, p-val);}}
}// 输出数值 x 的前驱(前驱定义为现有所有数中小于 x 的最大的数)。
int get_pre(TreeNode* root, int x)
{if (!root) return -INF;if (root-val x) return get_pre(root-left, x);else return max(root-val, get_pre(root-right, x));
}// 输出数值 x 的后继(后继定义为现有所有数中大于 x 的最小的数)。
int get_suc(TreeNode* root, int x)
{if (!root) return INF;if (root-val x) return get_suc(root-right, x);else return min(root-val, get_suc(root-left, x));
}int main()
{int n;cin n;while (n--){int t, x;cin t x;if (t 1) insert(root, x);else if (t 2) remove(root, x);else if (t 3) cout get_pre(root, x) endl;else cout get_suc(root, x) endl;}return 0;
}2. 表达式树
本题就是中序遍历 只要不是叶子节点 就加左括号然后遍历左边 遍历完右边加右括号 class Solution {
public:string dfs(TreeNode* root) {if(!root) return ;if(!root-left !root-right) {return root-val;}string ret ;ret (;ret dfs(root-left);ret root-val;ret dfs(root-right);ret );return ret;}string expressionTree(TreeNode* root) {return dfs(root-left) root-val dfs(root-right);}
};八、Huffman树
1. 合并果子 什么是哈夫曼树
本题就记住哈夫曼树的最简代码如下
#include iostream
#include algorithm
#include queueusing namespace std;int main()
{int n;scanf(%d, n);priority_queueint, vectorint, greaterint heap;while (n -- ){int x;scanf(%d, x);heap.push(x);}int res 0;while (heap.size() 1){int a heap.top(); heap.pop();int b heap.top(); heap.pop();res a b;heap.push(a b);}printf(%d\n, res);return 0;
}2. 荷马史诗
考点 构建深度最小的哈夫曼树 利用pair 可以忽略这个段下面有 图中所说的合并的次数本质其实是根节点的深度 所以优先队列的元素是pairlong long ,int 一个记录权值 一个记录深度 考点 k进制哈夫曼树需要补零节点
题解图中有解释 原题链接 图中所说的合并的次数本质其实是根节点的深度
所以优先队列的元素是pairlong long ,int 一个记录权值 一个记录深度
#include iostream
#include cstring
#include algorithm
#include queue#define x first
#define y secondusing namespace std;typedef long long LL;
typedef pairLL, int PLI;int main()
{int n, k;scanf(%d%d, n, k);priority_queuePLI, vectorPLI, greaterPLI heap;while (n -- ){LL w;scanf(%lld, w);heap.push({w, 0});}while ((heap.size() - 1) % (k - 1)) heap.push({0, 0});LL res 0;while (heap.size() 1){LL s 0;int depth 0;for (int i 0; i k; i ){auto t heap.top();heap.pop();s t.x, depth max(depth, t.y);}heap.push({s, depth 1});res s;}printf(%lld\n%d\n, res, heap.top().y);return 0;
}八、拓扑排序
1. 有向图的拓扑序列
原题链接
这就是一个模板 算法原理可以csdn搜一下
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010;int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}bool topsort()
{int hh 0, tt -1;for (int i 1; i n; i )if (!d[i])q[ tt] i;while (hh tt){int t q[hh ];for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (-- d[j] 0)q[ tt] j;}}return tt n - 1;
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);for (int i 0; i m; i ){int a, b;scanf(%d%d, a, b);add(a, b);d[b] ;}if (!topsort()) puts(-1);else{for (int i 0; i n; i ) printf(%d , q[i]);puts();}return 0;
}九、最小生成树、最短路
1. Prim算法求最小生成树和dijk算法差不多
原题链接 从1节点出发每次走最短路径距离集合的最短路径用d表示选出最短路径再加到res上 prim算法和dijkstra算法差不多只是d的表示含义不同
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 510, M 100010, INF 0x3f3f3f3f;int n, m;
int g[N][N], dist[N];
bool st[N];int prim()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;int res 0;for (int i 0; i n; i ){int t -1;for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;if (dist[t] INF) return INF;st[t] true;res dist[t];for (int j 1; j n; j )dist[j] min(dist[j], g[t][j]);}return res;
}int main()
{scanf(%d%d, n, m);memset(g, 0x3f, sizeof g);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);g[a][b] g[b][a] min(g[a][b], c);}int res prim();if (res INF) puts(impossible);else printf(%d\n, res);return 0;
}2. Dijkstra求最短路 I #include cstring
#include iostream
#include queueusing namespace std;const int N 1e5 10;int n, m;
int head[N], e[N], ne[N], w[N], idx;
bool st[N];
int dist[N];void add(int a, int b, int c)
{e[idx] b;w[idx] c;ne[idx] head[a];head[a] idx;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;queueint q;q.push(1);st[1] true; //判重数组 队列中有重复的点没有意义while (q.size()) {int t q.front();q.pop();st[t] false;for (int i head[t]; i ! -1; i ne[i]) {int j e[i];if (dist[j] dist[t] w[i]) {dist[j] dist[t] w[i];if (!st[j]) {q.push(j);st[j] true;}}}}if (dist[n] 0x3f3f3f3f) {return -1;}return dist[n];
}int main()
{cin n m;memset(head, -1, sizeof head);for (int i 0; i m; i) {int a, b, c;cin a b c;add(a, b, c);}int t spfa();if (t -1) {cout -1 endl;}else {cout dist[n] endl;}return 0;
}
3. Floyd求最短路 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 210, INF 0x3f3f3f3f;int n, m, Q;
int d[N][N];int main()
{scanf(%d%d%d, n, m, Q);memset(d, 0x3f, sizeof d);for (int i 1; i n; i ) d[i][i] 0;while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);d[a][b] min(d[a][b], c);}for (int k 1; k n; k )for (int i 1; i n; i )for (int j 1; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);while (Q -- ){int a, b;scanf(%d%d, a, b);int c d[a][b];if (c INF / 2) puts(impossible);else printf(%d\n, c);}return 0;
}4. spfa求最短路
权值可能为负 所以需要每条路径都走 而不是像dijkstra算法只走一部分
所以spfa算法用普通队列存储即可 并且每个点可能走多次所以st需要再次false
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;const int N 100010;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;queueint q;q.push(1);st[1] true;while (q.size()){int t q.front();q.pop();st[t] false;for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (dist[j] dist[t] w[i]){dist[j] dist[t] w[i];if (!st[j]){q.push(j);st[j] true;}}}}return dist[n];
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}int t spfa();if (t 0x3f3f3f3f) puts(impossible);else printf(%d\n, t);return 0;
}十、哈希表
1. 模拟散列表 开散列方法拉链法
就记住有N个链表头节点
对于原数据可以 (x % N N) % N;找到合适位置插入到头节点
#include cstring
#include iostreamusing namespace std;const int N 1e5 3; // 取大于1e5的第一个质数取质数冲突的概率最小 可以百度//* 开一个槽 h
int h[N], e[N], ne[N], idx; //邻接表void insert(int x) {// c中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数int k (x % N N) % N;e[idx] x;ne[idx] h[k];h[k] idx;
}bool find(int x) {//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数int k (x % N N) % N;for (int i h[k]; i ! -1; i ne[i]) {if (e[i] x) {return true;}}return false;
}int n;int main() {cin n;memset(h, -1, sizeof h); //将槽先清空 空指针一般用 -1 来表示while (n--) {string op;int x;cin op x;if (op I) {insert(x);} else {if (find(x)) {puts(Yes);} else {puts(No);}}}return 0;
}开放寻址法代码
本质最多存1e5个数
#include cstring
#include iostreamusing namespace std;//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N 2e5 3; //大于数据范围的第一个质数
const int null 0x3f3f3f3f; //规定空指针为 null 0x3f3f3f3fint h[N];int find(int x) {int t (x % N N) % N;while (h[t] ! null h[t] ! x) {t;if (t N) {t 0;}}return t; //如果这个位置是空的, 则返回的是他应该存储的位置
}int n;int main() {cin n;memset(h, 0x3f, sizeof h); //规定空指针为 0x3f3f3f3fwhile (n--) {string op;int x;cin op x;if (op I) {h[find(x)] x;} else {if (h[find(x)] null) {puts(No);} else {puts(Yes);}}}return 0;
}2. 未出现过的最小正整数( 2018年全国硕士研究生招生考试 ) 由于我们需要从1去找 是否出现在数组中
如果1去遍历一遍数组 2遍历一遍数组 太麻烦
如何一步到位 其实可以用 哈希思想
把数组出现的数都映射存储到数组中
如何都没有出现
那么一定是大于数组的个数1的那个值
class Solution {
public:int findMissMin(vectorint nums) {int n nums.size();vectorbool hash(n 1);for (int x: nums)if (x 1 x n)hash[x] true;for (int i 1; i n; i )if (!hash[i])return i;return n 1;}
};十一、KMP KMP是快速帮助 子串A 去匹配 主串B的算法
我们利用next记录 当B和A不匹配的时候A应该返回B中的哪个位置
所以next应该记录的是B的快速匹配位置
具体逻辑可以搜CSDN
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 100010, M 1000010;int n, m;
char p[N], s[M];
int ne[N];int main()
{scanf(%d%s, n, p 1);scanf(%d%s, m, s 1);for (int i 2, j 0; i n; 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 m; i ){while (j s[i] ! p[j 1]) j ne[j];if (s[i] p[j 1]) j ;if (j n) printf(%d , i - n);}return 0;
}十二、排序
1. 快速排序 快速排序的核心思想是 大于x的 放到数组右边 小于x的放在数组左边 等于x的放在数组中间剩下的背模板即可
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N100020;
int a[N];
int n;
void quick_sort(int l,int r)
{if(lr) return ;int ka[lr1],il-1,jr1;while(ij){do i; while(a[i]k);do j--; while(a[j]k);if(ij) swap(a[i],a[j]);}quick_sort(l,j);quick_sort(j1,r);
}
int main()
{scanf(%d,n);for(int i0;in;i)scanf(%d,a[i]);quick_sort(0,n-1);for(int i0;in;i)printf(%d ,a[i]);return 0;
}2. 整数集合划分 #include iostream
#include algorithm
using namespace std;const int N 100010;
int a[N];int sum(int a[], int l, int r)//求数组 a[l] ~ a[r] 的和
{ int res 0;for(int i l; i r; i)res a[i];return res;
}int main()
{int n;cin n;for(int i 0; i n; i){cin a[i];}sort(a,a n);//排序int s1, s2;s1 sum(a, 0, n/2-1);//s1 的和小s2 sum(a, n/2, n - 1);//s2 的和大cout n % 2 s2 - s1;
}十三、多路归并
1. 三元组的最小距离2020年全国硕士研究生招生考试 什么是多路归并 就是三个数组排序到一个数组进行比较 是需要开一个数组的空间的
为了节约空间我们可以通过三个数组分别用三个指针 指向各自数组然后判断当前三个元素的大小关系以及进行相应的运算或者应用数据去计算之后根据三个元素的大小关系进行角标转移
放到本题中
首先我们要理解题意
题意是让我们求三个数组中放到一个数组排序后出现的最小值到最大值距离最短的是多少
比如 a b c之间满足 最小值a 到 最大值c距离最小 并且之间包含b数组的元素
或者是 b a c也可以
总之就是 最小值和最大值并且中间包含一个与这两个集合不一样的集合元素 的距离值 ✖ 2就是答案
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;const int N 100010;int l, m, n;
int a[N], b[N], c[N];int main()
{scanf(%d%d%d, l, m, n);for (int i 0; i l; i ) scanf(%d, a[i]);for (int i 0; i m; i ) scanf(%d, b[i]);for (int i 0; i n; i ) scanf(%d, c[i]);LL res 1e18;for (int i 0, j 0, k 0; i l j m k n;){int x a[i], y b[j], z c[k];res min(res, (LL)max(max(x, y), z) - min(min(x, y), z));if (x y x z) i ;else if (y x y z) j ;else k ;}printf(%lld\n, res * 2);return 0;
}十四、摩尔投票法
1. 数组中出现次数超过一半的数字 class Solution {
public:int moreThanHalfNum_Solution(vectorint nums) {int cnt 0, val;for (auto x: nums) {if (!cnt) val x, cnt ;else if (x val) cnt ;else cnt -- ;}return val;}
};十五、DFS
1. 全排列( 北京大学考研机试题 ) #include iostream
#include cstring
#include algorithmusing namespace std;const int N 10;int n;
char str[N], path[N];
bool st[N];void dfs(int u)
{if (u n) cout path endl;else{for (int i 0; i n; i )if (!st[i]){path[u] str[i];st[i] true;dfs(u 1);st[i] false;}}
}int main()
{cin str;n strlen(str);dfs(0);return 0;
}2. 八皇后 北京大学考研机试题 #includeiostreamusing namespace std;const int N 100;int g[N][N];
bool l[N*2],ll[N*2],lll[N*2];
int d[N],idx;
int n;void dfs(int u,int sum)
{if(u8){d[idx] sum;}else{for(int i 1; i 8; i){if(l[i] false ll[iu] false lll[i-u9] false){l[i] true;lll[i-u9] true;ll[iu] true;dfs(u1,sum*10i);l[i] false;lll[i-u9] false;ll[iu] false;}}}
}int main()
{cin n;dfs(1,0);while(n--){int x;cin x;cout d[x] endl;}return 0;
}高精度计算核心就是
通过数组模拟出草稿纸上的运算过程
具体逻辑可以搜csdn
十六、模拟
1. 反序输出 清华大学考研机试题
考点reverse(s.begin(), s.end()); #include iostream
#include cstring
#include algorithmusing namespace std;int main()
{string s;while (cin s){reverse(s.begin(), s.end());cout s endl;}return 0;
}2. 特殊乘法 清华大学考研机试题 #include iostream
#include cstring
#include algorithmusing namespace std;int main()
{string a, b;cin a b;int res 0;for (auto x: a)for (auto y: b)res (x - 0) * (y - 0);cout res endl;return 0;
}3. 众数 清华大学考研机试题 #include iostream
#include cstring
#include algorithmusing namespace std;int s[6][10];int main()
{int n, m;scanf(%d%d, n, m);while (n -- ){int x;scanf(%d, x);for (int i 0; i m; i ){s[i][x % 10] ;x / 10;}}for (int i 0; i m; i ){int k 0;for (int j 0; j 10; j )if (s[i][k] s[i][j])k j;printf(%d\n, k);}return 0;
}4. 糖果分享游戏 #includeiostream
#includecstring
using namespace std;
const int N110;
int candy[N],bak[N];
int n,count;
bool isequal()
{for(int i1;in;i)if(candy[i]!candy[i-1])return false;return true;
}
void share()
{memset(bak,0,sizeof(bak));for(int i0;in;i)bak[(i1)%n]candy[i]/2;for(int i0;in;i)candy[i]candy[i]/2bak[i];for(int i0;in;i)if(candy[i]%2)candy[i]candy[i]1;
}
int main()
{scanf(%d,n);while(n!0){for(int i0;in;i) scanf(%d,candy[i]);count0;while(!isequal()){share();count;}printf(%d %d\n,count,candy[0]);scanf(%d,n);}}十七、递推
1. 递推数列 清华大学考研机试题 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 10010, MOD 10000;int a[N];int main()
{int p, q, k;cin a[0] a[1] p q k;for (int i 2; i k; i )a[i] (p * a[i - 1] q * a[i - 2]) % MOD;cout a[k] % MOD endl;return 0;
}2. 吃糖果 北京大学考研机试题 #includebits/stdc.h
using namespace std;int main()
{int n,f[21];cinn;f[0]1;f[1]1;for(int i2;in;i)f[i]f[i-1]f[i-2];coutf[n];
}
十八、BFS
1. 玛雅人的密码 整体思路是用BFS暴搜 存在队列中的基本元素是pairstring,int
前者表示经过多次交换后当下的字符串的组成后者表示达到当下的字符串状态经过的交换次数
因为数字本身可能会重复出现而且对于一个字符串交换它两个不同相邻位置得到的新字符串也可能产生重复但我们要求的是最少交换次数因为BFS的性质保证了可以实现最小所以可以设置一个map映射组来存储已经出现过的字符串情况防止重复对相同组成的字符串再入队处理以作到剪枝的作用降低时间复杂度。
这道题进入BFS暴搜前要做一些基本的判断很容易就考虑不到要做好了。
#include iostream
#include cstring
#include algorithm
#include queue
#include unordered_mapusing namespace std;int n;int bfs(string start)
{queuestring q;unordered_mapstring, int dist;dist[start] 0;q.push(start);while (q.size()){auto t q.front();q.pop();for (int i 0; i n; i )if (t.substr(i, 4) 2012)return dist[t];for (int i 1; i n; i ){string r t;swap(r[i], r[i - 1]);if (!dist.count(r)){dist[r] dist[t] 1;q.push(r);}}}return -1;
}int main()
{string start;cin n start;cout bfs(start) endl;return 0;
}2. 等差数列 本题的思路由样例入手
根据样例分析出 只要每行有两个元素 那么该行就能推出所有等差数据
同理列也是
所以我们先遍历所有行和列 看哪些有两个元素的
然后根据这样行和列进行填充 填充过程中观察是否新数据使得对应的行或者列 变得大于两个元素进而可以填充
那么该过程就想到了bfs
bfs队列存储的元素是什么呢就是所在的行或者列
怎么判断是行还是列呢 行的范围为0-n 列的范围nmn
#include iostream
#include cstring
#include algorithm#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 1010, M N * 2;int n, m;
int row[N], col[N];
int q[M], hh, tt -1;
bool st[M];
PII ans[N * N];
int top;
int g[N][N];int main()
{scanf(%d%d, n, m);for (int i 0; i n; i )for (int j 0; j m; j ){scanf(%d, g[i][j]);if (g[i][j]){row[i] ;col[j] ;}}for (int i 0; i n; i )if (row[i] 2 row[i] m){q[ tt] i;st[i] true;}for (int i 0; i m; i )if (col[i] 2 col[i] n){q[ tt] i n;st[i n] true;}while (hh tt){auto t q[hh ];if (t n) // 行{PII p[2];int cnt 0;for (int i 0; i m; i )if (g[t][i]){p[cnt ] {i, g[t][i]};if (cnt 2) break;}int d (p[1].y - p[0].y) / (p[1].x - p[0].x);int a p[1].y - d * p[1].x;for (int i 0; i m; i )if (!g[t][i]){g[t][i] a d * i;ans[top ] {t, i};col[i] ;if (col[i] 2 col[i] m !st[i n]){q[ tt] i n;st[i n] true;}}}else // 列{t - n;PII p[2];int cnt 0;for (int i 0; i n; i )if (g[i][t]){p[cnt ] {i, g[i][t]};if (cnt 2) break;}int d (p[1].y - p[0].y) / (p[1].x - p[0].x);int a p[1].y - d * p[1].x;for (int i 0; i n; i )if (!g[i][t]){g[i][t] a d * i;ans[top ] {i, t};row[i] ;if (row[i] 2 row[i] n !st[i]){q[ tt] i;st[i] true;}}}}sort(ans, ans top);for (int i 0; i top; i ){auto p ans[i];printf(%d %d %d\n, p.x 1, p.y 1, g[p.x][p.y]);}return 0;
}十九、字符串处理
1. 首字母大写 #include iostream
#include cstring
#include algorithmusing namespace std;int main()
{string s;getline(cin, s);for (int i 0; i s.size(); i )if (!i || s[i - 1] )cout (char)toupper(s[i]);elsecout s[i];return 0;
}2. 日志排序 #include iostream
#include cstring
#include algorithm
#include sstreamusing namespace std;const int N 10010;int n;
string logs[N];int main()
{while (getline(cin, logs[n]))if (logs[n].size()) n ;else break;sort(logs, logs n, [](string a, string b) {stringstream ssina(a), ssinb(b);string sa[4], sb[4];for (int i 0; i 4; i ){ssina sa[i];ssinb sb[i];}if (sa[3] sb[3]) return sa[1] sa[2] sb[1] sb[2];double ta, tb;sscanf(sa[3].c_str(), %lf(s), ta);sscanf(sb[3].c_str(), %lf(s), tb);return ta tb;});for (int i 0; i n; i )cout logs[i] endl;return 0;
}3. 字符串转换整数 #include iostream
#include cstring
#include algorithm
#include limits.husing namespace std;typedef long long LL;int main()
{string s;cin s;for (int i 0; i s.size(); i )if (isdigit(s[i])){LL x 0;while (i s.size() isdigit(s[i])){x x * 10 s[i] - 0;if (x INT_MAX){puts(-1);return 0;}i ;}cout x endl;return 0;}puts(-1);return 0;
}二十、递归画图
1. 重复者 本题由于第三次图形需要知道 第二层的图形
所以需要递归
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;int n;
vectorstring p;vectorstring g(int k)
{if (k 1) return p;auto s g(k - 1);int m s.size();vectorstring res(n * m);for (int i 0; i n * m; i )res[i] string(n * m, );for (int i 0; i n; i )for (int j 0; j n; j )if (p[i][j] ! )for (int x 0; x m; x )for (int y 0; y m; y )res[i * m x][j * m y] s[x][y];return res;
}int main()
{while (cin n, n){p.clear();getchar(); // 读掉n后的回车for (int i 0; i n; i ){string line;getline(cin, line);p.push_back(line);}int k;cin k;auto res g(k);for (auto s: res) cout s endl;}return 0;
}
二十一、背包问题
1. 01背包 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 1010;int n, m;
int f[N][N];int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ){int v, w;scanf(%d%d, v, w);for (int j 0; j m; j ){f[i][j] f[i - 1][j];if (j v)f[i][j] max(f[i][j], f[i - 1][j - v] w);}}printf(%d\n, f[n][m]);return 0;
}2. 神奇的口袋( 体积恰好是 ) #includeiostreamusing namespace std;const int N 50;int f[N][N];
int a[N];
int n;int main()
{cin n;for(int i 1; i n; i){cin a[i];}f[0][0] 1;for(int i 1; i n; i){for(int j 0; j 40; j){f[i][j] f[i-1][j];if(a[i]j){f[i][j] f[i][j] f[i-1][j-a[i]];}}}cout f[n][40];return 0;
}3. 整数拆分 本题中如果用这种做法的话会爆内存
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int N 1e610, mod 1e9;
LL v[25], f[25][N]; //v[]存储 2 的 i 次幂即 2^i void init(){ //预处理出 2 的 0 次幂到 20 次幂v[0] 1;for(int i 1;i 20;i) v[i] v[i - 1] * 2;
}void solve(){int n;cin n;init();for(int i 0;i 20;i){for(int j 0;j n;j){if(!i || !j){ //状态为 f[i][0] 和 f[0][j] 时将其初始化为 1f[i][j] 1;continue;}if(j v[i]) f[i][j] f[i - 1][j]; //当 2^i j 时f[i][j]中只有一个集合有0个 2^i 的集合else f[i][j] (f[i - 1][j] f[i][j - v[i]]) % mod; //状态转移方程}}cout f[20][n];
}int main(){solve();return 0;
}
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1000010, MOD 1e9;int n;
int f[N];int main()
{scanf(%d, n);f[0] 1;for (int i 1; i n; i * 2)for (int j i; j n; j )f[j] (f[j] f[j - i]) % MOD;cout f[n] endl;return 0;
}二十二、高精度
1. N的阶乘 做法预处理
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;const int N 1010;vectorint F[N];vectorint mul(vectorint A, int b)
{vectorint C;for (int i 0, t 0; i A.size() || t; i ){if (i A.size()) t A[i] * b;C.push_back(t % 10);t / 10;}return C;
}int main()
{int n;F[0] {1};for (int i 1; i 1000; i ) F[i] mul(F[i - 1], i);while (cin n){for (int i F[n].size() - 1; i 0; i -- )cout F[n][i];cout endl;}return 0;
}2. 基本算术 #include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;int add(vectorint A, vectorint B)
{int res 0;for (int i 0, t 0; i A.size() || i B.size() || t; i ){if (i A.size()) t A[i];if (i B.size()) t B[i];t / 10;res t;}return res;
}int main()
{string a, b;while (cin a b, a ! 0 || b ! 0){vectorint A, B;for (int i a.size() - 1; i 0; i -- ) A.push_back(a[i] - 0);for (int i b.size() - 1; i 0; i -- ) B.push_back(b[i] - 0);int res add(A, B);if (!res) puts(No carry operation.);else if (res 1) puts(1 carry operation.);else printf(%d carry operations.\n, res);}return 0;
}3. 整数查询 #include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;vectorint add(vectorint A, vectorint B)
{vectorint C;for (int i 0, t 0; i A.size() || i B.size() || t; i ){if (i A.size()) t A[i];if (i B.size()) t B[i];C.push_back(t % 10);t / 10;}return C;
}int main()
{vectorint A{0};string b;while (cin b, b ! 0){vectorint B;for (int i b.size() - 1; i 0; i -- )B.push_back(b[i] - 0);A add(A, B);}while (A.size() 1 !A.back()) A.pop_back();for (int i A.size() - 1; i 0; i -- )cout A[i];cout endl;return 0;
}二十三、因式分解
1. 质因数的个数 #include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int n;while (cin n){int res 0;for (int i 2; i * i n; i )if (n % i 0){while (n % i 0){n / i;res ;}}if (n 1) res ;cout res endl;}return 0;
}2. 约数个数 #include iostreamusing namespace std;int n, x;int main()
{cin n;while (n -- ){cin x;int res 0;for (int i 1; i x / i; i )if (x % i 0) {res ;if (x / i ! i) res ;}cout res \n;}return 0;
}
3. 阶乘的末尾0上海交通大学考研机试题 本题考的是理解末尾0
末尾的0 就表示 因数中有多少个10
那么也就是有多少个因数2 和 5
由于因数2的个数一定大于5的个数
所以就看有多少个因数5就可以了
#include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int n;cin n;int res 0;while (n / 5) res n / 5, n / 5;cout res endl;return 0;
}4. 整除问题上海交通大学考研机试题 #include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;vectorvectorint get_ds(int n)
{vectorvectorint res;for (int i 2; i * i n; i )if (n % i 0){int s 0;while (n % i 0) n / i, s ;res.push_back({i, s});}if (n 1) res.push_back({n, 1});return res;
}int get_p(int n, int p)
{int res 0;while (n / p) res n / p, n / p;return res;
}int main()
{int n, m;cin n m;auto ds get_ds(m);int res 1e8;for (int i 0; i ds.size(); i ){int p ds[i][0], s ds[i][1];res min(res, (get_p(n, p) / s));}cout res endl;return 0;
}二十四、枚举
1. 与7无关的数 北京大学考研机试题 #include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int n;cin n;int res 0;for (int i 1; i n; i ){if (i % 7 0 || to_string(i).find(7) ! -1)continue;res i * i;}cout res endl;return 0;
}2. 打印极值点下标( 北京大学考研机试题 ) #include iostream
#include cstring
#include algorithmusing namespace std;const int N 110;int n;
int w[N];int main()
{cin n;for (int i 0; i n; i ) cin w[i];for (int i 0; i n; i )if (!i){if (n 1 || w[i] ! w[i 1]) cout i ;}else if (i n - 1){if (w[i] ! w[i - 1]) cout i ;}else{if (w[i] w[i - 1] w[i] w[i 1] ||w[i] w[i - 1] w[i] w[i 1])cout i ;}return 0;
}3. 最简真分数( 北京大学考研机试题 ) 【真分数】 最简真分数
分子大于分母最大公约数是1
#include iostream
#include algorithm
#include cstringusing namespace std;const int N 110;int n;
int a[N];// 欧几里得算法辗转相除法
int gcd(int a, int b) {return b? gcd(b, a % b): a;
}int main() {while (cin n n) {memset(a, 0, sizeof(a));int cnt 0;for (int i 0; i n; i) cin a[i];for (int i 0; i n; i) {for (int j 0; j n; j) {if (a[i] a[j] gcd(a[i], a[j]) 1) {cnt; }}}cout cnt endl;}return 0;
}4. 买房子 北京大学考研机试题 【算立方和平方】 include iostream
#include cstring
#include algorithmusing namespace std;int main()
{double n, k;while (cin n k){double sum n, house 200;bool flag false;for (int i 1; i 21; i ){if (sum house){cout i endl;flag true;break;}sum n;house * 1 k / 100;}if (!flag) puts(Impossible);}return 0;
}5. Special数北京邮电大学考研机试题 #include iostream
#include cstring
#include algorithm
#include cmathusing namespace std;int main()
{int T;cin T;while (T -- ){int n;cin n;int res 0;for (int i 1; i * i * i n; i ){int x i * i * i;int r sqrt(x);if (r * r x)res ;}cout res endl;}return 0;
}二十六、位运算
1. 位操作练习北京大学考研机试题 本题的思路是 把a右移1位如果超界65535也就是保留16位
然后让a a未移动的值右移15位的值 得到的就是循环移动的值了
#includeiostreamusing namespace std;int main()
{int a,b;while(cin a b){bool flag false;for(int i 0; i 16;i){int t a;a (a 1)65535;a a (t15);if(ab){cout YES endl;flag true;}}if(flagfalse){cout NO endl;}}return 0;
}2. 二进制数北京邮电大学考研机试题 就是把10进制输出二进制 不输出前导0
#include iostream
#include cstring
#include algorithmusing namespace std;int main()
{unsigned int n;while (cin n){string res;if (!n) res 0;while (n) res to_string(n 1), n 1;reverse(res.begin(), res.end());cout res endl;}return 0;
}二十七、矩阵
1. 旋转矩阵北京航空航天大学考研机试题 这道题就是找规律
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;const int N 10;int n;vectorvectorint rotate(vectorvectorint a)
{auto res a;for (int i 0; i n; i )for (int j 0, k n - 1; j n; j , k -- )res[i][j] a[k][i];return res;
}int main()
{cin n;vectorvectorint a(n, vectorint(n));auto b a;for (int i 0; i n; i )for (int j 0; j n; j )cin a[i][j];for (int i 0; i n; i )for (int j 0; j n; j )cin b[i][j];for (int i 0; i 4; i ){if (a b){cout i * 90 endl;return 0;}a rotate(a);}puts(-1);return 0;
}2. 矩阵幂【矩阵相乘】北京邮电大学考研机试题 两个矩阵相乘结果
两个矩阵a,b相乘得到一个新的矩阵c,新矩阵的第i行第j列的元素是a的第i行和b的第j列的对应元素相乘的求和。 for(int i0;in;i)for(int j0;jn;j)for(int k0;kn;k)tmp[i][j]a[i][k]*b[k][j];求矩阵的k次方
注意1次方就是 矩阵乘单位矩阵
#include iostream
#include cstring
#include algorithm
#include cmath
using namespace std;
const int N15;
int n,k;
int w[N][N];
// 将矩阵a和b相乘结果存放到c中。
void mul(int c[][N],int a[][N],int b[][N]){static int tmp[N][N];memset(tmp,0,sizeof tmp);for(int i0;in;i)for(int j0;jn;j)for(int k0;kn;k)tmp[i][j]a[i][k]*b[k][j];memcpy(c,tmp,sizeof tmp);
}int main(){cinnk;// 读入原始矩阵 for(int i0;in;i)for(int j0;jn;j)cin w[i][j];// 将res初始化为单位矩阵 int res[N][N]{0};for(int i0;in;i) res[i][i]1;while(k--) mul(res,res,w);// 输出结果矩阵 for(int i0;in;i){for(int j0;jn;j)coutres[i][j] ;coutendl; } return 0;
}3. C翻转北京邮电大学考研机试题 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 5;int n;
int g[N][N];void rotate(int x, int y, int m)
{int w[N][N];memcpy(w, g, sizeof g);for (int i 0; i m; i )for (int j 0, k m - 1; j m; j , k -- )w[i][j] g[x k][y i];for (int i 0; i m; i )for (int j 0; j m; j )g[x i][y j] w[i][j];
}int main()
{for (int i 0; i 5; i )for (int j 0; j 5; j )cin g[i][j];int a, b, x, y;cin a b x y;x --, y -- ;if (a 1) rotate(x, y, b);else{for (int i 0; i 3; i )rotate(x, y, b);}for (int i 0; i 5; i ){for (int j 0; j 5; j )cout g[i][j] ;cout endl;}return 0;
}二十八、计算几何
1. 球的计算 #include iostream
#include cstring
#include algorithm
#include cmathusing namespace std;const double PI acos(-1);int main()
{int T;cin T;while (T -- ){double x0, y0, z0, x1, y1, z1;cin x0 y0 z0 x1 y1 z1;double dx x0 - x1;double dy y0 - y1;double dz z0 - z1;double r sqrt(dx * dx dy * dy dz * dz);double v 4.0 / 3 * PI * r * r * r;printf(%.2lf %.2lf\n, r, v);}return 0;
}2. 点的距离 重新定义类的相减
#include iostream
#include cstring
#include algorithm
#include cmathusing namespace std;class CPoint
{
public:double x, y;CPoint(){}CPoint(double _x, double _y): x(_x), y(_y) {}double operator- (const CPoint t) const{double dx x - t.x;double dy y - t.y;return sqrt(dx * dx dy * dy);}
};int main()
{int T;cin T;while (T -- ){CPoint a, b;cin a.x a.y b.x b.y;printf(%.2lf\n, a - b);}return 0;
}3. 直角三角形 #include iostream
#include cstring
#include algorithm
#include cmathusing namespace std;struct CPoint
{double x, y;double operator- (const CPoint t) const{double dx x - t.x;double dy y - t.y;return sqrt(dx * dx dy * dy);}
};struct CTriangle
{CPoint a, b, c;bool check(){double d[3] {a - b, b - c, a - c};sort(d, d 3);return fabs(d[0] * d[0] d[1] * d[1] - d[2] * d[2]) 1e-8;}double get_len(){return (a - b) (b - c) (a - c);}
};int main()
{int T;cin T;while (T -- ){CTriangle t;cin t.a.x t.a.y t.b.x t.b.y t.c.x t.c.y;if (t.check()) puts(Yes);else puts(No);printf(%.2lf\n, t.get_len());}return 0;
}二十九、前缀和
1. 最长平衡串北京邮电大学考研机试题 #include bits/stdc.h
using namespace std;const int N 1e6 10;
int a[N], b[N];
int c[N];
int n;
unordered_mapint, int st;int main()
{string x;cin x;n x.size();for(int i 1; i n; i ){a[i] a[i - 1], b[i] b[i - 1];if(x[i - 1] 1) a[i] ;else b[i] ;}int res 0;st[0] 0; //初始化哈希表头, 将从0开始, 到0结束的子串记为0for(int i 1; i n; i ){c[i] a[i] - b[i];if(st.count(c[i]) ! 0) res max(res, a[i] - a[st[c[i]]]);else st[c[i]] i;}printf(%d, res * 2);return 0;
}三十、推公式
1. 数字台阶 #include iostream
#include cstring
#include algorithmusing namespace std;
int check(int x,int y)
{return x*2-(x%2);}
int main()
{int x,y,n;cinn;while(n--){cinxy;if(xy)coutcheck(x,y)endl;else if(xy2)coutcheck(x-2,y)2endl;else puts(No Number);}return 0;
}2. 整数和 推等差公式
#includebits/stdc.h
using namespace std;int main()
{int n,x,c0;cinn;while(n--){cinx;c(abs(x)1)*3*x/2;//要考虑负数情况所以一开始要设绝对值coutcendl;}
}3. 弹地小球 #include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int T;cin T;while (T -- ){double h;int n;cin h n;double s h;for (int i 0; i n - 1; i ){s h;h / 2;}printf(%.2lf\n, s);}return 0;
}三十一、最短路
1. 我想回家北京大学考研机试题 求城市1到所属阵营城市的最短路径记录在dist1[]中 求城市2到所属阵营城市的最短路径记录在dist2[]中 遍历所有边边的两端的城市i、j分别属于阵营1、2, 该边的权重为w 那么本题可以等价于求解 min(wdist[i]dist[j])
#include iostream
#include cstring
#include algorithmusing namespace std;const int N610,M20010,INF0x3f3f3f3f;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int q[N],dist1[N],dist2[N];
bool st[N];
int team[N];void add(int a,int b,int c){e[idx]b;w[idx]c;ne[idx]h[a];h[a]idx;
}void spfa(int start,int dist[]){int hh0,tt1;q[0]start;memset(dist,0x3f,sizeof dist1);dist[start]0;while(hh!tt){// 队头元素出队 int tq[hh]; if(hhN) hh0; // 循环队列 st[t]false;// 遍历该元素的所有邻接点 for(int ih[t];i!-1;ine[i]){int je[i];if(team[j]!start)continue; // 如果是不同阵营的则跳过 if(dist[j]dist[t]w[i]){dist[j]dist[t]w[i]; // 更新入队 if(!st[j]){q[tt]j;if(ttN) tt0; // 循环队列 st[j]true;}}}}
}
int main(){while(scanf(%d,n),n){scanf(%d,m);memset(h,-1,sizeof h),idx0;while(m--){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c),add(b,a,c); // 无向图添加双向边 } for(int i1;in;i) scanf(%d,team[i]); // 输入所属的团队 spfa(1,dist1);spfa(2,dist2);int resINF;for(int i0;iidx;i){int ae[i^1],be[i];// 方向相反的一对边 if(team[a]1 team[b]2) // 如果该边连接的两个城市属于不同阵营则可以更新边 resmin(res,dist1[a]w[i]dist2[b]); }if(resINF) puts(-1);else coutresendl; }return 0;
}2. 最短路径 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, MOD 100000, INF 0x3f3f3f3f;int n, m;
int p[N];
int d[N][N];int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main()
{cin n m;for (int i 0; i n; i ) p[i] i;memset(d, 0x3f, sizeof d);for (int i 0; i n; i ) d[i][i] 0;for (int i 0, len 1; i m; i , len len * 2 % MOD){int a, b;cin a b;if (find(a) ! find(b)){p[find(a)] find(b);d[a][b] d[b][a] len;}}for (int k 0; k n; k )for (int i 0; i n; i )for (int j 0; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);for (int i 1; i n; i )if (d[0][i] INF) puts(-1);else cout d[0][i] % MOD endl;return 0;
}3. 最短路径 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 55, M N * N / 2, INF 0x3f3f3f3f;int n, m, Q;
int g[N][N], d[N][N];
struct Edge
{int a, b;
}e[M];void floyd()
{memcpy(d, g, sizeof d);for (int k 1; k n; k )for (int i 1; i n; i )for (int j 1; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);
}int main()
{int T;cin T;while (T -- ){cin n m Q;memset(g, 0x3f, sizeof g);for (int i 0; i n; i ) g[i][i] 0;for (int i 1; i m; i ){int a, b, c;cin a b c;e[i] {a, b};g[a][b] g[b][a] c;}floyd();printf(%d\n, d[1][n]);while (Q -- ){int t;cin t;int a e[t].a, b e[t].b;g[a][b] g[b][a] INF;}floyd();if (d[1][n] INF) puts(-1);else cout d[1][n] endl;}return 0;
}三十二、思维题
1. 棋盘遍历问题上海交通大学考研机试题 1.n1m1时答案显然是Y
2.接着n1||m1时但棋子走出去后显然没有回头的路答案应该是N
3.接着是n%20时棋子可以先一直走到底再把最后一行遍历完再是倒数第二行倒数第三…可以发现棋子从倒数第一行开始的转向分别是右左右左右左右左…只要最后是向左就可以遍历完即n为偶数答案为Y 示意图 1 2 3 4 5 6 7 8 9 10 11 12 顺序依次为1 4 7 10 11 12 9 8 5 6 3 2 1
4.然后是m%20时棋子也是先走到底再把第二列除去第一行的棋子遍历完接着是第三第四第五列都不遍历第一行…最后再把第一行遍历了即可到达终点答案为Y 示意图 1 2 3 4 5 6 7 8 9 10 11 12 顺序依次为1 5 9 10 6 7 11 12 8 4 3 2 1 5.最后剩下的就是无解情况答案为N
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N1e51e4,M1e31e2;
const ll Maxn0x3ffffff,Minm-0x3ffffff;
ll n,m;
signed main()
{while(cinnm){if(n1m1)coutY;//情况1else if(n1||m1)coutN;//情况2else if(n%20||m%20)coutY;//情况34else coutN;//情况5cout\n;}
}三十三、哈希表
1. 子串计算北京大学考研机试题 map自动排序
#include iostream
#include cstring
#include algorithm
#include mapusing namespace std;int main()
{string str;while (cin str){mapstring, int hash;for (int i 0; i str.size(); i ){string s;for (int j i; j str.size(); j ){s str[j];hash[s] ;}}for (auto [k, v]: hash)if (v 1)cout k v endl;}return 0;
}2. 查找北京邮电大学考研机试题
unordered_set通过countx0判断是否存在 #include iostream
#include cstring
#include algorithm
#include unordered_setusing namespace std;int main()
{int n, m;cin n;unordered_setint S;while (n -- ){int x;cin x;S.insert(x);}cin m;while (m -- ){int x;cin x;if (S.count(x)) puts(YES);else puts(NO);}return 0;
}3. 单词识别北京理工大学考研机试题 #include iostream
#include cstring
#include algorithm
#include mapusing namespace std;int main()
{string str;getline(cin, str);mapstring, int hash;for (int i 0; i str.size(); i ){if (isalpha(str[i])){int j i;string word;while (j str.size() isalpha(str[j]))word tolower(str[j ]);hash[word] ;i j;}}for (auto [k, v]: hash)cout k : v endl;return 0;
}
三十四、双指针
1. 最小面积子矩阵 算法1二维前缀和
#include bits/stdc.h
using namespace std;const int N 110, INF 0x3f3f3f3f;int n, m, k, a[N][N], s[N][N], res INF;int main()
{cin n m k;for(int i 1; i n; i ){for(int j 1; j m; j ) cin a[i][j];}//预处理前缀和for(int i 1; i n; i ){for(int j 1; j m; j ){s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j];}}//枚举每个矩形for(int a 1; a n; a ){for(int b 1; b m; b ){for(int c 1; c n; c ){for(int d 1; d m; d ){int ts s[c][d] - s[c][b - 1] - s[a - 1][d] s[a - 1] [b - 1]; //矩形内数字和int tc (d - b 1) * (c - a 1); //矩形面积if(ts k) res min(res, tc); //如果数字和大于等于k更新答案}}}}if(res INF) cout -1 endl;else cout res endl;return 0;
}算法2一维前缀和 双指针
#include bits/stdc.h
using namespace std;const int N 110, INF 0x3f3f3f3f;int n, m, k, res INF;
int g[N][N], s[N][N];int main()
{cin n m k;for(int i 1; i n; i ){for(int j 1; j m; j ) cin g[i][j];}//s[j][i]表示第i列的前缀和数组for(int j 1; j m; j ){for(int i 1; i n; i ) s[j][i] s[j][i - 1] g[i][j];}for(int i 1; i n; i ){for(int j i; j n; j ){for(int l 1, r 1, sum 0; r m; r ) //双指针{sum (s[r][j] - s[r][i - 1]);while(sum - (s[l][j] - s[l][i - 1]) k) {sum - (s[l][j] - s[l][i - 1]);l ;}if(sum k)res min(res, (r - l 1) * (j - i 1));}}}if(res INF) puts(-1);else cout res endl;return 0;
}三十五、序列型DP
1. 最大序列和清华大学考研机试题 这道题目实际上就是求一串数字中某一段数字和使其最大 因此我们可以使用dp来完成 令dp[i]为以a[i]结尾的最大序列和 则dp[i]可以为 以a[i-1]结尾的最大序列和加上a[i] 与 a[i]中的最大值 即该题的动态转移方程式可以为dp[i]max(dp[i-1]a[i],dp[i]);
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N1e51e6;
const ll Min-0x3ffffff;//负∞
ll n,ansMin;// 【注】本题涉及到负数为保证后面的ansmax(ans,dp[i])ans一开始因赋值为负∞
ll dp[N],a[N];
signed main()
{cinn;for(ll i1;in;i)cina[i],dp[i]a[i];for(ll i2;in;i)dp[i]max(dp[i],dp[i-1]a[i]);//动态转移方程式for(ll i1;in;i)ansmax(ans,dp[i]);coutans;
}2. 最长ZigZag子序列 #include bits/stdc.h
using namespace std;const int N 55, INF 0x3f3f3f3f;//f[i]表示以第i个数字结尾并且是前一个数字上升得到的a[i]
//g[i]表示以第i个数字结尾并且是前一个数字下降得到的a[i]
//集合划分:【只有一个a[i]】【其他:倒数第二个元素是第j个数字并且需要是下降得到a[j]:g[j] 1】
//状态计算:f[i] max(f[i], g[j] 1);
int f[N], g[N];
int n, a[N], res -INF;int main()
{cin n;for(int i 1; i n; i ) cin a[i];for(int i 1; i n; i ){f[i] g[i] 1;for(int j 1; j i; j ){if(a[j] a[i]) f[i] max(f[i], g[j] 1);if(a[j] a[i]) g[i] max(g[i], f[j] 1);}res max(res, max(f[i], g[i]));}cout res endl;return 0;
}三十六、红黑树和并查集
1. 合并集合 #includeiostreamusing namespace std;const int N100010;
int p[N];//定义多个集合int find(int x)
{if(p[x]!x) p[x]find(p[x]);/*经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:p[x]x;*/return p[x];//找到了便返回祖宗节点的值
}int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i) p[i]i;while(m--){char op[2];int a,b;scanf(%s%d%d,op,a,b);if(*opM) p[find(a)]find(b);//集合合并操作elseif(find(a)find(b))//如果祖宗节点一样,就输出yesprintf(Yes\n);elseprintf(No\n);}return 0;
}
