【蓝桥杯】每日四道填空题（两道真题+两道模拟题）| 第三天_蓝桥杯填空题

专栏： 蓝桥杯——每日四道填空题（两道真题+两道模拟题）
&离蓝桥杯已经不到一个月时间了，赶快刷起来吧，填空题一定别丢分！！
୧꒰•̀ᴗ•́꒱୨
另一个专栏是： 蓝桥杯——编程题刷题营（每日四题，两道模拟，两道真题）

目录

第一道真题（2021省赛）：路径   |   答案：10266837

第二道真题（2021省赛）：裁纸刀 |  答案：443

第三道模拟题（切面条）：答案：1025

第四道模拟题（2022省赛第四次模拟）：数字操作 | 答案：14

---

第一道真题（2021省赛）：路径   |   答案：10266837

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

运行限制
最大运行时间：1s
最大运行内存: 128M

---

#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
    if(x % y == 0) return y; //辗转相除法求最大公约数，在利用最小公倍数等于两数之积/最大公约数，得到最大公约数
 
    else return gcd(y,x % y);
}
int main()
{
    int f[2022];
    memset(f,0,sizeof f);
    for(int i = 1;i <= 2021;i++) {     
        for(int j = i+1;j <= i+21;j++) {
            if(j > 2021)
                break;
            if(f[j] == 0)
                f[j] = f[i]+j*i/gcd(i,j); //用f[]记录下每次1能走到j的路径长度
            else    
                f[j] = min(f[j],f[i]+j*i/gcd(i,j)); //若有另一条路径，记录最短的路径
        }
    }
    cout << f[2021] << endl;
}

第二道真题（2021省赛）：裁纸刀 |  答案：443

问题描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝有一个裁纸刀，每次可以将一张纸沿一条直线裁成两半。

小蓝用一张纸打印出两行三列共 6 个二维码，至少使用九次裁出来，下图给出了一种裁法。

在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁 4 次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。

如果小蓝要用一张纸打印出 20 行 22 列共 440 个二维码，他至少需要裁多少次？

运行限制
最大运行时间：1s
最大运行内存: 256M

---

这种纯找规律的数学题，在填空题里也很常见，这里给了一道简单的题。

解释：先看例子，边缘必须裁四次，然后得到两行三列共六张二维码。
横线5裁一次，竖线6 7 8 9各裁一次，加上裁边缘的四次，共九次。
也就是说，横向裁剪次数为【行数-1】次。
竖向裁剪次数为【(列数-1)*行数】次。
题目共20行22列，则次数为：4 + 19 + (21*20) = 443次。（数据量比较大时，建议用计算机处理）

第三道模拟题（切面条）：答案：1025

一根高筋拉面，中间切一刀，可以得到2根面条。

如果先对折1次，中间切一刀，可以得到3根面条。

如果连续对折2次，中间切一刀，可以得到5根面条。 那么，连续对折10次，中间切一刀，会得到多少面条呢？

---

图解来源技能树：

切面条
一根高筋拉面，中间切一刀，可以得到2根面条。
如果先对折1次，中间切一刀，可以得到3根面条。
如果连续对折2次，中间切一刀，可以得到5根面条。 那么，连续对折10次，中间切一刀，会得到多少面条呢？

如图所示：折叠一次两次三次的图像均已画出。出去不折叠这个特殊情况之外，可以分析规律得出公式：x = 2^k + 1 (x是面条条数，k是对折次数)。故答案为：2^10 + 1 =1025

第四道模拟题（2022省赛第四次模拟）：数字操作 | 答案：14

 这题是典型的bfs题，只是把路径距离抽象成次数。

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 3000;
queue<int>q; //bfs的实现就是用队列哦 
bool used[N] = {false}; //排除已经走过的数。 
int f[N]; //f[N]用于求每个结点（这里是每个数）到2021这个结点的距离，这里的距离都是1（因为题目是求操作次数） 。 
int bfs()
{
	q.push(2021);
	used[2021] = true;
	f[2021] = 0;
	while(q.size())  //q永远都不会为空  
	{
		int t = q.front();
		if(t == 1) break; //走到了1，就表明是最短路径了，因为bfs满足每个路径每次一起走一次 ，
		                 //即然这条路径先到1，那是不是就是最短路径啊！！ 
	    q.pop(); //走了的点记得出队，保证走下一个数。
		if(used[t+1] == false) 
		{
			q.push(t+1);
			used[t+1] = true;//排除此点 
			f[t+1] = f[t] + 1; //记录距离，即操作次数 
		}
		if(used[t-1] == false) 
		{
			q.push(t-1);
			used[t-1] = true; 
			f[t-1] = f[t] + 1; 
		}
		if(t % 2 == 0 && used[t/2]== false) 
		{
			q.push(t/2);
			used[t/2] = true;
			f[t/2] = f[t] + 1; //记录距离，即操作次数 
		}
	}
	return f[1];
} 
int main()
{
	cout<<bfs()<<endl;
	return 0;
}