A.小红的签到题
题意
已知改版的小白月赛一共有a道题，一共有b人参赛，所有人通过题目数量的总数为c道。问最多有多少人ak？
思路
签到题目，直接c/a就行了
代码
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=110;
typedef long long LL;
int main()
{
IOS;
int a,b,c;
cin>>a>>b>>c;
cout<<c/a<<endl;
return 0;
}
B.小红的ABC
题意
小红拿到了一个只包含 'a' , 'b' , 'c' 三种字符的字符串。
小红想知道，这个字符串最短的、长度超过 1 的回文子串的长度是多少？
思路
最短的长度超过1的回文子串只有三种可能，不存在，2或3，所以直接遍历便可以得出答案。
代码
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=110;
typedef long long LL;
string s;
int main()
{
cin>>s;
int i=0,j=1;
int flag=false,flag1=false; //是否出现了2和3的情况
for(int i=0;i<s.length();i++)
{
if(s[i]==s[i+1])
flag=true;
if(s[i]==s[i+2])
flag1=true;
}
if(flag)
cout<<2<<endl;
else if(flag1)
cout<<3<<endl;
else
cout<<-1<<endl;
return 0;
}
C.小红的口罩
题意
小红网购了n个口罩。
众所周知，戴口罩是很不舒服的。小红每个口罩戴一天的初始不舒适度为ai
小红有时候会将口罩重复使用（注：这是非常不卫生的！），每次重复使用时，该口罩的不舒适度会翻倍
小红想知道，自己在不舒适度总和不超过k的情况下，最多能用现有的口罩度过多少天？
思路
每次都选择舒适度最小的口罩戴上，之后将其舒适度翻倍重新排序，很明显我们可以用小根堆来解决这个问题。
代码
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=1e5+10;
priority_queue<int ,vector<int> ,greater<int> >q;
typedef long long LL;
LL a[N];
int cnt;
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){ //输入数据
int x;
cin>>x;
q.push(x);
}
while(k>=0)
{
int x=q.top();
if(k>=x)
{
k-=x;
x*=2; //舒适度加倍后重新入队
q.pop();
q.push(x);
cnt++;
}
else
break;
}
cout<<cnt<<endl;
return 0;
}
D.小红的数组
题意
小红拿到了一个长度为 n的数组，数组中的元素都是正整数。
小红想让你回答以下三个问题，取两个数乘积大于k的方案数、取两个数乘积等于k的方案数、取两个数乘积小于k的方案数。
思路
二分
排序后遍历数组有三种情况：
1.如果a[i]*a[i+1]>k，那么从i+1~n有n-i-1个数乘a[i]都会>k。
2.如果a[i]*a[n]<k,那么从i+1~n也有n-i-1个数乘a[i]也会<k。
3.如果a[i]*a[i+1]=k 或者 a[i]*a[n]=k,首先我们要二分查找出左边界L为>=k/a[i]的第一个数和右边界R为>k/a[i],其中我们又要分两种情况来判断:
- a :如果k%a[i]=0：
那么从i-1~L的数乘上a[i]<k, L~R的数乘上a[i]=k,R~n的数乘上a[i]>k - b :如果k%a[i]！=0：
那么就不会存在等于k的情况,所以有R~n个数乘a[i]＞k,i-1~R个数乘a[i]<k
代码
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=3e5+10;
typedef long long LL;
LL n,k;
LL a[N];
LL k1,k2,k3;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int i=0;i<n-1;i++)
{
if(a[i]*a[i+1]>k) k1+=n-i-1;
else if(a[i]*a[n-1]<k) k3+=n-i-1;
else {
int p=lower_bound(a+i+1,a+n,k/a[i])-a;
int q=upper_bound(a+i+1,a+n,k/a[i])-a;
if(k%a[i]!=0)
{
k1+=n-q;
k3+=q-i-1;
}
else
{
k3+=p-i-1;
k1+=n-q;
k2+=q-p;
}
}
}
cout<<k1<<' '<<k2<<' '<<k3<<endl;
return 0;
}
QAQ~ 困了睡觉咯