考研机试题

目录 头文件与STL动态规划最大数组子串和最长公共子序列最长连续公共子串最长递增子序列最大上升子序列和0-1背包多重背包多重背包问题 I整数拆分最小邮票最大子矩阵 数学问题朴素法筛素数线性筛素数快速幂 石子合并锯木棍并查集Dijkstra单源最短路Python进制转换(整数无限大)全排列神奇的口袋全排列II放苹果求第k小八皇后问题哈夫曼编码KMP算法遍历建立二叉树

头文件与STL #include <iostream> #include <cstring> #include <algorithm> using namespace std; vector.insert(vector.begin(),2,99)//在头部插入2个99 vector.erase(vector.begin() + 5, vector.end()) //删除第5个以后的元素 map<string,int> map.insert(pair<string, int>()) map.count() //0或1 map.earse() //删除 string s; s.find() s.substr(int start,int length) //切割子串 //输入含空格字符串 getline(cin,s); //优先队列 priority_queue<int,vecotr<int>,greater<int>>; //less是降序

python输入

import sys for line in sys.stdin: arr = line.split() //拼接列表 ' '.join(list) a = int(arr[0]) 动态规划 最大数组子串和

dp[i]其实代表的是以i结尾的最大子串和

for(int i=0;i<n;i++){ cin>>a[i]; // 需要额外的ans存储max，因为是子串 dp[i+1]=max(dp[i]+a[i],a[i]); ans=max(dp[i+1],ans); } 最长公共子序列

动态规划

for(int i=1;i<=s1.size();i++){ for(int j=1;j<=s2.size();j++){ if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } 最长连续公共子串 //t存储公共子串在s1中的末尾位置 int t=0; //最大长度，要额外的maxLen存储max，因为是子串 int maxLen=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s1[i-1]==s2[j-1]){ dp[i][j]=dp[i-1][j-1]+1; // =号确保 如果不唯一，则输出s1中的最后一个。 if(dp[i][j]>=maxLen){ maxLen=dp[i][j]; //存储公共子串在s1中的末尾位置，可以输出子串 t=i-1; } } } } 最长递增子序列

.nowcoder /practice/cf209ca9ac994015b8caf5bf2cae5c98?tpId=40&tags=&title=&difficulty=0&judgeStatus=0&rp=1&sourceUrl=

dp[i]只代表以i结尾的最长递增子序列数

for(int i=0;i<n;i++){ //初始化：最长为本身 1 dp[i]=1; for(int j=0;j<i;j++){ //dp[i]代表以i结尾的最长递增子序列数 if(a[i]>a[j])dp[i]=max(dp[j]+1,dp[i]); ans=max(dp[i],ans); } } 最大上升子序列和

和上述最长递增子序列思路一致，不过dp[i]代表以i结尾的最长递增子序列的和，用ans存储结果

0-1背包 int dp[1001][1001];//代表前i个物体，背包为j的最大价值 int n,bag; int v[10001],w[10001]; cin>>n>>bag; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; } dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=bag;j++){ if(j>=v[i]){ dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]); } else{ dp[i][j]=dp[i-1][j]; } } } cout<<dp[n][bag]; 多重背包

每种物品无限件

for(int i=1;i<=n;i++){ for(int j=v[i];j<=m;j++){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } 多重背包问题 I

第 i 种物品最多有 si件，

//将 si拆成多个物品，即01背包 while(s--) { a[++t]=v; b[t]=w; }//死拆，把多重背包拆成01背包 整数拆分

一个整数总可以拆分为2的幂的和

//奇数 if(i%2)dp[i]=dp[i-1]; //偶数 ？没想明白*** else dp[i]=(dp[i-1]+dp[i/2])%1000000000; 最小邮票 dp[0][0]=0; for(int i=1;i<=m;i++){ //代表集不齐 dp[0][i]=1e9; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j-a[i]>=0) dp[i][j]=min(dp[i-1][j-a[i]]+1,dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } } 最大子矩阵

子矩阵的和：pivot - dp[k-1][j] - dp[i][q-1] + dp[k-1][q-1]

for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> matrix[i][j]; //计算机前缀和 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j]; } } int ans = INT_MIN; //记录最大子矩阵位置 int x1,x2,y1,y2; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int pivot = dp[i][j]; for (int k = 1; k <= i; k++) { for (int q = 1; q <= j; q++) { if((pivot - dp[k-1][j] - dp[i][q-1] + dp[k-1][q-1])>ans){ ans = max(ans, pivot - dp[k-1][j] - dp[i][q-1] + dp[k-1][q-1]); x1=k; x2=i; y1=q; y2=j; } } } } } cout << ans<<endl; cout<<x1<<y1<<" "<<x2<<y2<<endl; 数学问题 朴素法筛素数

求n以内的所有素数，时间O(nlog(logn))【不是最优：例如14会被2和7筛重复2次】

void get_primes(int n){ for(int i=2;i<n;i++){ //i被筛了，直接跳过 if(st[i]) continue; //i是素数，添加进数组,并筛掉与i成倍数的非素数 else {primes[cnt ++ ] = i; for(int j=2*i;j<=n;j+=i){ //j一定不是素数 st[j]=true; } } } } 线性筛素数

时间O(n)，解决重复筛

for（int i=2;i<=n;i++){ //i没被筛，加入 if(!st[i]) primes[prime_count++]=i; for(int j=0;j<prime_count;++j) { if(prime[j]*i>n) break; //翻倍，一个数 * 素数一定为合数 st[primes[j]*i]=true; //退出循环，避免之后重复进行筛选 if(i%primes[j]==0) break; } } 快速幂 int qmi(int a,int b, int p){ if(b==0)return 1 ; int k = qmi(a,b/2,p)%p; // k*k可能会超过int if(b%2==0)return (1LL*k*k) %p; else return ((1LL*k*k)%p*a)%p; } 石子合并

贪心：只能合并相邻的最小的两堆

int n; int min_idx=0; int min_sum=1e7; // 边界处理 ve.push_back(1e7); int ans=0; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; ve.push_back(x); if(min_sum>ve[i]+ve[i-1]){ min_sum=ve[i]+ve[i-1]; min_idx=i; } } while(ve.size()>2){ ans += min_sum; ve[min_idx]=ve[min_idx]+ve[min_idx-1]; ve.erase(ve.begin()+min_idx-1); min_sum=1e7; // min_idx=0; if(ve.size()<=2) break; for(int i=1;i<ve.size();i++){ if(min_sum>ve[i]+ve[i-1]){ min_sum=ve[i]+ve[i-1]; min_idx=i; } } } cout<<ans<<endl; 锯木棍

贪心-思想是WPL最小带权路径,永远合并最小的两个

#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; //自定义比较结构体 struct cmp{ //函数重载 注意两个括号！！！ bool operator()(int a,int b){ //稳定 if(a==b) return false; else return a>b; } }; int main(int argc, char** argv) { //priority_queue<int,vector<int>,greater<int>> que; priority_queue<int,vector<int>,cmp> que; int n,l; cin>>n>>l; int tmp; int ans=0; while(n--){ cin>>tmp; que.push(tmp); } while(que.size()!=1){ int a=que.top(); que.pop(); int b=que.top(); que.pop(); que.push(a+b); ans=ans+a+b; } cout<<ans; return 0; } 并查集 int Find(int a){ int x=a; while(s[x]>0){ x=s[x]; } return x; } void Union(int a,int b){ root1=Find(a); root2=Find(b); if(root2==root1)return ; else{ s[root2]=root1; } } Dijkstra单源最短路 int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中，确定一个最短的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 用t更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); st[t] = true; } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } Python进制转换(整数无限大) import sys for line in sys.stdin: a = line.split() a=int(a[0]) b=bin(a) s=(b[2:][::-1]) print(int(s,2)) 全排列

回溯法

void dfs(int k){ if(k==n+1){ for(int i=1;i<=n;i++){ cout<<arr[i]<<' '; } cout<<'\n'; return ; } for(int i=1;i<=n;i++){ //还没访问的数 if(!st[i]){ st[i]=true; // 存储第k个数 arr[k]=i; dfs(k+1); // 恢复-现场 st[i]=false; } } } int main() { cin>>n; dfs(1); } 神奇的口袋

有一个神奇的口袋，总容积是40，有n个物品,体积为Vi，装满40有多少种装法

void dfs(int u,int j){ if(u==40){ ans++; } else{ //从j开始，前面用过的舍弃掉，防止重复 for(int i=j;i<n;i++){ if(!st[i]){ st[i]=true; dfs(u+v[i],i); st[i]=false; } } } } 全排列II

带有重复元素的全排列

void dfs(int k){ if(k==n+1){ for(int i=1;i<=n;i++){ cout<<arr[i]<<' '; } cout<<'\n'; return ; } for(int i=1;i<=n;i++){ //还没访问的数 if(!st[i]){ st[i]=true; // 存储第k个数 arr[k]=i; dfs(k+1); // 恢复-现场 st[i]=false; //***当与后一个元素重复时，跳过不排列,且这一步要在恢复现场之后做 while(s[i+1]==s[i])i++; } } } int main() { cin>>n; //使重复的元素排在一起 sort(a,a+n); dfs(1); } 放苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

//处理边界 for(int i=0;i<=m;i++){ //为0的可以不用处理，数组默认为0 //1个盘子的 dp[i][1]=1; } for(int i=0;i<=n;i++){ //0个苹果的 dp[0][i]=1; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ //如果盘子多，多余的用不到的盘子都是没用的 if(j>i){ dp[i][j]=dp[i][i]; } //如果苹果多，dp[i][j]等于 有空盘子的(挑一个盘子为空)+没有空盘子(每个盘子初始都放一个苹果)的状态 else{ dp[i][j]=dp[i][j-1]+dp[i-j][j]; } } } 求第k小

使用快排划分的思想

#include <iostream> #include <algorithm> /**求第k小 */ using namespace std; int n; int a[10001]; int k; void partition(int start,int end) { int pivot=a[start]; int l=start; int r=end; while(l<r) { while(a[l]<pivot) { l++; } while(a[r]>pivot) { r--; } swap(a[l],a[r]); } a[l]=pivot; if(l==k-1) { cout<<a[l]; return ; } else if(l<k){ partition(l+1,end); } else{ partiton(start,l); } } int main(int argc, char** argv) { cin>>n; cin>>k; for(int i=0; i<n; i++) { cin>>a[i]; } partition(0,n-1); return 0; } 八皇后问题 哈夫曼编码 priority_queue<int,vector<int>,greater<int> q; int alpha[26]; //去最小的两个 KMP算法 //字符串下标都从0开始 void getNextTable(int m){ int j=0; next[0]=-1; int i=-1; while(j<m){ if(i==-1 || pattern[j]==pattern[i]){ i++; j++; next[j]=i; } else{ i=next[i]; } } return ; } int kMP(string a,string b){ int i=0,j=0; while(i<n&&j<m){ if(j==-1 || s[i]==pattern[j]){ i++; j++; } else{ j=next[j]; } } if(j==m){ return i-j+1; } else{ //匹配失败 return -1; } } 遍历建立二叉树

TNode(char c):data©,left(nullptr),right(nullptr){};

using TreeNode = struct TNode{ char data; struct TNode* left; struct TNode* right; TNode(char c):data(c),left(nullptr),right(nullptr){}; }; TreeNode* Build(TreeNode* root,char c){ if(c=='#')return NULL; // C style：(TreeNode*)malloc(sizeof(TreeNode)) root=new TNode(c); char c1=s[cnt++]; root->left=Build(root->left,c1); char c2=s[cnt++]; root->right=Build(root->right,c2); return root; } void Inorder(TreeNode* root){ if(root->left) Inorder(root->left); cout<<root->data<<endl; if(root->right) Inorder(root->right); } void postOrder(TreeNode* root){ } int main(int argc, char** argv) { TreeNode* T=NULL; T=Build(T,s[cnt++]); Inorder(T); return 0; }