每周算法比赛
比赛链接:第 21 场 小白入门赛 - 蓝桥云课
1.动态密码
#include <iostream>
using namespace std;
int main()
{char result[10010];cout<<itoa(20241111,result,2)<<endl;return 0;
}
2.购物车的宝贝
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[100010];
int main()
{cin>>n;for(int i=0; i<n; i++){cin>>a[i];}int sum=a[0]; for(int i=1; i<n; i++){sum^=a[i];}if(sum==0){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}return 0;
}
3.代金券
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,num;
int main()
{cin>>t;while(t--){ll n,m;cin>>n>>m;string temp=to_string(n);ll min_num=LLONG_MAX;for(int i=0;i<=temp.size();i++){for(int j=0;j<=9;j++){string new_temp=temp;new_temp.insert(i,to_string(j));num=stoll(new_temp);if(num>n && (num%m==0)){min_num=min(min_num,num);}}}if(min_num==num){cout<<-1<<endl;}else{cout<<min_num<<endl;}}return 0;
}
4.蓝桥商场
// 贪心最优策略:交替吃食物,当食物最多的超过其他之和,此时会等待浪费时间
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,sum=0;
int a[100010];
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}sort(a,a+n);cout<<max(sum,2*a[n-1]-1)<<endl;return 0;
}
5.蓝桥派对
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<int,int>num;
vector<num>nums;
int main()
{cin>>n>>m;int a[n],b[n];for(int i=0;i<n;i++){cin>>a[i]>>b[i];nums.emplace_back(a[i],b[i]);}sort(a,a+n);sort(b,b+n);int f[n];for(int i=0;i<n;i++){int l=nums[i].first; //开始点 int r=nums[i].second; //结束点 int front=upper_bound(a,a+n,r)-a; //在结束点之前开始的所有人int end=lower_bound(b,b+n,l)-b; //在开始点之前结束的所有人f[i]=front-end-1; //所有开始-所有结束=区间内的交朋友个数 }for(auto x:f){cout<<x<<endl;}return 0;
}
6.薅羊毛
//相邻数最小公倍数就是相邻数相乘(没有公因子)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll l,r,sum=0;
ll qmi(ll b,ll q,ll k)
{ll res=1;while(q){if(q&1) res=res*b%k;q>>=1;b=b*b%k;}return res;
}int main()
{cin>>l>>r;for(int i=l;i<r;i++){sum=(sum+qmi(i,i,mod)*qmi(i+1,i+1,mod)%mod)%mod; }cout<<sum<<endl;return 0;
}
7.小H学语文
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll h[200010];
typedef pair<int,int>num;
vector<num>nums;
int main()
{cin>>n;for(int i=0; i<n; i++){cin>>h[i];nums.push_back({i+1,h[i]});}//算出最大(从数组h[]中选择x个数,x的平方乘以x个数的最小值)sort(nums.begin(), nums.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.second < b.second; // 按高度升序排序});ll max1=0,sum1=0; //最大体积,木板数vector<int>index; //索引for(int i=1; i<=n; i++){int result = i*i*nums[n-i].second; //从排序的尾部选木板数量,nums从0开始if(result>max1){max1=result;sum1=i;}}cout<<sum1<<endl;for(int j=n-sum1; j<n; j++){index.push_back(nums[j].first);}sort(index.begin(),index.end());for(int t:index){cout<<t<<" ";}return 0;
}
总结知识点:
1.itoa()函数用法
2. ^位运算
3.字符串插入insert(i,to_string(j)),stoll()函数用法,LLONG_MAX
4.nums.emplace_back(),upper_bound()和lower_bound()二分用法
5.快速幂
6.新的排序方法:
sort(nums.begin(), nums.end(), [](const pair<int, int> &a, const pair<int, int> &b)
{
return a.second < b.second; /
});