​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

时间:2021-04-19 01:30:41

专栏: 蓝桥杯——每日四道编程题(两道真题+两道模拟)
蓝桥杯就要开始了,这些题刷到就是赚到”
₍ᐢ..ᐢ₎
另一个专栏: 蓝桥杯——每日四道填空题(两道真题+两道模拟题)

目录

专栏: 蓝桥杯——每日四道编程题(两道真题+两道模拟)“蓝桥杯就要开始了,这些题刷到就是赚到”₍ᐢ..ᐢ₎♡另一个专栏: 蓝桥杯——每日四道填空题(两道真题+两道模拟题)

第一道题(高精度求阶乘之和)

 第二道题(青蛙跳杯子)

第三道模拟题(2022年第二次模拟赛)

第四道模拟题(2022年第一次模拟赛)


第一道题(高精度求阶乘之和

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

输入样例:

3

 输出样例:

9

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

这题 n <= 50 ,很显然 int 的范围为:12!~ 13!;long long 的范围为:20!~  21!;

所以会涉及到高精度乘法和高精度加法。

#include<bits/stdc++.h>
using namespace std;

vector<int> mul(vector<int> A , int b)  //i的值最大只有50,所以采用高精度*低精度
{
	vector<int> C;
	int t=0;
	for(int i = 0 ; i < A.size() ; i++)  
	{
		if(i < A.size()) t += A[i] * b;  //上一个数的进位记得加上 
		C.push_back(t % 10);  //只取各位,其余的是进位
		t /= 10; //算进位
	}
  while (t){
    C.push_back(t % 10) ;
    t /= 10;
    //计算到最后一个相乘的进位后,已经退出循环了,这里要把它加上,注意进位可以是几百,上千,因此要用循环
  }
	
	while(C.size() > 1 && C.back() == 0)	C.pop_back();  //记得处理前导0
	
	return C;
}
vector<int> add(vector<int>A , vector<int>B)  //高精度+高精度(不需要去除前导零)
{
    if(A.size() < B.size()) return add(B,A); //这里一定要先确定好,那个数是最大的。
    vector<int>C;
    int t = 0;
    for(int i = 0 ; i < A.size() ; i++)
    {
        t += A[i]; //上一个数的进位记得加上
        if(i < B.size()) t += B[i]; //当A数对应的长度大于B数时,就只有A数了,不加B数了。
        C.push_back(t % 10);  
        t /= 10;  //大于10进位
    }
    if(t) C.push_back(t);  //如果它们最后一个数相加还有进位的法(此时已经退出循环了),这里如果进位大于0,记得加上。
    return C;
    
}

int main()
{
	int n;
	
	cin>>n;
	
	vector<int> jiec;
	vector<int> sum;
	sum.push_back(1);  //初始化,阶乘1不需要要算,直接加上就可以了
	
	for(int k = 2 ; k <= n ; k++)
	{
		jiec.clear();   //每次都是需要清空的,每个阶乘要独立的算
		jiec.push_back(1);  
		
		for(int i = 2 ; i <= k ; i++)  //计算单个阶乘 
		{
			jiec = mul(jiec,i); //高精度乘法,每次计算结果返回的已经是倒序的了,不需要再逆序一下了
		}
		
		sum = add(sum,jiec);  //高精度加法
	}
	
	for(int i=sum.size()-1;i >= 0;i--)	printf("%d",sum[i]); //逆序输出
	
	return 0;
 } 

高精度减高精度:

vector<int> sub(vector<int> A, vector<int> B)  //这里的A > B,在执行函数之前一定要把大小确定了
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ ) //注意A 和 B 都是逆序存入的
    {
        t = A[i] - t; //上一个数的借位记得减掉
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);  //想减数可能为负数
        if (t < 0) t = 1; //小于零向上借一位
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导零
    return C;
}

高精度除低精度:

vector<int> div(vector<int> A, int b, int &r) //A 为被除数,b为除数,r为余数
{
    vector<int> C;
    r = 0;
    for (int i = 0; i < A.size() ; i -- )  //A之前不需要逆序存入
    {
        r = r * 10 + A[i]; //上一个数的余数记得加上
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();  //去除前导零
    return C;
}

总结:

  1. 高精度加法不需要去除前导零,其他都要去除前导零。
  2. 高进度除法不需要逆序存入(不从低位到高位算起),其他都要逆序存入
  3. 最后输出结果都需要逆序输出。 

顺便再总结下vector的用法: 

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

 第二道题(青蛙跳杯子

X 星球的流行宠物是青蛙,一般有两种颜色:白色和黑色。

X 星球的居民喜欢把它们放在一排茶杯里,这样可以观察它们跳来跳去。

如下图,有一排杯子,左边的一个是空着的,右边的杯子,每个里边有一只青蛙。

*WWWBBB

其中,W 字母表示白色青蛙,B 表示黑色青蛙,∗ 表示空杯子。

X 星的青蛙很有些癖好,它们只做 3 个动作之一:

  • 跳到相邻的空杯子里。
  • 隔着 1 只其它的青蛙(随便什么颜色)跳到空杯子里。
  • 隔着 2 只其它的青蛙(随便什么颜色)跳到空杯子里。

对于上图的局面,只要 1 步,就可跳成下图局面:

WWW ∗BBB

本题的任务就是已知初始局面,询问至少需要几步,才能跳成另一个目标局面。

输入描述

输入为 2 行,2 个串,表示初始局面和目标局面。我们约定,输入的串的长度不超过 15。

输出描述

输出要求为一个整数,表示至少需要多少步的青蛙跳。

输入输出样例

输入样例:

*WWBB
WWBB*

输出样例:

2

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

这里找了一道bfs的真题,复习一下吧,顺便复习一下map的使用

#include <bits/stdc++.h>

using namespace std;
string st_str,end_str; //分别表示初始局面和目标局面
int n;
int d[6] = {-3,-2,-1,1,2,3}; //向左边跳有三种跳法,右边跳有三种跳法
map<string,int> ans; //


//补全BFS函数,百分之八十都是模板了
int bfs()
{
    //声明一个队列
    queue<string> q;
    //将当前的状态入队
    q.push(st_str);
    
    ans[st_str] = 0;
    
    //当队列不为空的时候
    while(q.size())
    {
        //取出队头
        string ss = q.front();
        q.pop();
        
        int cnt = ans[ss]; //记录到达这个局面需要的步数
        
        int x = ss.find('*'); //记录空杯子的位置
        
        //拓展六个方向
        for(int i = 0;i < 6;i++)
        {
            int z = x + d[i]; 
            
            //判断出来的距离,是合法的
            if(z>= 0 && z < n)
            {
                swap(ss[x],ss[z]); //交换青蛙和当前空杯子的位置
                if(!ans.count(ss)) //用count来判断当前字符串是否在哈希表中出现过
                {
                    ans[ss] = cnt + 1;  //把每次变换后的结果存下来,避免重复
                    //符合结果,输入
                    if(ss == end_str) return ans[ss]; //当第一次变到目标局面,就肯定是最少的步骤
                    q.push(ss); 
                    
                }

                //还原现场(注意!!!!,不要局限模板,要因题而异)
                swap(ss[x],ss[z]);
            }
        }
    }
    
    return -1;
}

int main()
{

    cin >> st_str >>end_str;
    n = st_str.size();

    cout << bfs() <<endl;
    
    return 0;
}

做完后,如果想再检验一下自己,就做一下 【蓝桥杯】每日四道填空题(两道真题+两道模拟题)| 第三天里面那道数字操作吧。

map的用法:

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

 详细内容:C++ map用法总结(整理)

第三道模拟题(2022年第二次模拟赛)

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

5
lanqiao
hi
hello
hello
lanqiao

【样例输出】

lanqiao
hi
hello

【评测用例规模与约定】

对于所有评测用例,1 <= n <= 100,每个单词的长度不超过 100。最大运行时间 :1s

复习set的使用。

#include <bits/stdc++.h>
using namespace std;

int n;
set<string> st;
string str;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> str;
        if (st.count(str)) continue;
        st.insert(str);
    }
    for (auto s = st.rbegin() ; s != st.rend() ; ++s){ //注意是s++,别写成s--了。 
    	cout<<*s<<endl;
	}
    return 0;
}

 set的用法:

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

 详细内容:C++中set使用详细说明

第四道模拟题(2022年第一次模拟赛)

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天

输入样例:

 

 3
 12:00:00 12 1
 12:01:02 5 2
 12:01:10 0 0

输出样例

824

【评测用例规模与约定】

对于所有评测用例,1 <= n <= 100, 0 <= U, I <= 100。最大运行时间:1s

这题和【蓝桥杯】每日四道编程题(两道真题+两道模拟)| 第三天 中那道时间显示,考察了我们对于时间的相关计算。

每次输入记下时间戳与功率

输入时拿时间差值乘以功率加在答案里

每次输入更新时间戳与功率

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
int last = 0, p = 0;	// 上次时间戳与功率
int ans = 0;

// 时间字符串转化为秒作为时间戳
int toSecond(string s) {
    int h = (s[0] - '0' + 0) * 10 + (s[1] - '0' + 0);
    int m = (s[3] - '0' + 0) * 10 + (s[4] - '0' + 0);
    int second = (s[6] - '0' + 0) * 10 + (s[7] - '0' + 0);
    return second + m * 60 + h * 60 * 60;
}

signed main() {
    string s;
    int u, i;
    cin >> n;
    while (n--) {
        cin >> s >> u >> i;
        int second = toSecond(s);
        ans += p * (second - last);
        last = second;
        p = u * i;
    }
    cout << ans << endl;
    return 0;
}

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第5天