第 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 longsigned 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 longsigned 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 longsigned 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 longint 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;
}