今日练习专题：
一、成绩统计
题目链接：成绩统计 - 蓝桥云课 (lanqiao.cn)
题目要求：
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。
请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。
解题思路：
这是一道求及格率和优秀率的题目，我们选择使用printf来输出答案，把得出来的整数型换成浮点再输出。
#include<bits/stdc++.h> using namespace std; int main() { int n; int num = 0, sum = 0; cin >> n; for(int i=0;i<n;i++) { int x; cin>>x; if(x>=60) { num++; } if(x>=85) { sum++; } } printf("%.0lf%%\n%.0lf%%",(num*100.0)/(n*1.0),(sum*100.0)/(n*1.0)); return 0; }
二、既约分数
题目链接：既约分数 - 蓝桥云课 (lanqiao.cn)
题目要求：
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如 4/3,8/1,1/7， 都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？
解题思路：
直接用欧几里得求就完事了，这是简单数论应该都会。
#include<stdio.h> #include<algorithm> using namespace std; int gcd(int a,int b) { if(a%b==0) { return b; } return gcd(b,a%b); } int main() { int ans=0; for(int i=1;i<=2020;i++) { for(int j=1;j<=2020;j++) { if(gcd(i,j)==1) { ans++; } } } printf("%d",ans); }
三、最优包含
题目链接：最优包含 - 蓝桥云课 (lanqiao.cn)
题目要求：
我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。
给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T ？
其中，1≤∣T∣≤∣S∣≤1000。
解题思路：
dp,闫氏dp分析！
状态表示：f[i,j]
集合：S串中前i个字符，包含有T串中前j个字符最少需要修改的字符个数
属性：min
状态计算：
如果S[i]=T[j] ,那么T的最后一位要么和S[i]相等，要么和前面的相等，得出公式为：f[i][j] = min(f[i-1][j],f[i-1][j-1]);
如果S[i]!=T[j],那么让T[j]和S串前面的字符一样，或者修改S[i]，得出公式：f[i][j]= min(f[i-1][j-1]+1,f[i-1][j])
状态转移方程就出来了 然后就是输入 初始化 因为下标从0开始，所以我们+1，求最小初始化正无穷，每次初始化第一个为0，然后就套公式。
#include<bits/stdc++.h> using namespace std; char a[1000],b[1000]; int f[1000][1000]; int main() { cin>>a+1>>b+1; int l1=strlen(a+1); int l2=strlen(b+1); memset(f,127,sizeof f); f[0][0]=0; for(int i=1;i<=l1;i++) { f[i][0]=0; for(int j=1;j<=l2;j++) { if(a[i]==b[j]) { f[i][j]=min(f[i-1][j],f[i-1][j-1]); } else { f[i][j]=min(f[i-1][j],f[i-1][j-1]+1); } } } cout<<f[l1][l2]; return 0; }
复习专题：
一、空间
题目链接：空间 - 蓝桥云课 (lanqiao.cn)
题目要求：
小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？
解题思路：
简单的手算，1mb1024kb 1kb1024b 1b=8bit
(256 * 1024 * 1024 * 8)/32
二、等差数列
题目链接：等差数列 - 蓝桥云课 (lanqiao.cn)
题目要求：
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
解题思路：
主要是复习一下等差数列这种简单数学题，不要忘了做法
#include<bits/stdc++.h> using namespace std; //就是对它先排序找出最小的差，那就是等差数列差， //要注意的一点就是要判断一下它的差是不是0，如果是0的话最小就是n个。 int a[100001]; int main() { int n; cin>>n; int x = INT_MAX; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n); for(int i=1;i<n;i++) { x = min(a[i]-a[i-1],x);//找到最小的差 就是等差数列的差 } if(!x) { cout<<n;//如果差是0 最小就是n个 } else { int sum = (a[n-1]-a[0])/x+1;//如果不是0 那就让最大的数-最小的数并且除以该差+1 cout<<sum; } return 0; }
三、回文日期
题目链接：回文日期 - 蓝桥云课 (lanqiao.cn)
题目要求：
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。
有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。
也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。
解题思路：
大模拟！！！懂得都懂
#include<bits/stdc++.h> using namespace std; int pd(int x,int y) { switch(y) { case 2: if((x%4==0&&x%100==1)||x%400==0) return 29; else return 28; break; case 1: case 3: case 5: case 7: case 8: case 10: case 12: return 31; default: return 30; } } void print(int a,int b,int c) { cout<<a; if(b<10) { cout<<"0"<<b; } else { cout<<b; } if(c<10) { cout<<"0"<<c<<endl; } else { cout<<c<<endl; } } int main() { int n,y,r; scanf("%4d%2d%2d",&n,&y,&r); int flag = 0; for(int i=n;i;i++) { int m = n%10*10+n/10%10; int z = i/100%10*10+i/1000; if(i>n) { if(m<=12&&m>=1&&z<=pd(i,m)) { if(flag==0) { print(i,m,z); flag = 1; } if(i/1000==i/10%10&&i/100%10==i%10) { print(i,m,z); break; } } else { if(m<=12&&m>=1&&z<=pd(i,m)) { if(flag==0) { print(i,m,z); flag = 1; } if(i/1000==i/10%10&&i/100%10==i%10) { print(i,m,z); break; } } } } } return 0; }
四、青蛙跳杯子
题目链接：“蓝桥杯”练习系统 (lanqiao.cn)
题目要求：
X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
*WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。
X星的青蛙很有些癖好，它们只做3个动作之一：
1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要1步，就可跳成下图局面：
WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
解题思路：
bfs变种，需要用map
#include<bits/stdc++.h> using namespace std; struct node{ string s; int x; int d; }; map<string,bool>vis; int dx[6] = {-1,1,-2,2,-3,3}; string s,t; void bfs(int x) { node now,next; now.x = x,now.d = 0,now.s = s; queue<node>q; q.push(now); vis[now.s] = 1; while(q.size()) { now = q.front(); q.pop(); if(now.s == t) { cout<<now.d; return; } for(int i=0;i<6;i++) { next.x = now.x + dx[i]; if(next.x >= 0 && next.x < s.size()) { next.s = now.s,next.d = now.d + 1; swap(next.s[now.x],next.s[next.x]); if(!vis[next.s]) { q.push(next); vis[next.s] = 1; } } } } } int main() { cin>>s>>t; int x = s.find('*'); bfs(x); return 0; }
还有八天！！冲！！！！！
