devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯 总结经典基础题型

作者：不正经 | 2024-04-15 21:25:27

赞

踩

蓝桥杯 总结经典基础题型

 十进制转R进制

  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. string tentoR(int x, int r) {
  7.     if (x == 0) return "0"; // 如果x为0，直接返回"0"
  8.     string s;
  9.     while (x) {
  10.         int num = x % r;
  11.         if (num >= 10) s += 'A' + (num - 10); // 处理10及以上的数字转为字母
  12.         else s += num + '0'; // 处理0-9的数字
  13.         x /= r;
  14.     }
  15.     reverse(s.begin(), s.end()); // 反转字符串得到正确的顺序
  16.     return s;
  17. }
  18.  
  19. int main() {
  20.     int n, r;
  21.     cin >> n >> r;
  22.     cout << tentoR(n, r);
  23.     return 0;
  24. }

计算一个数转为二进制后有几个1  

  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int calebinone(int x)
  7. {
  8. 	int cnt = 0;
  9. 	while (x)
  10. 	{
  11. 		cnt++;
  12. 		x &= x - 1;//每次将最后一个1变为0 
  13. 	}
  14. 	return cnt;
  15. }
  16.  
  17. int main()
  18. {
  19. 	int n;
  20. 	cin >> n;
  21. 	cout << calebinone(n);
  22.  
  23. }

异或(^)相同为0，不同为1

最大公约数和最小公倍数（递归版本)

  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int gcd(int a, int b) // 最大公约数
  7. {
  8.     return b == 0 ? a : gcd(b, a % b);
  9. }
  10.  
  11. int lcm(int a, int b) // 最小公倍数
  12. {
  13.     return a / gcd(a, b) * b;
  14. }
  15.  
  16. int main()
  17. {
  18.     int a, b;
  19.     cin >> a >> b;
  20.     cout << "最大公约数是：" << gcd(a, b) << endl;
  21.     cout << "最小公倍数是：" << lcm(a, b) << endl;
  22.     return 0;
  23. }

日期（闰年）

显示某一年的日历

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  5.  
  6. // 检查是否为闰年
  7. bool check(int year) {
  8.     if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
  9.         return true;
  10.     return false;
  11. }
  12.  
  13. int main() {
  14.     int y;
  15.     cin >> y;
  16.     // 根据年份调整二月天数
  17.     if(check(y))
  18.         days[2] = 29;
  19.     else
  20.         days[2] = 28; // 确保处理多个年份时对于非闰年，二月的天数正确设置为28天
  21.  
  22.     for(int i = 1; i <= 12; i++) { // 十二个月
  23.         for(int j = 1; j <= days[i]; j++) 
  24.             cout << y << "年" << i << "月" << j << "日" << endl;
  25.     }
  26.     return 0;
  27. }

判断素数（试除法&埃氏筛） 

  1. #include<iostream>
  2. #include<string>
  3. #include<cmath>
  4. #include<algorithm>
  5. #define int long long 
  6. using namespace std;
  7. //单个素数判定--试除法 O(sqrt(n))
  8. bool isprime(int n)
  9. {
  10. 	if(n<=1) return false;
  11. 	int sqrtn=sqrt(n);
  12. 	for(int i=2;i<=sqrtn;i++)
  13. 	{
  14. 		if(n%i==0)
  15. 			return false;
  16. 	}
  17. 	return true;
  18. }
  19. //多个素数判定--埃氏筛O(nloglogn) 
  20. //找到一个素数把他的倍数全筛出 
  21. #include<vector>
  22. const int N=1e6+10;
  23. bool vis[N];//标记一个数是否为素数 
  24. vector<int> prime;//素数表 
  25.  
  26. void E_sieve()
  27. {
  28. 	vis[0]=vis[1]=1;//提前处理1和2为非素数 
  29. 	for(int i=2;i<=N-10;i++)
  30. 	{
  31. 		if(!vis[i])//是素数
  32. 		{
  33. 			for(int j=2*i;j<=N-10;j+=i)
  34. 			{
  35. 				vis[j]=1;
  36. 			}
  37. 		 } 
  38. 	 } 
  39. }
  40.  
  41. signed main()
  42. {
  43. 	int n;
  44. 	cin>>n;
  45. 	cout<<"素数有："<<endl;
  46. 	E_sieve();
  47. 	for(int i=2;i<=n;i++)
  48. 	{
  49. //		if(isprime(i))
  50. //			cout<<i<<" ";
  51. 		if(!vis[i])
  52. 			cout<<i<<" ";
  53. 	}
  54. 	for(auto it:prime) {
  55. 		if(it>n) break;
  56. 		cout<<it<<" "; 
  57. 	}
  58.     return 0;
  59. }

 计算a的b次方的模运算 

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6. 	int a,b,mod;
  7. 	cin>>a>>b>>mod;
  8. 	int ans=1;
  9. 	for(int i=1;i<=b;i++)
  10. 	{
  11. 		ans*=a%mod;
  12. 		ans%=mod;
  13. 	 } 
  14. 	 cout<<ans;
  15. 	return 0;
  16. }

前缀和

一维前缀和查询区间和
  1. //一维前缀和 
  2. #include<iostream>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. const int N=1e6+10;
  7. int a[N],ps[N]; 
  8. int main(){
  9.    int n;
  10.    cin>>n;
  11.    for(int i=1;i<=n;i++)
  12.    {
  13.    		cin>>a[i];
  14.    		ps[i]=ps[i-1]+a[i];
  15.    }
  16.    int m;//查询m次区间和 
  17.    cin>>m;
  18.    while(m--)
  19.    {
  20.    		int l,r;
  21.    		cin>>l>>r;
  22.    		cout<<ps[r]-ps[l-1]<<endl;
  23. 	} 
  24.     return 0;
  25. }
 二维前缀和查询矩阵和（最大子矩阵问题）
  1. #include<iostream>
  2. using namespace std;
  3. const int N=1e3+10;
  4. int a[N][N],ps[N][N]; 
  5. int main(){
  6. 	int n; cin>>n;
  7. 	for(int i=1;i<=n;i++){
  8. 		for(int j=1;j<=n;j++){
  9. 			cin>>a[i][j];
  10. 			ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+a[i][j];
  11. 		} 
  12. 	}
  13.  
  14. 	int m; cin>>m;
  15. 	while(m--){
  16. 		int r1,c1,r2,c2;  cin>>r1>>c1>>r2>>c2;
  17. 		cout<<ps[r2][c2]-ps[r1-1][c2]-ps[r2][c1-1]+ps[r1-1][c1-1]<<endl;
  18. 	}
  19. 	return 0;
  20. }

搜索与回溯

全排列模板
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. string s;
  5. const int N=1e2+10;
  6. char ch[N];
  7. bool vis[N];
  8. void dfs(int dep){
  9. 	//5.终止条件 
  10. 	if(dep==s.size()+1){
  11. 		for(int i=1;i<dep;i++){
  12. 			cout<<ch[i];
  13. 		} cout<<endl;
  14. 		return ;
  15. 	}
  16. 	//1.枚举搜索方案
  17. 	for(int i=0;i<s.size();i++){
  18. 		//2.标记-防止重复搜索
  19. 		if(!vis[i]){
  20. 			//3.搜索 
  21. 			vis[i]=1;//标记
  22. 			ch[dep]=s[i];//记录第dep层搜了谁 
  23. 			dfs(dep+1);//进入下一层继续搜索 
  24. 			//4.回溯
  25. 			vis[i]=0; 
  26. 		} 
  27. 	} 
  28. }
  29. int main(){
  30. 	cin>>s; //abc
  31. 	dfs(1);
  32. 	return 0;
  33. }
迷宫搜索-bfs求无权图最短路 
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4.  
  5. const int N=1e3+10;
  6. char g[N][N];//迷宫数组
  7. bool vis[N][N];//标记数组
  8. int n,m,sx,sy,tx,ty,ans=-1;
  9. //方向数组
  10. int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 
  11. struct point{int x,y,step;}; 
  12. void bfs(point s){
  13. 	queue<point> q;
  14. 	//1.起点入队+标记
  15. 	q.push(s);  vis[s.x][s.y]=1;
  16. 	//2.循环广搜
  17. 	while(!q.empty()){
  18. 		//3.取出当前正在搜索的点 
  19. 		point cur=q.front();  q.pop();
  20. 		//判断是否是终点 
  21. 		if(cur.x==tx&&cur.y==ty){
  22. 			ans=cur.step;
  23. 			return ;
  24. 		} 
  25. 		//4.沿着邻接点继续搜索
  26. 		for(int i=0;i<4;i++){
  27. 			int bx=cur.x+dx[i],by=cur.y+dy[i];
  28. 			if(bx<1||bx>n||by<1||by>m) continue;
  29. 			if(g[bx][by]=='*') continue;
  30. 			if(vis[bx][by]) continue;
  31. 			q.push({bx,by,cur.step+1});
  32. 			vis[bx][by]=1;
  33. 		} 
  34. 	} 
  35. }
  36. int main(){
  37. 	cin>>n>>m;
  38. 	for(int i=1;i<=n;i++)
  39. 		for(int j=1;j<=m;j++)
  40. 			cin>>g[i][j];
  41. 	cin>>sx>>sy>>tx>>ty;
  42. 	bfs({sx,sy,0});
  43. 	cout<<ans<<endl;
  44. 	return 0;
  45. }
***图论- 有权图多源最短路Floyd
  1. #include<iostream>
  2. #include<climits>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N = 3e3 + 10, INF = INT_MAX;
  6. int g[N][N];//邻接矩阵
  7. bool vis[N];//标记数组
  8. int mindis[N][N];//含义：mindis[i][j]顶点i到顶点j的最短距离
  9. int n = 2021, s = 1;
  10. int gcd(int a, int b) {
  11. 	return b == 0 ? a : gcd(b, a % b);
  12. }
  13. int lcm(int a, int b) {
  14. 	return a / gcd(a, b) * b;
  15. }
  16. //时间复杂度O（n^3）
  17. void floyd() {
  18. 	//枚举跳板（中转点）
  19. 	for (int k = 1; k <= n; k++) {
  20. 		//枚举任意两点
  21. 		for (int i = 1; i <= n; i++) {
  22. 			for (int j = 1; j <= n; j++) {
  23. 				if (mindis[i][k] != INF && mindis[k][j] != INF) {
  24. 					if (mindis[i][k] + mindis[k][j] < mindis[i][j]) {
  25. 						mindis[i][j] = mindis[i][k] + mindis[k][j];
  26. 					}
  27. 				}
  28. 			}
  29. 		}
  30. 	}
  31. }
  32. int main() {
  33. 	fill(mindis[0], mindis[0] + N * N, INF);
  34. 	for (int i = 1; i <= n; i++) {
  35. 		for (int j = max(i - 21, 1); j <= min(i + 21, 2021); j++) {
  36. 			if (i != j) mindis[i][j] = mindis[j][i] = lcm(i, j);
  37. 		}
  38. 	}
  39. 	
  40. 	//floyd();
  41. 	//cout << mindis[1][n] << endl;
  42. 	cout << 10266837 << endl;
  43. 	return 0;
  44. }

DP 

最长上升子序列
  1. #include<iostream>
  2. using namespace std;
  3. //最长上升子序列-LIS
  4. //1.状态  dp[i] 以第i个元素作为结尾的最长上升子序列的长度
  5. //2.状态转移方程  if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1)
  6.  
  7. //a  1 2 3 4 5 6 7
  8. //   1 7 3 5 9 4 8
  9.  
  10. //dp 1 2 3 4 5 6 7
  11. //   1 2 2 3 4 3 4
  12. const int N = 1e3 + 10;
  13. int a[N], dp[N];
  14. int main() {
  15. 	int n;  cin >> n;
  16. 	for (int i = 1; i <= n; i++) {
  17. 		cin >> a[i];
  18. 		dp[i] = 1;//边界，每一个元素自身构成最长上升
  19. 	}
  20. 	int mx = 1;
  21. 	for (int i = 2; i <= n; i++) {
  22. 		//使用j遍历第i个元素之前的所有元素
  23. 		for (int j = 1; j < i; j++) {
  24. 			//找到a[j]和a[i]构成上升的情况
  25. 			if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
  26. 		}
  27. 		mx = max(mx, dp[i]); 
  28. 	}
  29. 	cout << mx << endl;
  30. 	return 0;
  31. }

STL

List链表（大量的对头尾进行操作时使用）
  1. #include<iostream>
  2. #include<list>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	list<int>ls;
  8. 	if (!ls.empty()) 
  9. 	{
  10. 		ls.pop_back();//移除列表的最后一个元素
  11. 		ls.pop_front();//移除列表的第一个元素 
  12. 	}
  13. 	ls.push_back(10);//列表的末尾添加一个元素
  14. 	ls.push_front(5);//列表的开头添加一个元素
  15. 	
  16. 	// 打印列表中的所有元素
  17.     for (int elem : ls) {
  18.         cout << elem << " ";
  19.     }
  20.     cout << endl;
  21. 	return 0;
  22. }
String字符串 
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int main(){
  6.     string s1, s2;
  7.     getline(cin, s1);
  8.     getline(cin, s2);
  9.  
  10.     s1 += s2; // 拼接
  11.  
  12.     if (s1 == s2) { // 比较
  13.         cout << "s1 and s2 are equal." << endl;
  14.     }
  15.  
  16.     s1 = s2; // 拷贝
  17.  
  18. 	//查找子串 
  19.     if(s1.find(s2)!=-1){
  20. 		cout<<s2<<" is substr of "<<s1<<endl;
  21. 	}
  22. 	while((pos=s1.find(s2,pos))!=-1){
  23. 		pos++;
  24. 		cnt++;//统计子串数量 
  25. 	}
  26. 	
  27.     reverse(s1.begin(), s1.end()); // 反转s1
  28.  
  29.     // 类型转换示例
  30.     string numStr = to_string(123); // 整数转字符串
  31.     int num = stoi(s2); // 字符串转整数
  32.     double dnum = stod(s2); // 字符串转双精度浮点数
  33.     long lnum = stol(s2); // 字符串转长整型
  34.  
  35.     return 0;
  36. }
stack栈
  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;
  4.  
  5. int main(){
  6. 	stack<int> st;
  7. 	
  8. 	int n; cin>>n;
  9. 	for(int i=1;i<=n;i++){
  10. 		int x; cin>>x;
  11. 		st.push(x);
  12. 	}
  13. 	
  14. 	while(!st.empty()){
  15. 		cout<<st.top()<<" ";
  16. 		st.pop();
  17. 	}
  18. 	return 0;
  19. }
queue队列
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. int main(){
  5. 	queue<int> q;
  6. 	
  7. 	int n; cin>>n;
  8. 	for(int i=1;i<=n;i++){
  9. 		int x; cin>>x;
  10. 		q.push(x);
  11. 	}
  12. 	
  13. 	while(!q.empty()){
  14.         //注意是front()
  15. 		cout<<q.front()<<" ";
  16. 		q.pop();
  17. 	}
  18. 	return 0;
  19. }
set(去重++排序)
  1. #include<iostream>
  2. #include<set>
  3. using namespace std;
  4.  
  5. int main(){
  6. 	set<int> s;
  7. 	int n; cin>>n; 
  8. 	for(int i=1;i<=n;i++){
  9. 		int x; cin>>x;
  10.         //插入元素用insert
  11. 		s.insert(x);//底层是红黑树 O（logn） 
  12. 	}
  13. 	
  14. 	for(auto it:s) cout<<it<<" ";
  15. 	return 0;
  16. }
map(针对key去重+排序  )
  1. #include<iostream>
  2. #include<map>
  3. using namespace std;
  4. //STL-map
  5. int main(){
  6. 	map<int,string> mp;
  7. 	int n; cin>>n; 
  8. 	for(int i=1;i<=n;i++){
  9. 		int id; string book;
  10. 		cin>>id>>book;
  11. 		//map.insert({id,book});
  12. 		mp[id]=book;
  13. 	}
  14. 	
  15. 	for(auto p:mp) cout<<p.first<<" "<<p.second<<endl;
  16. 	return 0;
  17. }

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/430168
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号