【题解】小白月赛41题解

E题数据已加强，之前用dfs通过的可能现在过不去，感兴趣的同学可以重新提交试试（不会影响到排行榜

写在前面的话

作为改版后的第一场小白月赛，所有题目的难度控制在了div2 A~C。本场比赛中，真正零基础的小白（无任何算法知识点）也可以通过A和B，另外F也不需要很高的知识点（但思维方面较难），可供小白尝试。而C、D、E三题则考察了非常基础的知识点/代码基本功，旨在对大家代码能力的锻炼。

希望大家ak愉快~ 赛中没通过的同学也建议补一下题目，练好自己的代码基本功。

A 小红的签到题

知识点：贪心、数学

对标cf难度：800

签到题。题目保证了数据合法，因此ak人数的最大可能即为尽可能多的人ak，剩下的人几乎全部爆零。答案为c/a。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<c/a;
}

B 小红的ABC

知识点：字符串、枚举

对标cf难度：1000

这道题本意是考特判：最短回文串的长度不会超过3。不过考虑到照顾萌新，因此放过了暴力枚举的做法，哪怕 的复杂度也是可以通过的。

我们考虑到，任何长度为 的回文字符串，一定可以通过去掉首尾字母，生成一个长度为 的回文字符串。例如：abcaacba ，我们去掉首尾生成 bcaacb 是回文字符串，同理可生成 caac 、 aa。而本题要求最短的回文字符串长度，所以我们只需要依次判断是否存在长度为 2 和 3 的回文字符串即可。

长度为 2 的回文字符串的判定方法：判断是否存在两个相邻的相同字母即可。

长度为 3 的回文字符串的判定方法：判断是否存在两个下标距离为 2 的相同字母即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int i;
    cin>>s;
    for(i=0;i<s.length()-1;i++){
        if(s[i]==s[i+1]){cout<<2;return 0;}
    }
    for(i=0;i<s.length()-2;i++){
        if(s[i]==s[i+2]){cout<<3;return 0;}
    }
    cout<<-1;
}

C 小红的口罩

对标cf难度：1200

知识点：贪心、堆、模拟

显然，我们每一天选择当前消耗最小的口罩即可。

可以用一个最小堆（优先队列）来模拟选择过程。每次最小值出堆，使用后该数的两倍入堆。这样一定能保证可以用最小的不舒适度度过最大的天数。

进阶：本做法的复杂度是 ，你可以想出复杂度 的做法吗？（提示：二分）

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    priority_queue<ll,vector<ll>,greater<ll>>q;    //这里是小根堆。不加greater即为大根堆。
    int a[101010];
    int cnt=0,sum=0;
    int n,k,i;
    cin>>n>>k;
    for(i=0;i<n;i++)cin>>a[i],q.push(a[i]);
    while(sum<=k){
        ll temp=q.top();
        q.pop();
        sum+=temp;
        q.push(temp*2);
        cnt++;
    }
    cout<<cnt-1;
}

D 小红的数组

对标cf难度：1500

知识点：排序、二分/双指针

本题是非常经典的模型了，解法也有很多种。本题解主要介绍二分和双指针两种解法。

首先显然排序不影响最终方案的统计，因此我们可以优先对数组进行排序。排序过后，对于指定一个数 而言，另一个数乘以 和 的关系就在一个连续的区间内了。我们可以通过二分或者双指针的方式求出该区间。

1.二分

显然指定一个数 之后，另一个数 是以 为边界分隔区间的，且由于排序了，因此区间满足单调性，满足二分的前置条件。

我们可以手写二分，也可以直接调用c++的库函数 lower_bound （有序数组中，返回最小的不小于 的数的指针）和 upper_bound （有序数组中，返回最小的大于 的数的指针） 达成二分的目的。

另外提一下，set 等有序容器也是可以调用 lower_bound 和 upper_bound 达成二分的目的的。返回的是对应数的迭代器。建议熟练掌握这些函数的用法。当然最好自己也要会手写二分，比如二分答案这种就无法调用库函数解决了。

2.双指针

由于一个数 之后，另一个数 的区间是连续的，且当 不断增大的时候，对应 的区间会不断变小。所以可以通过双指针来解决这个问题。

参考代码（二分解法）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[301010];
int main(){
    int n,i;
    ll k;
    cin>>n>>k;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    ll res1=0,res2=0,res3=0;
    for(i=0;i<n-1;i++){
        if(a[i]*a[i+1]>k)res1+=n-i-1;
        else if(a[i]*a[n-1]<k)res3+=n-i-1;
        else{
            int i1=lower_bound(a+i+1,a+n,k/a[i])-a;    //要注意二分的边界
            int i2=upper_bound(a+i+1,a+n,k/a[i])-a;
            if(k%a[i]!=0){
                res3+=i2-i-1;
                res1+=n-i2;
            }
            else{
                res3+=i1-i-1;
                res1+=n-i2;
                res2+=i2-i1;
            }
        }
    }
    cout<<res1<<" "<<res2<<" "<<res3<<endl;
}

E 小红的rpg游戏

知识点：最短路、枚举

对标cf难度：1600

思路：

我们观察数据范围，一共只有不超过10个怪物，因此我们可以通过状压枚举每个怪物选或不选的状态（共有最多 种状态），针对每个状态用 bfs 跑一次 的最短路即可。

总复杂度为 ，cnt为怪物数量。

进阶：本题有复杂度更优的dp做法，你能想到吗？

#include<bits/stdc++.h>
using namespace std;
string a[101];
struct mons{
    int x,y,h;
    mons(int x,int y,int h):x(x),y(y),h(h){}
};
int mk[101][101];
int main(){
    int n,m,h,i,j;
    cin>>n>>m>>h;
    for(i=0;i<n;i++)cin>>a[i];
    vector<mons>b;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(a[i][j]>='1'&&a[i][j]<='9'){
                b.push_back(mons(i,j,a[i][j]-'0'));
            }
        }
    }
    int res=1e9;
    for(i=0;i<1<<b.size();i++){        //注意这里用状压来枚举怪物选或不选的情况。
        int sum=0;
        for(j=0;j<b.size();j++){
            if((1<<j)&i)mk[b[j].x][b[j].y]=1,sum+=b[j].h;
            else mk[b[j].x][b[j].y]=0;
        }
        if(sum>=h)continue;
        queue<pair<int,int> >q;
        q.push({0,0});
        int ops[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
        int visited[101][101]={};
        memset(visited,-1,sizeof(visited));
        visited[0][0]=0;
        while(!q.empty()){
            pair<int,int>temp=q.front();    
            q.pop();
            for(j=0;j<4;j++){
                int x0=temp.first+ops[j][0],y0=temp.second+ops[j][1];
                if(x0>=0&&x0<n&&y0>=0&&y0<m&&visited[x0][y0]==-1){
                    if(a[x0][y0]=='.'||(a[x0][y0]!='*'&&mk[x0][y0])){
                        visited[x0][y0]=visited[temp.first][temp.second]+1;
                        q.push({x0,y0});
                    }
                }
            }
        }

        if(visited[n-1][m-1]!=-1)res=min(res,visited[n-1][m-1]);
    }
    if(res==10***00)cout<<-1;
    else cout<<res;
}

F 小红的375

对标cf难度：1800

知识点：数学、构造

思路：

我们可以观察到 ，因此我们只需要满足构造的数是3的倍数和125的倍数即可。

3的倍数的特征是：所有数位之和能被3整除。由于改变数的相对位置并不会改变总和，因此只需要判断初始所有数之和能否被3整除即可。

125的倍数的特征是：最后3位构成的三位数能被125整除。我们可以枚举1000以内125的倍数完成构造，只要有一个合法即可。判断是否合法的方式如下：用一个桶存每个数位的出现次数，之后即可判断能不能拿出3个数字完成后三位的构造。然后剩下的数可以倒序输出来规避前导零。

要注意特判前导零。例如3075构造成0375是不合法的，只能构造成3750。有一种避免特判的方式：先判断000、500、250、750这些包含0结尾的情况，后处理125、375、625、875这些不含0的情况。

参考代码：

#include<bits/stdc++.h>
using namespace std;
string check[8]={"500","000","750","250","125","375","625","875"};      //注意这里的顺序，无0的放后面可以规避前导零特判。
int main(){
    int tong[101010]={};
    string s;
    cin>>s;
    if(s.length()>300000)return -1;
    int sum=0,i,j;
    for(i=0;i<s.length();i++){
        tong[s[i]-'0']++;
        sum+=s[i]-'0';
    }
    if(sum%3!=0){cout<<-1;return 0;}
    for(i=0;i<8;i++){
        int sum=0;
        for(j=0;j<3;j++){
            tong[check[i][j]-'0']--;        //这里的处理技巧：先减掉，然后判断。如果不合法再加回来。
        }
        for(j=0;j<=9;j++){
            if(tong[j]<0)break;
        }
        if(j==10){
            for(j=9;j>=0;j--)while(tong[j])cout<<j,tong[j]--;
            cout<<check[i];
            return 0;
        }
        for(j=0;j<3;j++){
            tong[check[i][j]-'0']++;
        }
    }
    cout<<-1;
}