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<<" ";
else
cout<<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 e
sum - ((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;
}
