第 30 场 蓝桥·算法入门赛 题解

1. 零食争议【算法赛】

签到题：1-7奇数相加

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<1+3+5+7;
  return 0;
}

2. 数字炸弹【算法赛】

把n个人看为前n-1和后n-1 ， 方便找到是第几段的第几个数

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int n,m;
  cin>>n>>m;

    int z = m/(n-1);
    int k = m%(n-1);
    if(z % 2 == 0){
        cout<<k<<endl;
    }
    else{
        cout<<n-k+1<<endl;
    }

  return 0;
}

3. 巴士接乘【算法赛】

n个点都要经过，两点都有距离，那最短距离就是不走两点间最长边

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
  // 请在此输入您的代码
  int n,m;
  cin>>n>>m;

  vector<int> a(n);
  for(int i=0;i<n;i++){
      cin>>a[i];
  }

  sort(a.begin(),a.end());
  
  int ans1 = 0;
  int ma = 0;
  for(int i=0;i<n-1;i++){
      ans1 += (a[i+1] - a[i]);
      ma = max(ma , (a[i+1] - a[i]));
  }
  ma = max(ma , m - a[n-1] + a[0]);
  ans1 += m - a[n-1] + a[0];
  ans1 -= ma;
  cout<<ans1<<endl;

  return 0;
}

4. 旅行攻略【算法赛】

必须要改一次“QQ" , 如果本来是”QQ" , 记录出现过 ， 最后+1

但是出现“QL" 改为 ”QQ" 记录一次+1 ， 如果下一个“LQ" 就会再次记录 ， 所以”QLQ“跳过

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
  // 请在此输入您的代码
  string s;
  cin>>s;
  int n = s.size();
  int ans = 0;
  bool flag = false;
  for(int i=0;i<n-1;i++){
      if(i > 0 && s[i-1] == 'Q' && s[i] == 'L' && s[i+1] == 'Q'){
          continue;
      }
      if(s[i] == 'Q' && s[i+1] == 'Q'){
          flag = true;
          continue;
      }
      else{
          ans++;
      }
  }

  if(flag)ans++;
  cout<<ans<<endl;
  return 0;
}

5. 魔王挑战【算法赛】

贪心：越大的数需要最小的个数

        大到小排序 ， 如果当前x可以 以x为最小值的一组 就ans++ 

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
  // 请在此输入您的代码
  
  //贪心从大到小
  int n,k;
  cin>>n>>k;

  vector<int> a(n,0);
  for(int i=0;i<n;i++){
      cin>>a[i];
  }

  sort(a.rbegin() , a.rend());

  int cur = 0;
  int ans = 0;
  for(int i=0;i<n;i++){
      int z = (k+a[i]-1) / a[i];
      z--;
      if(z <= cur){
          ans++;
          cur -= z;
      }
      else{
          cur++;
      }
  }

  cout<<ans<<endl;

  return 0;
}

6. 暑假日记【算法赛】

容斥定理 + 二分

二分枚举需要到达第几天，才能够k个

只有公倍数时才会重复，所以容斥 (x + y + z) - (xy + xz + yz) + (xyz)

#include <bits/stdc++.h>
using namespace std;
#define int long long

int lcm(int a,int b)
{
    return a/__gcd(a,b)*b;
}

bool check(int x,int y,int z,int k,int f)
{
    int ans = 0;
    ans += f / x + f / y + f / z;
    ans -= f / lcm(x , y) + f / lcm(y , z) + f / lcm(x , z);
    ans += f / lcm(x , lcm(y , z));

    return ans >= k;
}

signed main()
{
  // 请在此输入您的代码
  int T;
  cin>>T;
  while(T--){
       //容斥+二分
       int x,y,z,k;
       cin>>x>>y>>z>>k;

        int l = 1 , r = 1e18;   //枚举范围
        int ans = 0;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(check(x,y,z,k,mid)){
                ans = mid;
                r = mid-1;
            }
            else{
                l = mid+1;
            }
        }

        cout<<ans<<endl;
  }
  
  return 0;
}