蓝桥首场算法团队战 2024.10.24 题解
1:不同角度【算法赛】
题意：
给定自然数 S ，需要找出一个自然数 T。
使得数字 T > 数字 S 并且 S 和 T 转化为字符串后，满足 S 的字典序> T 的字典序。
T 一定存在，找出符合条件且字典序最小的 T。
输入：
第一行一个整数 t ，表示 t 组测试用例。\((t \leq 10^{3})\)
接下来 t 行，每行包含一个自然数 S。\((S \leq 10^{9})\)
输出：
每个测试样例输出一个整数。表示满足条件的自然数 T。
样例输入：
2
99
999
样例输出：
990
9990
分析：
对于一个整数 S ，需要满足数字 T > 数字 S，我们不妨考虑两种情况。
- |T| = |S|
- |T| > |S|
对于情况1而言，我们生成的 T 一定是 数字 S + 1。
而对于情况2而言，我们生成的 T 应该是 数字 S \(\ast\) 10，即末尾补0。
对比这样两种情况下的 T ，我们容易得出，第二种字典序明显小于第一种，故我们策略应该是末尾补0。
但是，由刚刚情况2的分析，我们可以看出，如果 S = 0；那么得到的 T 为 00，并不满足数字 T > 数字 S 的条件，
此时应该特判一下 0 的情况，发现，如果输入是 0 ，我们输出 1，即可保证符合题意。
综上：我们的策略应该是是 0 变 1 ，非 0 补 0即可。
ac 代码：
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
string s;
cin>>s;
if(s=="0")cout<<1<<endl;
else {
s+='0';
cout<<s<<endl;
}
}
return 0;
}
2:摆放显示器【算法赛】
题意：
给定长 N 宽 M 的桌子，在其中放入边长为 K 的正方形显示屏，求解满足以下条件下，放入的最大值。
- 放入的显示屏不重合。
- 放入的显示屏不越界。
- 放入的显示屏必须至少有一条边与桌边紧贴。
输入：
第一行一个整数 t ，表示 t 组测试用例。\((1 \leq t \leq 10^{3})\)
接下来 t 行，每行三个数 N，M，K，分别表示桌面的长、宽以及显示屏的边长。\((1 \leq N,M,K \leq 10^{9})\)
样例输入：
2
1 1 1
3 3 2
样例输出：
1
1
分析：
对于不重合和不越界的条件比较好判定，最多就是\(\lfloor\)\(\frac{n}{k}\)\(\rfloor\) \(\ast\) \(\lfloor\)\(\frac{m}{k}\)\(\rfloor\)种情况。
但是我们需要考虑到至少有一条边与桌边紧贴这种情况，也就是说，中间没有与桌边紧贴的部分需要减掉。
很容易得到，当 n \(\geq\) 3\(\ast\)k 并且 m \(\geq\) 3\(\ast\)k 时，他就需要减去中间部分，中间部分即为\(\lfloor\)\(\frac{n}{k}\)-2\(\rfloor\) \(\ast\) \(\lfloor\)\(\frac{m}{k}\)-2\(\rfloor\)
按照思路写出代码即可。
ac 代码：
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
long long n,m,k;
cin>>n>>m>>k;
long long n_=n/k,m_=m/k;
long long ans=n_*m_;
if(n>=3*k&&m>=3*k){
ans-=((n-2*k)/k)*((m-2*k)/k);
}
cout<<ans<<"\n";
}
return 0;
}
3:整数对F1【算法赛】
题意：
给定一个长度为N的数列\(A_x + A_1 + A_2 + \ldots + A_N\)。
对于一对整数\(\{x,y \}\) \((x \leq y)\),定义公式
$F1(x,y) = \sum_{k = x}^y{A_k} = A_x + A_{x+1} + A_{x+2} + \ldots + A_y$
接下来对所有满足$1 \leq l \leq r \leq N$的整数对$\{l,r \}$,求出$F1(l,r)$的总和。输入：
第一行一个整数N,表示数组长度。\((1 \leq N \leq 10^{5})\)
第二行N个整数\(A_x + A_1 + A_2 + \ldots + A_N\)。\((10^{-5} \leq A_i \leq 10^{5})\)
输出：
一个整数，表示\(F1(l,r)\)的总和
样例输入：
2
1 2
样例输出：
6
分析：
我们发现，对于第\(i\)个\((\)下标从\(0\)开始\()\)位置的数而言，它以及它前面的数字个数为\(i+1\)，它后面的数字个数\(n-i+1\)
那么它累加的次数是\((i+1) \ast (n-i+1)\)
所以可以得到公式
$sum = \sum_{i = 1}^N{A_i \ast (i+1) \ast (n-i+1)} $
ac 代码：
#include <iostream>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
signed main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int ans=0;
for(int i=0;i<n;i++){
ans+=a[i]* (i + 1) * (n - i);
}
cout<<ans<<endl;
return 0;
}
4:小学生的账号密码【算法赛】
题意：
给定\(n\)个数字\(a_1,a_2,a_3,\ldots,a_n\)和\(q\)次操作。
每次操作给定一个数\(k\)，然后需要将\(a_1,a_2,a_3,\ldots ,a_n\)中。下标\(i\)是\(k\)的倍数的元素\(a_i\)修改为\(F(a_i)\)。
其中，$F(a_i) = a_i \ast 10 mod 24 $。
输入：
第一行两个整数\(n,q\),表示数组大小与操作次数。\((1 \leq n,q \leq 3 \ast 10^{5})\)
第二行\(n\)个整数\(a_1,a_2,a_3,\ldots,a_n\)。\((1 \leq a_i \leq 10^{9})\)
接下来q行，每行包括一个整数\(k\)。\((1 \leq a_i \leq n)\)
输出：
一行共\(n\)个整数，表示\(q\)次操作结束后的\(a_1,a_2,a_3,\ldots,a_n\)。
样例输入：
5 2
1 2 3 4 5
1
2
样例输出：
10 8 6 16 2
分析：
对于这个问题，我们可以分析得到枚举每一个位置，然后再找出其因子，操作。
这种情况下不考虑操作的次数，时间复杂度是\(O(n^{1.5})\)。
再加上操作，时间复杂度就达到了\(O(q)+O(n^{1.5})=O(n^{2.5})\)。
此时一定会TLE。
那么我们需要优化一下操作的步骤，是否存在可以提前退出操作等的优化办法。
分析函数\(F(a_i) = a_i \ast 10 mod 24\)，我们发现,有几个特殊点，
当\(a_i=0\)的时候\(F(0) = 0 mod 24 = 0\)
当\(a_i=8\)的时候\(F(8) = 80 mod 24 = 8\)
当\(a_i=16\)的时候\(F(16) = 160 mod 24 = 16\)
也就是说，这三个点，不管操不操作都无法变动了，这是类似于剪枝的优化算法，提前判断结束位置，减少操作次数。
这样时间复杂度就降低下来了\(\approx O(n^{1.5})\)。
ac 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int a[N],cnt[N];
int n,q,t;
void opera(int u,int n){
for (int i=0;i<n;i++){
if(a[u]==16||a[u]==8||a[u]==0) break;
a[u]=a[u]*10%24;
}
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<q;i++) {
cin>>t;
++cnt[t];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i/j;j++){
if(i%j==0){
opera(i,cnt[j]);
if(j*j!=i) opera(i,cnt[i/j]);
}
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
5:整数对F2【算法赛】
题意：
给定一个长度为N的数列\(A_x + A_1 + A_2 + \ldots + A_N\)。
对于一对整数\(\{x,y \}\) \((x \leq y)\),定义公式
$F2(x,y) = \sum_{k = x}^y{(-1)^{k-x} \ast A_k} = A_x - A_{x+1} + A_{x+2} - A_{x+3} + \ldots$
接下来对所有满足$1 \leq l \leq r \leq N$的整数对$\{l,r \}$,求出$F2(l,r)$的总和。输入：
第一行一个整数N,表示数组长度。\((1 \leq N \leq 10^{5})\)
第二行N个整数\(A_x + A_1 + A_2 + \ldots + A_N\)。\((10^{-5} \leq A_i \leq 10^{5})\)
输出：
一个整数，表示\(F2(l,r)\)的总和
样例输入：
2
1 2
样例输出：
2
分析：
对于第\(i\)位\((\)下标从\(1\)开始\()\)的数，我们考虑其奇偶。
先考虑第\(i\)位以前的数字对第\(i\)位的影响：
- 如果是偶数位，那么它在前面被计算了\((i-1) \ast (n-i+1)\)次。
其中正号有\(\lfloor \frac{i-1}{2} \rfloor \ast (n-i+1)\)次
负数有\(\lceil \frac{i-1}{2} \rceil \ast (n-i+1)\)次
也就是\(-(n-i+1)\)次。 - 如果是奇数位，那么它在前面也被计算了\((i-1) \ast (n-i+1)\)次。
因为\(i\)是奇数，所以\(\lceil \frac{i-1}{2} \rceil == \lfloor \frac{i-1}{2} \rfloor\)
也就是正负对半。
其中正号有\(\frac{i-1}{2} \ast (n-i+1)\)次
负数有\(\frac{i-1}{2} \ast (n-i+1)\)次
也就是\(0\)次。
再考虑第\(i\)位及以后的位置，可以看出，后续影响主要在于\(i\)==\(l\),也就是函数以第\(i\)位为左端点，此时一共累加\(n-i+1\)次。
综上:
如果是偶数位那么最后累加次数就是\(-(n-i+1)+(n-i+1) \Longrightarrow 0\)。
如果是奇数位那么最后累加次数就是\(0+(n-i+1) \Longrightarrow n-i+1\)。
综上得到：
$sum = \sum_{i = 1}^n{A_i \ast (i mod 2) \ast (n-i+1)} $
ac 代码：
#include <iostream>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++){
if(i%2)ans+=a[i]*(n - i+1);
}
cout<<ans<<endl;
return 0;
}