A.小红的签到题
知识点：贪心
思路：签到题，由于题目保证了输入合法，所以不需要考虑b,答案为c/a。
时间复杂度：O(1)
参考代码：
#include<iostream>
using namespace std;
int main()
{
int a,b,c;
cin>>a>>b>>c;
cout<<c/a;
return 0;
}
B.小红的ABC
知识点：字符串
思路1：由于题目给的数据范围小，所以直接暴力枚举每一个子串，判断是否为回文串并记录最小长度。
时间复杂度：O(N3)
参考代码1：
#include<iostream>
#include<string>
using namespace std;
//判断是否为回文串，是返回true，不是返回false
bool hw(string &t)
{
int n=t.size();
//从字符串的两端同时遍历，若有不一样的字符则说明不是回文串
for(int i=0;i<n/2;i++)
if(t[i]!=t[n-1-i])
return false;
return true;
}
//返回最小回文子串的长度
int shortHw(string &s)
{
//将答案初始化最大，方便迭代
int res=0x3f;
int n=s.size();
//i表示字符串的开头，j表示子串的长度
for(int i=0;i<n-1;i++)
for(int j=2;j<=n-i;j++)
{
string t=s.substr(i,j);
int num=t.size();
//当子串是回文串并且长度大于1时，更新答案
if(hw(t)&&num>1) res=min(res,num);
}
if(res!=0x3f) return res;
//若没有符合题意的答案，则要返回-1
return -1;
}
int main()
{
string s;
cin>>s;
cout<<shortHw(s);
return 0;
}
思路2：任何长度为n（n>3）的回文字符串，一定可以通过去掉首尾字母，生成一个长度为n-2的回文字符串，以此一直迭代下去，就只有长度为2和3的回文字符串两种可能，也即将原问题转化为判定是否存在长度为2,3的回文字符串。
长度为2的回文字符串的判定方法：判断是否存在两个相邻的相同字符
长度为3的回文字符串的判定方法：判断是否存在两个下标距离为2的相同字符
时间复杂度：O(N)
参考代码2：
#include<iostream>
using namespace std;
int main()
{
string s;
cin>>s;
//判断是否有两个连续的相同字符
for(int i=1;i<s.size();i++)
if(s[i-1]==s[i])
{cout<<2;return 0;}
//return 0可以提前结束程序
//判断是否有间隔一个的相同字符
for(int i=1;i<s.size()-1;i++)
if(s[i-1]==s[i+1])
{cout<<3;return 0;}
//没有答案的话输出-1
cout<<-1;
return 0;
}
C.小红的口罩
知识点：贪心，堆
思路1：每次都选用舒适度最小的口罩。先将口罩初始的不舒适度从小到大排序，然后取第一个（也就是舒适度最低的口罩）使用，然后将该口罩的舒适度x2，如果这个口罩的不舒适度大于后面的，那么再排序，重复之前步骤，直到达到最多能忍受的不舒适度总和。
时间复杂度：排序的时间复杂度为O(NlogN)，外层不清楚，总之超时了过不了。
可能的优化：口罩使用后不舒适度翻倍，然后用二分找到它的位置，将其插入。
参考代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);//对初始的不舒适度排序
int cnt=0;//cnt记录天数
while(k>0)
{
k-=a[0];//k就相当于是耐久值
a[0]=a[0]*2;//不舒适度翻倍
if(a[0]>a[1])//表明当前的位置不对了
sort(a,a+n);
cnt++;
}
cout<<cnt-1;
return 0;
}
思路2：使用小根堆来存储，每次都是最小值出堆，使用后两倍入堆。
priority_queue<int,vector
时间复杂度：O(NlogNlogk)
参考代码2：
#include<iostream>
#include<queue>//小根堆包含的头文件
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
priority_queue<int,vector<int>,greater<int>> q;//小根堆，不加greater是大根堆
while(n--)
{
int x;
cin>>x;
q.push(x);//入堆
}
int cnt=0;//记录天数
while(k>0)
{
int temp=q.top();//取堆顶元素即最小值
q.pop();//将堆顶元素弹出
k-=temp;
q.push(temp*2);//使用后两倍入堆
cnt++;
}
cout<<cnt-1;
return 0;
}
D.小红的数组
知识点：排序、二分
思路：二分做法，先将数组从小到大排序，已知了x，那么整个数组就可以以k/x为分割线来分割区间。二分边界问题很多，实际应用中需要仔细甄别。
时间复杂度：O()
参考代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=3e5+10;
LL a[N];
int main()
{
int n;
LL k;
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
LL res1=0,res2=0,res3=0;
sort(a,a+n);
for(int i=0;i<n-1;i++)
//a[i+1]是目前方案中的最小值
//a[i]*a[i+1]<k意味着a[i]与后面所有的数的乘积都满足大于k
if(a[i]*a[i+1]>k)
res1+=n-i-1;//(n-1)-(i+1)+1
else if(a[i]*a[n-1]<k)
res3+=n-i-1;
else
{
//lower_bound 查找不小于目标值的第一个数，参数（头，尾，x），返回值为指针
//upper_bound 查找大于目标值的第一个数，找到的是右边界+1的位置
int l=lower_bound(a+i+1,a+n,k/a[i])-a;//左边界
int r=upper_bound(a+i+1,a+n,k/a[i])-a;//右边界+1
//k能整除a[i]意味着存在k/a[i]这个数
if(k%a[i]==0)
{
res2+=r-l;
res1+=n-r;//(n-1)-r+1
res3+=l-i-1;//(l-1)-(i+1)+1
}
//不能整除，l在小于的方案，r在大于的方案
else
{
res1+=n-r;//(n-1)-r+1
//l和r之间可能还会有一段相等的数，这一段应该都在小于方案
res3+=r-i-1;//(r-1)-(i+1)+1
}
}
cout<<res1<<' '<<res2<<' '<<res3;
return 0;
}
E.小红的rpg游戏
知识点：最短路、枚举
思路：
参考代码：