每周算法比赛

比赛链接：第 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; /
    });