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;
}
