说明/背景
此文仅为作者的个人见解，原题为第十六届蓝桥杯省赛c++b组原题。可以在以下链接找到对应的评测：https://www.luogu.com.cn/problem/list?tag=363%7C62&page=1
难度评级参照洛谷评测
1.移动距离 普及/提高-
题目描述
- 小明初始在二维平面的原点，他想前往坐标 (233,666)。在移动过程中，他只能采用以下两种移动方式，并且这两种移动方式可以交替、不限次数地使用：1.水平向右移动，即沿着 x 轴正方向移动一定的距离。
2.沿着一个圆心在原点 (0,0)、以他当前位置到原点的距离为半径的圆的圆周移动，移动方向不限（即顺时针或逆时针移动不限）。
在这种条件下，他到达目的地最少移动多少单位距离？你只需要输出答案四舍五入到整数的结果。 - 输入格式：无。
- 输出格式：直接填写答案。
示例
- 无。
思路
- 思维题。只能选择两种方式，且可以无限次数使用。经过思考之后可以知道，无捷径可走，只能按照类似于先向右边走d ， 再以O为圆心d为半径的圆弧走到目的地。
计算过程涉及到高数的知识，可以直接使用cpp自带的库函数解决。时间复杂度O(1).
代码
void solve()
{
double r = sqrt(233 * 233 + 666 * 666);
int ans = r + asin(666.0 / r) * r;
cout << ans << endl;
return ;
}
2.客流量上限 普及+/提高
题目描述
- 一家连锁旅馆在全国拥有 2025 个分店，分别编号为 1 至 2025。随着节日临近，总部决定为每家分店设定每日客流量的上限，分别记作 A_1, A_2, …, A_2025。这些上限并非随意分配，而是需要满足以下约束条件：1. A_1, A_2, …, A_2025 必须是 1 至 2025 的一个排列，即每个 A_i 均是 1 至 2025 之间的整数，且所有 A_i 互不相同。
2. 对于任意分店 i 和 j（1 ≤ i, j ≤ 2025，i 可等于 j），它们的客流量上限 A_i 和 A_j 的乘积不得超过 i × j + 2025。这些约束旨在平衡各分店客流压力，确保服务质量和运营稳定性。现在，请你计算这样的分配方案究竟有多少种。由于答案可能很大，你只需输出其对 10^9 + 7 取余后的结果即可。 - 输入格式：无
- 输出格式：填入一个整数即可。
示例
- 无。
思路
- 思维题，排列组合。根据题意当i == j时，即为Ai² <= (i ² + 2025) , 经过推理运算，可知当 就会把 都占用完，所以 只能等于 ， 只能等于
- 可以使用快速幂进行时间优化。时间复杂度O(logn)。
代码
const int mod = 1e9 + 7;
inline int qmi(int a , int n)
{
int res = 1;
while (n)
{
if (n & 1) res = a * res % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
void solve()
{
cout << qmi(2 , 1012) << endl;
return ;
}
3.可分解的正整数 普及-
题目描述
- 定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件：1. 序列长度至少为 3。
2. 序列中的数字是连续递增的整数（即相邻元素之差为 1），可以包括正整数、负整数或 0。例如：
- [1,2,3]、[4,5,6,7] 和 [−1,0,1] 是符合条件的序列。
- [1,2]（长度不足）和 [1,2,4]（不连续）不符合要求。现给定一组包含 N 个正整数的数据 A_1, A_2, ..., A_N。如果某个 A_i 能够表示为符合上述条件的连续整数序列中所有元素的和，则称 A_i 是可分解的。请你统计这组数据中可分解的正整数的数量。 - 输入格式：输入的第一行包含一个正整数 N，表示数据的个数。
第二行包含 N 个正整数 A_1, A_2, ..., A_N，表示需要判断是否可分解的正整数序列。 - 输出格式：输出一个整数，表示给定数据中可分解的正整数的数量。
示例
- 输入：
3
3 6 15 - 输出：
3 - 说明：
- A_i = 3 是可分解的，因为 [0,1,2] 的和为 0+1+2=3。
- A_i = 6 是可分解的，因为 [1,2,3] 的和为 1+2+3=6。
- A_i = 15 是可分解的，因为 [4,5,6] 的和为 4+5+6=15。
所以可分解的正整数的数量为 3。 - 数据：
- 对于 30% 的评测用例，1 ≤ N ≤ 100，1 ≤ A_i ≤ 100。
- 对于 100% 的评测用例，1 ≤ N ≤ 10^5，1 ≤ A_i ≤ 10^9。
思路
- 思维题。通过大量的数据可以知道，除了1以外，其他的数字均为可分解的正整数。时间复杂度O(n)
代码
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
int ans = 0;
for (int i = 1 ; i <= n ; i ++ ) if (a[i] != 1) ans ++;
cout << ans << endl;
return ;
}
4.产值调整 普及-
题目描述
- 偏远的小镇上，三兄弟共同经营着一家小型矿业公司“兄弟矿业”。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数 A、B 和 C 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的生计。然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时，将根据当前的产值 A、B、C，计算新产值：- 金矿新产值：A' = ⌊(B + C) / 2⌋
- 银矿新产值：B' = ⌊(A + C) / 2⌋
- 铜矿新产值：C' = ⌊(A + B) / 2⌋其中，⌊⌋ 表示向下取整。例如，⌊3.7⌋ = 3，⌊5.2⌋ = 5。计算出 A'、B'、C' 后，同时更新：A 变为 A'，B 变为 B'，C 变为 C'，作为下一年调整的基础。三兄弟认为这个方法能平衡产值波动，于是计划连续执行 K 次调整。现在，请你帮他们计算，经过 K 次调整后，金矿、银矿和铜矿的产值分别是多少。 - 输入格式：输入的第一行包含一个整数 T，表示测试用例的数量。
接下来的 T 行，每行包含四个整数 A, B, C, K，分别表示金矿、银矿和铜矿的初始产值，以及需要执行的调整次数。 - 输出格式：对于每个测试用例，输出一行，包含三个整数，表示经过 K 次调整后金矿、银矿和铜矿的产值，用空格分隔。
示例
- 输入：
2
10 20 30 1
5 5 5 3 - 输出：
25 20 15
5 5 5 - 数据限制：
评测用例规模与约定：
- 对于 30% 的评测用例，1 ≤ T ≤ 100，1 ≤ A, B, C, K ≤ 10^5。
- 对于 100% 的评测用例，1 ≤ T ≤ 10^5，1 ≤ A, B, C, K ≤ 10^9。
思路
- 细节题。在每次修改数据的时候，都进行一次检测。当a == b == c 的时候，就进行break操作。通过一些数据的列举可以知道，在经过一定次数的操作之后，abc总有相互靠近并且相等的趋势。
代码
void solve()
{
int a , b , c , k;
cin >> a >> b >> c >> k;
while (k -- )
{
int aa = (b + c) >> 1;
int bb = (a + c) >> 1;
int cc = (a + b) >> 1;
a = aa , b = bb , c = cc;
if (a == b && b == c) break;
}
cout << a << " " << b << " " << c << endl;
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
cin >> T;
while (T -- ) solve();
return 0;
}
5.画展布置 普及-
题目描述
- 画展策展人小蓝和助理小桥为即将举办的画展准备了 N 幅画作，其艺术价值分别为 A1,A2,…,AN。他们需要从这 N 幅画中挑选 M 幅，并按照一定顺序布置在展厅的 M 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于突兀，导致观众的观展体验不够流畅。
为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 M 幅画，应使艺术价值的变化程度通过一个数值 L 来衡量，且该值越小越好。数值 L 的定义为：
L = Σ(i=1到M-1) |B(i+1)^2 - B(i)^2|
其中 B(i) 表示展厅第 i 个位置上画作的艺术价值。
现在，他们希望通过精心挑选和排列这 M 幅画作，使 L 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。 - 输入格式
输入共两行。
第一行包含两个正整数 N 和 M，分别表示画作的总数和需要挑选的画作数量。
第二行包含 N 个正整数 A1,A2,…,AN，表示每幅画作的艺术价值。 - 输出格式
输出一个整数，表示 L 的最小值。
示例
- 输入：
4 2
1 5 2 4 - 输出：
3 - 说明：
评测用例规模与约定
对于 40% 的评测用例，2≤M≤N≤10^3，1≤Ai≤10^3。
对于 100% 的评测用例，2≤M≤N≤10^5，1≤Ai≤10^5。
思路
- 贪心。要使得|Ai+1² - Ai²| 累加最小 即|Ai+1 - Ai|越小。满足此条件的唯一方案按照从大到小或者从小到大的排序方式，进行O(nm) 暴力模拟即可得出答案。
但是时间不允许。把|Ai+1² - Ai²|拆开，可以发现，如果按照从小到大排序的话，Ai+1 始终大于Ai。所以可以去掉绝对值，将相反的数抵消之后就可以得出每一次O(m) 都可以变成(Ai+m-1² - ai²)。如此 就可以将总的时间复杂度优化为O(n).
代码
void solve()
{
int n , m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
sort(all(a));
int ans = INF;
for (int i = 1 ; i + m - 1 <= n ; i ++ )
{
ans = min(ans , a[i + m - 1] * a[i + m - 1] - a[i] * a[i]);
}
cout << ans << endl;
return ;
}
6.水质检测 普及/提高-
题目描述
- 小明需要在一条 2×n 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 A 和 B 连通，B 和 C 连通，那么 A 和 C 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？
- 输入格式：
输入共两行，表示一个 2×n 的河床。
每行一个长度为 n 的字符串，仅包含 '#' 和 '.' ，其中 '#' 表示已经存在的检测器，'.' 表示空白。 - 输出格式：输出共 1 行，一个整数表示答案。
示例
- 输入：
.##. . ...#
.#.#.#.. . - 输出：5
- 说明：
其中一种方案：
.### . . . . #
.#. ######
增加了 5 个检测器。 - 评测用例规模与约定：对于 100% 的评测用例，保证 n≤1000000。
思路
- 贪心加分类讨论。分别用a , b 代表第一行，第二行的分布情况。分为三种情况：
1.a[i] == '#' && b[i] == '#' 此时其和任意一个连通块的距离都是相同的。为index - i - 1.
2.a[i] == '#' && b[i] == '.' 此时若a[i+index] == '#' 则距离为 index - i - 1.
3.a[i] == '.' && b[i] == '#' 此时若b[i+index] == '#' 则距离为index - i - 1.
再进行一些特判优化，最后时间复杂度为O(n)。
代码
void solve()
{
string a , b;
cin >> a >> b;
int n = a.size();
a = " " + a , b = " " + b;
int ans = 0;
for (int i = 1 ; i <= n ; i ++ )
{
if (a[i] == '#' && b[i] == '#')
{
if (a[i + 1] == '#' || b[i + 1] == '#') continue;
for (int j = i + 1 ; j <= n ; j ++ )
{
if ((a[j] == '.' && b[j] == '#')
|| (a[j] == '#' && b[j] == '.')
|| (a[j] == '#' && b[j] == '#'))
{
ans += j - i - 1;
i = j - 1;
break;
}
}
}
if (a[i] == '#' && b[i] == '.')
{
if (a[i + 1] == '#') continue;
for (int j = i + 1 ; j <= n ; j ++ )
{
if ((a[j] == '#' && b[j] == '.')
|| (a[j] == '#' && b[j] == '#'))
{
ans += j - i - 1;
i = j - 1;
break;
}
if (a[j] == '.' && b[j] == '#')
{
ans += j - i;
i = j - 1;
a[j] = b[j] = '#';
break;
}
}
}
if (a[i] == '.' && b[i] == '#')
{
if (b[i + 1] == '#') continue;
for (int j = i + 1 ; j <= n ; j ++ )
{
if ((a[j] == '.' && b[j] == '#')
|| (a[j] == '#' && b[j] == '#'))
{
ans += j - i - 1;
i = j - 1;
break;
}
if (a[j] == '#' && b[j] == '.')
{
ans += j - i;
i = j - 1;
a[j] = b[j] = '#';
break;
}
}
}
}
cout << ans << endl;
}
7.生产车间 普及+/提高
题目描述
- 小明正在改造一个生产车间的生产流水线。这个车间共有 n 台设备，构成以 1 为根结点的一棵树，结点 i 有权值 w i 。其中叶节点的权值 w i 表示每单位时间将产出 w i 单位的材料并送往父结点，根结点的权值 w i 表示每单位时间内能打包多少单位成品，其他结点的权值 w i 表示每单位时间最多能加工 w i 单位的材料并送往父结点。 由于当前生产线中某些结点存在产能不够的问题导致生产线无法正常运行，即存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限。小明计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结点每单位时间内最多能打包多少单位的成品？
- 输入格式：输入共 n+1 行。 第一行为一个正整数 n。 第二行为 n 个由空格分开的正整数 w 1 ,w 2 ,…,w n 。 后面 n−1 行，每行两个整数表示树上的一条边连接的两个结点。
- 输出格式：输出共一行，一个整数代表答案。
示例
- 输入：
9
9 7 3 7 1 6 2 2 7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
6 9 - 输出：8
- 说明：删掉结点 4、9 后生产线满足条件，根结点 1 每单位时间将打包出 8 单位的成品。
- 规定：
对于 20% 的评测用例，2≤n≤100。
对于 100% 的评测用例，2≤n≤1000，1≤wi ≤1000。
思路
-
- 树上DP。每个叶子节点为产量，都分为选或者不选。则可以 以其父节点为一个背包来进行01背包。
如下图，每个子节点都可以提供自身的价值或是0.
则对于每个节点 u 及其子节点 v ∈ children[u]，状态转移方程为：dp[u][s] = ⋁_{v ∈ children[u]} ( ⋁_{k ∈ a[v]} dp[u][s - k] )。
利用滚动数组优化空间。总时间复杂度O(NW)，空间复杂度O(N+W)。
- 树上DP。每个叶子节点为产量，都分为选或者不选。则可以 以其父节点为一个背包来进行01背包。
代码
const int N = 1010;
vector<vector<int> > g(N , vector<int>() ) , a(N , vector<int>() );
vector<int> w(N , 0);
int dfs(int n, int parent = -1)
{
if (g[n].size() == 1 && n != 1)
{
a[n].push_back(w[n]);
return 1;
}
vector<bool> dp(w[n] + 1, false);
dp[0] = true;
for (int v : g[n])
{
if (v == parent) continue;
if (!a[v].size()) dfs(v, n);
vector<bool> temp = dp;
for (int i = 0 ; i <= w[n] ; i ++ )
{
if (dp[i]) {
for (int val : a[v]) {
if (i + val <= w[n])
temp[i + val] = true;
}
}
}
dp = temp;
}
a[n].clear();
for (int i = 0 ; i <= w[n] ; i ++ )
{
if (dp[i]) a[n].push_back(i);
}
return a[n].size();
}
void solve()
{
int n;
cin >> n;
for (int i = 1 ; i <= n ; i++)
cin >> w[i];
for (int i = 1 ; i < n ; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
int ans = 0;
for (int val : a[1])
ans = max(ans , val);
cout << ans << endl;
}
8.装修报价 普及/提高-
题目描述
- 老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供 N 项装修相关费用 A1,A2,…,AN，系统便会根据这些费用生成最终的报价。
然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。
公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入 +（加法）、−（减法）或 ⊕（异或）运算符，并按照特定优先级规则计算结果：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以及中间过程都不会对外公开。
为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇为吃力，便向你求助。
现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你只需提供其对 10^9 +7 取余后的结果即可。 - 输入格式：
第一行输入一个整数 N，表示装修相关费用的项数。
第二行输入 N 个非负整数 A1,A2,…,AN，表示各项费用。 - 输出格式：输出一个整数，表示所有可能的总和对 10^9 +7 取余后的结果。
示例
- 输入：
3
0 2 5 - 输出：11
- 说明：
对于输入样例中的三个数 A=[0,2,5]，所有可能的运算符组合共有 9 种。计算结果如下：
0⊕2⊕5=7
0⊕2+5=7
0⊕2−5=−3
0+2⊕5=7
0+2+5=7
0+2−5=−3
0−2⊕5=−7
0−2+5=3
0−2−5=−7
所有结果的总和为：
7+7+(−3)+7+7+(−3)+(−7)+3+(−7)=11
11 对 10^9 +7 取余后的值依然为 11，因此，输出结果为 11。 - 数据规模：
对于 30% 的评测用例，1≤N≤13，0≤Ai≤10^3。
对于 60% 的评测用例，1≤N≤10^3，0≤Ai≤10^5。
对于 100% 的评测用例，1≤N≤10^5，0≤Ai≤10^9。
Comments NOTHING