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