移动距离

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

小明初始在二维平面的原点，他想前往坐标 $(233, 666)$。在移动过程中，他只能采用以下两种移动方式，并且这两种移动方式可以交替、不限次数地使用：

水平向右移动，即沿着 $x$ 轴正方向移动一定的距离。
沿着一个圆心在原点 $(0, 0)$、以他当前位置到原点的距离为半径的圆的圆周移动，移动方向不限（即顺时针或逆时针移动不限）。

在这种条件下，他到达目的地最少移动多少单位距离？你只需要输出答案四舍五入到整数的结果。

题目解析

因为通过旋转所走的路程也算是在总的移动距离里面，凭感觉，可知道，要想到达目标点位，我们只能旋转一次，这样是最优的，所以我们首先走，$\sqrt{223^2+666^2}$，然后再旋转即可到达。
代码如下：注意输出要求

	double r=sqrt(233*233+666*666);
	r+=r*atan((double)666/233);
	cout<<(int)r;

客流量上限

题目描述

一家连锁旅馆在全国拥有 $2025$ 个分店，分别编号为 $1$ 至 $2025$。随着节日临近，总部决定为每家分店设定每日客流量的上限，分别记作 $A_1, A_2, \dots , A_{2025}$。这些上限并非随意分配，而是需要满足以下约束条件：

$A_1, A_2, \dots , A_{2025}$ 必须是 $1$ 至 $2025$ 的一个排列，即每个 $A_i$ 均是 $1$ 至 $2025$ 之间的整数，且所有 $A_i$ 互不相同。
对于任意分店 $i$ 和 $j$（$1 \leq i, j \leq 2025$，$i$ 可等于 $j$），它们的客流量上限 $A_i$ 和 $A_j$ 的乘积不得超过 $i \times j + 2025$。

这些约束旨在平衡各分店客流压力，确保服务质量和运营稳定性。

现在，请你计算这样的分配方案究竟有多少种。由于答案可能很大，你只需输出其对 $10^9 + 7$ 取余后的结果即可。

题目解析

题目中说i可以等于j，那么说明这可能是个特殊情况，所以我们可以得到以下式子
$$A_i^2 \leq i^2+2025$$
那么我们可以去暴力打表

for(int i=1;i<=2025;i++){
		cout<<i<<" "<<(int)sqrt(i*i+2025)<<endl;
	}

可以发现当$i==1013$开始，开方之后的值就是$i$本身，所以我们可以得到，在$i\ge1013$时，$A_i==i$。所以$A_{1\sim1012} \le 1012$

当$1\le i\le1012<j\le2025$时，

$A_i\times A_j==A_i\times j$

$A_i\times A_j\leq i\times j+2025$

$A_i\times j\le i\times j+2025$

$A_i\le i+\frac{2025}{j}$

$$A_i\le i+1$$

所以对于$A_i$可以选择$1\le A_i\le i+1$
因为整个序列是个排列，不能有重复数字。
所以每个位置只有两种选择,总量为$2^{1012}$

long long ans=1;
	int mod=1e9+7;
	for(int i=1;i<=1012;i++){
		ans*=2;
		ans%=mod;
	}
	cout<<ans;

可分解的正整数

P12132 [蓝桥杯 2025 省 B] 可分解的正整数

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件：

序列长度至少为 $3$。
序列中的数字是连续递增的整数（即相邻元素之差为 $1$），可以包括正整数、负整数或 $0$。

例如，$[1, 2, 3]$、$[4, 5, 6, 7]$ 和 $[−1, 0, 1]$ 是符合条件的序列，而 $[1, 2]$（长度不足）和 $[1, 2, 4]$（不连续）不符合要求。

现给定一组包含 $N$ 个正整数的数据 $A_1, A_2, \dots , A_N$。如果某个 $A_i$ 能够表示为符合上述条件的连续整数序列中所有元素的和，则称 $A_i$ 是可分解的。

请你统计这组数据中可分解的正整数的数量。

题目解析

不难发现，当你选择-1,0,1时，就已经满足序列长度为3，这时候再选2，就能满足条件，类比发现，$x\ge 2$都是有序列可以满足条件的，只有当$x==1$时没有满足条件的序列。

int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(x==1){
			continue;
		}
		ans++;
	}
	cout<<ans;

产值调整

题目描述

偏远的小镇上，三兄弟共同经营着一家小型矿业公司“兄弟矿业”。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数 $A$、$B$ 和 $C$ 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的生计。

然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时，将根据当前的产值 $A$、$B$、$C$，计算新产值：

金矿新产值：$A'=\lfloor \dfrac{B+C}{2} \rfloor$；
银矿新产值：$B'=\lfloor \dfrac{A+C}{2} \rfloor$；
铜矿新产值：$C'=\lfloor \dfrac{A+B}{2} \rfloor$；

其中，$\lfloor \rfloor$ 表示向下取整。例如，$\lfloor 3.7\rfloor = 3$，$\lfloor 5.2\rfloor = 5$。

计算出 $A'$、$B'$、$C'$ 后，同时更新：$A$ 变为 $A'$，$B$ 变为 $B'$，$C$ 变为 $C'$，作为下一年调整的基础。

三兄弟认为这个方法能平衡产值波动，于是计划连续执行 $K$ 次调整。现在，请你帮他们计算，经过 $K$ 次调整后，金矿、银矿和铜矿的产值分别是多少。

评测用例规模与约定

对于 $30%$ 的评测用例，$1 \leq T \leq 100$，$1 \leq A, B, C, K \leq 10^5$。
对于 $100%$ 的评测用例，$1 \leq T \leq 10^5$，$1 \leq A, B, C, K \leq 10^9$。

题目分析

根据100%的大小，正常做的复杂度为$O(TK)$,这个数值到了1e14，很明显会超时，我们其实可以打表看一看有没有规律，像这种互相制约的，会最终取向同一个数。
我们打表投入一下数据1 1000000000 2000000000 3000000000 1000，以及1 1000000000 2000000000 3000000000 100，会发现其在100次之内$a,b,c$就会趋于同一个数，所以我们有了如下代码

#define int long long
signed main(){
	int t;
	cin>>t;
	while(t--){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		int na,nb,nc;
		d=min((long long)100,d);
		for(int i=1;i<=d;i++){
			na=(b+c)/2;
			nb=(a+c)/2;
			nc=(a+b)/2;
			a=na,b=nb,c=nc;
		}
		cout<<a<<" "<<b<<" "<<c<<endl;
	}
}

画展布置

题目描述

画展策展人小蓝和助理小桥为即将举办的画展准备了 $N$ 幅画作，其艺术价值分别为 $A_1, A_2, \dots , A_N$。他们需要从这 $N$ 幅画中挑选 $M$ 幅，并按照一定顺序布置在展厅的 $M$ 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于突兀，导致观众的观展体验不够流畅。

为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 $M$ 幅画，应使艺术价值的变化程度通过一个数值 $L$ 来衡量，且该值越小越好。数值 $L$ 的定义为：

$$L=\sum_{i=1}^{M-1} |B_{i+1}^2-B_i^2|$$

其中 $B_i$ 表示展厅第 $i$ 个位置上画作的艺术价值。

现在，他们希望通过精心挑选和排列这 $M$ 幅画作，使 $L$ 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。

题目解析

将数值L的公式进行分析，发现以下结论
$$L=|B_{i+M-1}^2-B_i^2|$$
所以我们直接对读入的每个数进行平方，然后在进行排序，之后通过循环搜索答案。
注意数据范围，平方会爆$int$大小，需要开long long。

const int MAXN=1e6+10;
#define int long long
int a[MAXN];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]*=a[i];
	}
	sort(a+1,a+n+1);
	int ans=1e17;
	for(int i=1;i<=n-m+1;i++){
		ans=min(ans,a[i+m-1]-a[i]);
	} 
	cout<<ans<<endl;
}

水质检测

题目描述

小明需要在一条 $2 \times n$ 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 $A$ 和 $B$ 连通，$B$ 和 $C$ 连通，那么 $A$ 和 $C$ 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

评测用例规模与约定

对于 $100%$ 的评测用例，保证 $n \leq 1000000$。

题目解析

看这篇题解吧

	string str1,str2;
	cin>>str1>>str2;
	int n=str1.length();
	int ans=0;
	int r=0;
	for(int i=0;i<n;i++){
		if(str1[i]=='#'||str2[i]=='#'){
			r=i;//这个可以筛掉这种情况
      //#.....
      //#.....
		}
	}
	for(int i=0;i<r;i++){
		if(str1[i]=='#'&&str2[i]=='.'){
			if(str1[i+1]=='.'){
				str1[i+1]='#';
				ans++;
			}
		}
		if(str1[i]=='.'&&str2[i]=='#'){
			if(str2[i+1]=='.'){
				str2[i+1]='#';
				ans++;
			}
		}
		if(str1[i+1]=='.'&&str2[i+1]=='.'&&str1[i]=='#'&&str2[i]=='#'){
			for(int j=i+1;j<=r;j++){
				if(str1[j]=='#'){
					str1[i+1]='#';
					ans++;
					break;
				}
				if(str2[j]=='#'){
					str2[i+1]='#';
					ans++; 
					break;
				}
			}
		}
	}
	cout<<ans<<endl;;