（A～F）题解 今天是lzgg出的题呀，是小红专场；题目不是很难，但是比赛时候网站老是崩，体验就不太舒服；
A、小红的签到题
题目：传送门
题意： a 道题，一共有 b 人参赛，所有人通过题目数量的总数为 c 道，问最多有多少人全部写完；
解题思路：简单签到题，这题差点就抢到首A了，QAQ；直接用c除以a不计算余数就是答案；
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a, b, c;
cin>>a>>b>>c;
cout<<c/a<<endl;
return 0;
}
B、小红的ABC
题目：传送门
题意：给你一个字符串s判断这个字符串的子串中长度超过1的最短的回文串长度是多少，如果没有，输出-1；
解题思路：看一眼数据范围，字符串长度不超过100，这数据范围还要啥自行车，直接暴力枚举每一个长度大于2的字串，看它是不是回文串，然后找到最小的长度；
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
string s;
cin>>s;
int n = s.length();
int ans = 0x3f3f3f3f;//维护子串长度最小的回文串长度
string c, t;
for(int i = 0; i<n; i++){
for(int j = i+1; j<n; j++){
c = "", t = "";
for(int k = i; k<=j; k++) c+=s[k], t+=s[j-k+i];
// for(int k = c.length()-1; k>=0; i--) t+=c[k];
// cout<<c<<endl;
// cout<<t<<"***"<<endl;
if(c == t){//判断回文串
ans = min(ans, j-i+1);
}
}
}
if(ans == 0x3f3f3f3f) puts("-1");
else cout<<ans<<endl;
return 0;
}
C、小红的口罩
题目：传送门
题意：换种说法讲这个题意，小红能吃下重量为k的食物，现在有n个食物，每个食物重量是a[i]，小红每吃一个重量为x的食物，就会多出一个重量为2*x的食物，问小红最多能吃多少个食物；
解题思路：这题首先可以看出每次都是贪心得取最小的，而如果直接用数组存储暴力模拟每次取最小的，时间复杂度就是O(nnk)，一定会超时，所以我们可以选择用小根堆去存储，使得插入、删除都是longn的；关于小根堆可以直接用stl中的priority_queue，详细用法自行查询；
AC代码：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
struct cmp1
{
bool operator ()(int &a,int &b)
{
return a>b;
}
};
priority_queue <int,vector<int>, cmp1> q;//小根堆
const int N = 100005;
int main()
{
int n, k, x;
scanf("%d%d", &n, &k);
for(int i = 1; i<=n; i++){
scanf("%d", &x);
q.push(x);
}
int ans = 0;
while(k&&!q.empty()){
int t = q.top();
q.pop();
if(t>k) break;
k-=t;
ans++;
if((ll)t*2<=1e9){
q.push(t*2);
}
}
cout<<ans<<endl;
return 0;
}
D、小红的数组
题目：传送门
题意：小红有一个长度为n的数组a，求出同时在数组里取两个数，分别输出他们的乘积大于k，等于k，小于k的方案数；
解题思路：按照lzgg给出的官方题解，这题可以用二分和双指针来解决，我是用二分来解决的，当然二分需要注意边界条件，我在这里吃了两次亏；二分的前提就是对给出的数组进行从小到大的排序，排完序后对于每个a[i]，我们需要二分查找的是k/a[i]的边界（可以直接用stl中的二分函数），这里注意要分类讨论能否进行整除；而我们要求的三种情况：
1、当乘积等于k时：这种情况只有在k能整除a[i]，且数组a中含有k/a[i]的时候，才会存在，数量为k/a[i]的数量，可以提前用map存一下数量，注意当a[i] == k/a[i]的时候，需要减去1（因为一次不能同时取一个位置上的数）；
2、当乘积大于k的时候：这种情况下，若是k能整除a[i]，找到第一个大于k/a[i]的数的位置（upper_bound())tot，后面的n-tot+1个数和他组合满足此情况，注意判断此时a[i]是否在tot后面，若是则方案数减1（因为一次不能同时取一个位置上的数）；k不能整除a[i]的时候类似；
3、当乘积小于k的时候：这种情况与第二种情况相反，就不多赘述；
此时利用二分求出来的答案，会造成相同两个位置上的数【x，y】取一次【y，x】取一次，这样会使得最终的答案恰好是标准答案的两倍，最后的答案需要除以2；
AC代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int N = 300005;
ll a[N];
map<ll, int> ma;
int main()
{
int n;ll k;
scanf("%d%lld", &n, &k);
for(int i = 1; i<=n; i++) scanf("%lld", &a[i]), ma[a[i]]++;
sort(a+1, a+n+1);
ll t;
ll ans = 0, res = 0, num = 0;
a[n+1] = 0x3f3f3f3f;
for(int i = 1; i<=n; i++){
t = a[i];
ll p = k/t;
if(k%t == 0){
int tot = lower_bound(a+1, a+n+1, p) - a;
if(p == a[tot]) {
ans+=ma[p];
if(p == a[tot]) ans--;
}
res+=tot-1; if(t<a[tot]) res--;
tot = upper_bound(a+1, a+n+1, p)-a;
num+=n - tot + 1; if(t>=a[tot]) num--;
}
else{
int tot = upper_bound(a+1, a+n+1, p) - a;
res+=tot-1; if(t<a[tot]) res--;
num+=n-tot+1; if(t>=a[tot]) num--;
}
}
cout<<num/2ll<<' '<<ans/2ll<<' '<<res/2ll<<endl;
return 0;
}
E、小红的rpg游戏
题目：传送门
题意：给你一个nm大小的地图，小红需要从左上角走到右下角，途中有'.'道路可以直接走，''围墙不能走，'0~9的数字'，表示走这个点需要花费给定数值的血量，小红有h滴血，求小红从左上角走到右下角最少需要走多少个格子（注：数字格子不超过10个）；
解题思路：如果没有数字格子，那么这个题目就是一个经典的bfs最短路问题，但是题目中给定的条件数字格子不超过10个，我们就可以枚举每个数字格子选还是不选，如果不选，那么这个数字格子就可以看作是一个'*'，无法通行，如果选择，则需要判断小红的血量h能否撑过所有的数字格子，对枚举的每一种状态做dfs就行，因为枚举最多10个格子选或不选，就可以二进制状压枚举；
昨晚眼瞎没看到格子数不超过10个，一直在想dp做法，结果F题也没看，dp永远的痛；
AC代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 100;
string s[N];
int v[N][N];
struct lq{
int x, y, h;
lq(int x, int y, int h): x(x), y(y), h(h){}
};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, h;
vector<lq>a;
int main()
{
scanf("%d%d%d", &n, &m, &h);
for(int i = 0; i<n; i++) cin>>s[i];
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(s[i][j]>='0'&&s[i][j]<='9'){
a.push_back(lq(i, j, s[i][j] - '0'));
}
}
}
int ans = 0x3f3f3f3f;
for(int i = 0; i<1<<a.size(); i++){
int sum = 0;
for(int j = 0; j<a.size(); j++){
if((1<<j)&i) v[a[j].x][a[j].y] = 1, sum+=a[j].h;
else v[a[j].x][a[j].y] = 0;
}
if(sum>=h) continue;
queue<pair<int,int> >q;
q.push({0,0});
int st[N][N] = {};
memset(st, -1, sizeof st);
st[0][0] = 0;
while(!q.empty()){
pair<int, int>t = q.front();
q.pop();
for(int j = 0; j<4; j++){
int x = t.first+dx[j], y = t.second+dy[j];
if(x<0||x>=n||y<0||y>=m||st[x][y]!=-1) continue;
if(s[x][y] == '.'||(s[x][y]!='*'&&v[x][y])){
st[x][y] = st[t.first][t.second]+1;
q.push({x, y});
}
}
}
if(st[n-1][m-1]!=-1) ans = min(ans, st[n-1][m-1]);
}
if(ans == 0x3f3f3f3f) puts("-1");
else cout<<ans<<endl;
return 0;
}
F、小红的375
题目：传送门
题意：给出一个位数长度为300000的数字，对它的各个位数进行重新排列，使得重排后的数能够被375整除，输出重排后的数（不包含前导0），否则输出-1；
解题思路：375可以拆分成3*125，即重排后的数字要同时是3和125的倍数，注意数字位数过大；
对于3很简单，各个位数相加的和如果能被3整除，那么这个数也能被3整除；
对于125，125的特征是一个125的循环是1000，简单说就是枚举三位内125的倍数，若一个数最后三位数是125的倍数，则这个数能被125整除；枚举方法可以用桶去存储，查看桶中剩余的数能否构成一个三位数的125的倍数（注意考虑前导0）；
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
int st[50];
// string check[8] = {"125", "250", "375", "500", "625", "750", "875", "000"};
string check[8]={"500","000","750","250","125","375","625","875"};//这里把0结尾的放在前面，预防前导0；
int main()
{
string s;
cin>>s;
int len = s.length();
ll ans = 0;
for(int i = 0; i<len; i++){
st[s[i] - '0']++;
ans += s[i] - '0';
}
if(ans%3!=0){
puts("-1");
return 0;
}
for(int i = 0; i<8; i++){
for(int j = 0; j<3; j++){
st[check[i][j] - '0']--;
}
bool flag = 1;
for(int j = 0; j<=9; j++){
if(st[j]<0){
flag = 0;
break;
}
}
if(flag){
for(int j=9;j>=0;j--)while(st[j])printf("%d", j),st[j]--;
cout<<check[i];
return 0;
}
for(int j = 0; j<3; j++){
st[check[i][j] - '0']++;
}
}
puts("-1");
return 0;
}
京公网安备 11010502036488号