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

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

目录

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

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

 第二道题（青蛙跳杯子）

第三道模拟题（2022年第二次模拟赛）

第四道模拟题（2022年第一次模拟赛）

---

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

输入样例：

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的用法： 

 第二道题（青蛙跳杯子）

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的用法：

 详细内容：C++ map用法总结（整理）

第三道模拟题（2022年第二次模拟赛）

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的用法：

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

第四道模拟题（2022年第一次模拟赛）

输入样例：

 

 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;
}