大家好，我是泡泡，接下来几天每天都有复习
目录
今日练习专题：
一丶成绩统计
二丶既约分数
三丶最优包含
复习专题：
一丶空间
二丶等差数列
三丶回文日期
四丶青蛙跳杯子
今日练习专题：
一丶成绩统计
题目链接：成绩统计 - 蓝桥云课 (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;
}
还有八天！！冲！！！！！
