2025/3/8 第 27 场 蓝桥入门赛 题解

1. 38红包【算法赛】

签到题：  算倍数就行了

#include <bits/stdc++.h>
using namespace std;
int main()
{int ans=0;for(int i=1;i<=2025;i++){if(i % 3 == 0)ans++;else if(i % 8 == 0)ans++;else if(i % 38 == 0)ans++;}cout<<ans<<endl;return 0;
}

2. 祝福语【算法赛】

字典序： 两个字符串  ， 挨个比较字符 ， 如果一个字符大则该字符串字典序大  ， 如果一个字符串比较完了，则长度长的字典序大。

思路：aaa最小   ，  所以统计连续的最长a字串  ， 再多输出1个a(避免是字串）

#include <bits/stdc++.h>
using namespace std;
int main()
{// 请在此输入您的代码string s;cin>>s;int n=s.size();int num=0;  //连续a最大长度int ans=0;for(int i=0;i<n;i++){if(s[i] == 'a' && i == n-1)ans = max(ans , num+1);if(s[i] == 'a')num++;else {ans = max(ans , num);num = 0;}}for(int i=0;i<ans+1;i++){cout<<'a';}return 0;
}

3. 社区服务【算法赛】

思路  ：  前缀数组统计，i左边最近1位置的下标

               后缀数组统计，i右边最近1位置的下标

                再遍历每个点，算最小距离

#include <bits/stdc++.h>
using namespace std;
int main()
{// 请在此输入您的代码int n;cin>>n;string s;cin>>s;vector<int> pre(n,-1);int pos=-1;for(int i=0;i<n;i++){pre[i] = pos;if(s[i] == '1'){pos = i;}}vector<int> back(n,-1);pos=-1;for(int i=n-1;i>=0;i--){back[i] = pos;if(s[i] == '1'){pos = i;}}//   for(int i=0;i<n;i++){
//       cout<<pre[i]<<" ";
//   }
//   cout<<endl;
//    for(int i=0;i<n;i++){
//       cout<<back[i]<<" ";
//   }for(int i=0;i<n;i++){if(s[i] == '0'){int t1=INT_MAX,t2=INT_MAX;if(pre[i] != -1){t1 = i - pre[i];}if(back[i] != -1){t2 = back[i] - i;}if(t1==INT_MAX && t2==INT_MAX)cout<<-1<<" ";elsecout<<min(t1 , t2)<<" ";}}return 0;
}

4. 表演队【算法赛】

思路： 滑动窗口（k个数） ， 排序（越靠近越好） ， 前缀和用于计算窗口滑动时的值转换

        1.求第一个窗口的值 ： 

                a1 a2 a3 a4  （假设k=4)    怎么求两两差值呢？

        规律： a2 - a1        a3 - a1       a4 - a1      a1减3次      a2加1次

                    a3 - a2        a4 - a2                        a2减2次      a3加2次

                    a4 - a3                                            a3减1次      a4加3次

        一个数a[i]        减（后面几个数）个  ， 加（前面几个数）个   a[i]

          2.求滑动窗口  看注释

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;int main()
{// 请在此输入您的代码int n,k;cin>>n>>k;vector<ll> a(n+1,0);for(int i=1;i<=n;i++){cin>>a[i];}//排序sort(a.begin()+1,a.end());//前缀和vector<ll> pre(n+1,0);for(int i=1;i<=n;i++){pre[i] = pre[i-1] + a[i];}//   for(int i=1;i<=n;i++){
//       cout<<pre[i]<<" ";
//   }//滑动窗口//第一个窗口值ll ans = 0;  //上一个窗口值ll res = 0;  //答案for(int i=1;i<=k;i++){ans +=  (i-1) * a[i] - (k-i) * a[i];}res = ans;//   cout<<ans;/*a b c d esum - ((b - a) + (c - a)) + ((d - b) + (d - c));== sum  -(b + c) + 2*a +  2*d - (b + c)== sum -2*(b+c) + 2*a + 2*d*/for(int i=2;i<=n-k+1;i++){ans = ans - 2 * (pre[i+k-2] - pre[i-1]) + (k-1)*a[i-1] + (k-1)*a[i+k-1];res = min(ans , res);}cout<<res<<endl;return 0;
}

5. 花束搭配【算法赛】

思路  Ai + Aj > Bi + Bj      ->     Ai - Bi > - (Aj - Bj)

二分查找即可，但要注意以下几点：

sub[i] <= 0      :   不用考虑自己大于 - sub[i]          

sub[i] > 0        :   考虑自己大于 - sub[i]       答案-1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;int main() {int n;cin >> n;vector<int> a(n);vector<int> b(n);for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}vector<int> sub(n);for (int i = 0; i < n; i++) {sub[i] = a[i] - b[i];}sort(sub.begin(), sub.end());ll ans = 0;for (int i = 0; i < n; i++) {auto it = upper_bound(sub.begin(), sub.end(), -sub[i]);if (it != sub.end()) {int pos = it - sub.begin();// n - pos 个int y = n - pos;if (sub[i] > 0) y--;  //换成负的包括正数自己ans = ans + y;}}cout << ans << endl;return 0;
}

6. 妇女唇膏【算法赛】

思路 ： 找二进制都是0的位  ， 因为这样  相加  和   异或  该位都一样变成1      

#include <bits/stdc++.h>
using namespace std;int main()
{// 请在此输入您的代码int n;cin>>n;vector<int> nums(n,0);for(int i=0;i<n;i++){cin>>nums[i];}vector<bool> flag(32,true);for(int i=0;i<n;i++){int t=nums[i];int pos=0;while(t){if(t%2 == 1)flag[pos] = false;t/=2;pos++;}}for(int i=0;i<32;i++){if(flag[i]){cout<<(1<<i)<<endl;   //不能pow，pow返回浮点数  ， 会有精度问题break;}}//   for(int i=1;i<=10000;i++){
//       bool flag=true;
//       for(int j=0;j<n;j++){
//           if(nums[j] + i != (nums[j] ^ i)){
//               flag=false;
//               break;
//           }
//       }
//       if(flag ){
//           cout<<i<<endl;
//           break;
//       }
//   }return 0;
}