竞赛讨论区 > 【题解】小白月赛41题解
头像
神崎兰子
编辑于 2021-12-04 22:10
+ 关注

【题解】小白月赛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;
}

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐