第 29 场 蓝桥·算法入门赛

1. 不油腻的星座

"我们只欢迎不油腻的星座！"
在「非哺乳动物星座联盟」的派对上，主持人突然宣布："请在场的 12 星座中，名字里包含哺乳动物的立刻离场"，结果白羊、金牛、狮子、摩羯 44 个星座红着脸拖着行李箱走了。
现在，请问还有多少星座留在现场？

#include <iostream>
using namespace std;
int main(){
  cout<<12-4;
  return 0;
}

 2. 守护神开会

白羊座、金牛座和双子座的守护神正在一条直线上开会。起初，他们分别位于坐标 A、B 和 C 三个不同的位置上。由于他们说话声音都很小，为了能彼此听得更清楚，每次，最外侧（位置坐标最大或最小）的一位守护神要移动到另外两位守护神之间的空隙处，以便他们三靠得更近。

对此，请你算算，他们最多可以进行多少次这样的移动？注意，他们的位置需始终保持不同。

解题思路：把最小值和最小值放到另外两个数直接即可 

#include <iostream>
using namespace std;
int main(){
  int t; cin>>t; int mx=-1;
  while(t--){
    int a,b,c; cin>>a>>b>>c;
    mx=max(abs(a-b),abs(b-c));
    cout<<mx-1<<endl;
  }
  return 0;
}

3. 守护射手座 

 射手星座正遭受来自外星系的攻击！星座中有 N 户居民排成一条直线，第 i 户居民有 Ai​ 人。只有当某户居民人数不少于 M 时，该户才能形成防护罩抵御攻击。
国王可以进行迁移操作：每次选择某一户的所有居民，将他们整体迁移到相邻的左边或右边住户。由于每次迁移都会消耗大量资源，请计算最少需要多少次迁移，才能使所有住户都形成防御罩低于攻击。
如果无论如何都无法实现，输出 −1。
注意：两户居民合并后为一户，不会存在一个空的户。

解题思路：当最后sum==0时, 此时恰好cnt个片段, 需要合并n-cnt 次, 否则, 剩最后一段sum,就合并到最后一个片段中, 特殊的如果cnt==0,  说明 total<m

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m; cin>>n>>m; 
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    long long sum=0;
    int cnt=0;
    long long total=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        total+=a[i];
        if(sum>=m){
            cnt++;
            sum=0;
        }
    }
    if(sum==0){
        cout<<n-cnt;
    }else{
        if(cnt>0){
            cout<<n-cnt;
        }else{
            if(total<m) cout<<-1;
        }
    }
    return 0;
}

 4.星座骑士

在一次盛大的十二星座大会上，各星座代表齐聚一堂，共同商议组建一支星座守护军队，以应对可能出现的突发情况。这支军队不仅需要强大的战斗力，还需要有卓越的领导才能。经过严格的选拔，最终从十二星座中挑选出了 N 位星座骑士，他们各自展现出独特的能力值，记为 Ai。

为了确保军队的高效运作，会议决定选出两位星座骑士作为左右统帅。然而，统帅的选择并非随意，而是有着特殊的要求：这两位统帅的能力值之和必须与剩余骑士的能力值之和保持相同的奇偶性。这一规定旨在确保军队在战斗时的稳定性，避免潜在的混乱和冲突。

请你帮忙计算一下最终能选出多少种符合条件的统帅组合。

所有骑士能力值总和为偶数时，任意一对都满足条件 

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    long long sum=0;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        sum+=x;
    } 
    if(sum&1) cout<<0;
    else{
        long long ans=1LL*n*(n-1)/2;
        cout<<ans<<endl;
    }
    return 0;
}

 5.狮子座的试炼

2025 年，在狮子座最明亮的那一夜，草原上将举行一场庄严的仪式： N 头年轻的狮子从左到右排成一行，依次编号为 1 到 N，准备接受试炼。

每只狮子都有一种内在特质：犹豫迟疑（用 0 表示）或自信坚定（用 1 表示）。其中，第 ii 头狮子的特质为 Ai​，取值为 0 或 1。

试炼的核心目标是检验群体是否具备王者的凝聚力。狮子座的王者精神不仅体现在个体的勇气中，更体现在群体的信念共振上。因此，试炼要求：

• 当这群狮子排成一行时，任意连续的、至少包含 2 头狮子的群体中，犹豫迟疑的数量不能超过自信坚定的数量。

为帮助年轻狮子通过试炼，狮子王请来了大祭司。大祭司可施展魔法：将某头狮子的犹豫特质（0）转化为自信特质（1）。 对此，请你计算，最少需要进行多少次魔法，才能使狮群通过试炼。

解题思路：

我们将某些0翻成1视作在最终序列中保留若干 0，其余都翻为1。要求最终序列中不得出现：
连续两个 0("00")，也就是任意两零之间下标差 ≥2。
"0 1 0"的模式，也就是任意两个 0 之间下标差 !=2。
综上等价于：任意两保留下来的"0"在下标上至少间隔 3，其余位置全部变成1即可。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n; cin>>n;
    vector<int> a;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        a.push_back(x);
    }
    vector<int> b;
    for(int i=0;i<n;i++){
        if(a[i]==0) b.push_back(i);
    }
    int k=b.size();
    if(k==0) { cout<<0; return; }
    int cnt=1;
    int pre=b[0];
    for(int i=1;i<k;i++){
        if(b[i]>=pre+3){
            cnt++;
            pre=b[i];
        }
    }
    cout<<k-cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t;
    // cin >> t;
    // while (t--) {
        solve();
    // }
    return 0;
}

 6. 星座解密

在一次盛大的星座大会上，各星座代表聚集在一起，讨论如何管理他们的星座力量。每个星座代表都有一个整数值，代表他们的力量，记为 x。

现在，他们面临一个挑战：需要将 x 转换为 0。可以通过以下两种操作来改变这个整数：

1. 将 x 增加 1（即 x+1）。
2. 将 x 改为 x&(x+1)（按位与操作）。

星座代表们希望找到将 x 转换为 0 所需的最小操作次数，请你帮助他们计算。

解题思路：二进制数不全为1的时候, & 就数就会变大, 所以, 先x累加成全为1, 然后 & (x+1)

结果就为0了 

#include <bits/stdc++.h>
using namespace std;
bool solve(int x){
  while(x>0){
    if(x%2==0) return false;
    x/=2;
  }
  return true;
}
int main(){
  int x;
  cin>>x;
  int ans=0;
  while(!solve(x)){ x++; ans++; }
  cout <<ans+1<< endl;
  return 0;
}

 感谢大家的点赞和关注，你们的支持是我创作的动力！(其他细节，有时间再补充...)