题解 |小白赛41全题解
小红的签到题
https://ac.nowcoder.com/acm/contest/11218/A
小白赛41全题解
写在前面:
说实话这次月赛排名比上次进步了许多,可能是小白赛改版了简单了不少,但是排名确实是比之前进步了,说实话D题没A出来实属不应该,不过E题用dfs爆搜偷摸过了算是抵消了。f题其实也不难,给我多点时间说不定也能A出来。
总之改版后的小白赛才是名副其实的小白赛啊！！
题目:
A:小红的签到题
没什么好说的,白给的签到题:
考场code:
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
cin>>a>>b>>c;
cout<<c/a<<endl;
return 0;
}
B:小红的ABC:
这题O(n^3)的算法也是可以过的,但我还是做复杂了。容易想到如果存在最短回文子串,那他一定不是2就是3,枚举每一个子串就行了,dp[i][j]代表s[i]-s[j]是不是回文串,如果s[i]==s[j]就看dp[i+1][j-1]就行了,我这里用的是区间dp的写法,而且每段区间我都枚举了的
其实你们只需要枚举
如果存在s[i]==s[i+1]就直接输出2
否则就枚举如果存在s[i]==s[i+2]就直接输出3
否则就输出-1
因为如果没有长度为2和3的回文子串就一定不存在大于等于2和3的回文子串,可以自行模拟下,很好理解我就不讲了
考场code(很多没必要的操作hhh):
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
string s;
int minlen = 0x3f3f3f;
bool flag;
int main()
{
cin>>s;
int n = s.size();
for(int i = 1;i<=n;++i)
dp[i][i] = 1,dp[i+1][i] = 1;
for(int len = 2;len<=n;++len)
{
for(int i = 0;i+len-1<n;++i)
{
if(flag) break;
int r = i+len-1;
if(s[i]==s[r]&&r-i==1) dp[i][r] = 1;
if(s[i]==s[r]&&r-i>1) dp[i][r] = dp[i+1][r-1];
if(dp[i][r]==1&&len%2==0)
{
minlen = 2;
flag = true;
break;
}
else if(dp[i][r]==1&&len%2)
{
minlen = min(minlen,len);
flag = true;
break;
}
}
}
if(minlen>=0x3f3f3f) cout<<"-1"<<endl;
else cout<<minlen<<endl;
return 0;
}
C:小红的口罩:
很简单的贪心,堆模拟一下就行了。如果每次用数组直接O(n)找最小值肯定会超时的。
用堆维护实时最小不舒适度,每次取出不舒适度最小的口罩,直至当前累计的不舒适度加上最小的不舒适度大于能忍受的上限的时候直接退出就行了,每次取出最小的不舒适度时累计天数加一,然后将不舒适度*2再入堆
堆这里用的是stl的priority_queue
考场code:
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int ans;
int day;
int n,m;
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;++i)
{
int x;
cin>>x;
q.push(x);
}
while(1)
{
int temp = q.top();
q.pop();
if(temp+ans>m) break;
ans+=temp;
temp*=2;
day++;
q.push(temp);
}
cout<<day<<endl;
return 0;
}
D:小红的数组:
个人认为我这题没a出来实属不应该,总是想着暴力优化了,最后想到二分时时间已经来不及了
对于这题我们先对数组进行一次排序,这样对于每一个数a[i]，a[i]*a[j]小于 k 等于k 大于k的情况一定分别在三个连续的区间
而我们只需要二分的找出最后一个a[i]*a[j]<k的位置,这里称他为L,则L - i 就是对于这个数a[i]相乘其他数所能获得的小于k的方案数
紧接着找到第一个a[i]*a[j]>k的位置,称其为R,则n-R就是对于这个数a[i]相乘其他数所能获得的大于于k的方案数
则r-l就是等于k的方案数了
事后补救code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[300005];
int n;
ll k;
ll ans1,ans2,ans3,v1,v2;
inline ll read(){//当时为了优化我的O(n^2)常数用的read()
char ch = getchar();ll x = 0, f = 1;
while(ch<'0'||ch>'9'){if(ch == '-') f = -1;ch = getchar();}
while('0'<=ch && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
return x*f;
}
int main()
{
n = read();
k = read();
for(int i = 1;i<=n;++i)
a[i] = read();
sort(a+1,a+1+n);
for(int i = 1;i<=n;++i)
{
int l = lower_bound(a + 1 + i,a + 1 + n,1.0 * k / a[i]) - a;
int r = upper_bound(a + 1 + i,a + 1 + n,1.0 * k / a[i]) - a;
ans1+=l-i-1;
ans3+=n-r+1;
ans2+=r-l;
}
printf("%lld %lld %lld",ans3,ans2,ans1);
return 0;
}
E:小红的rpg游戏:
本题考场中用dfs稍微剪下枝A掉的,不过赛后数据加强了就A不了了,剪枝也是最经典的当当前搜到的步数大于最短步数就return掉
考场code:
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
char ma[55][55];
int vis[55][55];
int n,m,h;
int ans = 0x3f3f3f3f;
void dfs(int nowx,int nowy,int nowhp,int step)//分别表示当前坐标,当前血量,当前步数
{
if(step>ans||vis[nowx][nowy]||nowhp<=0) return;//越界条件
if(nowx==n&&nowy==m)
{
ans = min(ans,step);
return;
}
vis[nowx][nowy] = 1;
for(int i = 0;i<4;++i)
{
int xx = nowx+dx[i],yy = nowy+dy[i];
if(ma[xx][yy]=='*') continue;
if(ma[xx][yy]=='.') dfs(xx,yy,nowhp,step+1);
if(ma[xx][yy]<='9'&&ma[xx][yy]>='0') dfs(xx,yy,nowhp-ma[xx][yy]+'0',step+1);
}
vis[nowx][nowy] = 0;
}
int main()
{
cin>>n>>m>>h;
memset(ma,'*', sizeof(ma));
for(int i = 1;i<=n;++i)
for(int j = 1;j<=m;++j)
cin>>ma[i][j];
dfs(1,1,h,0);
if(ans>=0x3f3f3f3f) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
不过这种做法数据大点就会超时了,所以我再写了一遍正解:因为怪物只有十种,对于每一个怪物有选和不选两种状态,如果选就将这个怪物标为可以走的路,不选就标为不可以走的路。这里通过状态压缩的方式枚举每个怪物选或者不选,对于每一种状态都用bfs求一遍最短路径
事后补救code：
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,h;
};
int n,m,h;
char ma[55][55];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
node b[15];//用于存每个怪物的坐标
int ans = 0x3f3f3f3f;
int cnt;
int main()
{
memset(ma,'*',sizeof(ma));
cin>>n>>m>>h;
for(int i = 1;i<=n;++i)
for(int j = 1;j<=m;++j)
{
cin>>ma[i][j];
if(ma[i][j]<='9'&&ma[i][j]>='0')
b[cnt++] = (node){i,j,ma[i][j]-'0'};
}
for(int i = 0;i<1<<cnt;++i)//枚举每个怪物选或者不选的状态
{
int vis[55][55] = {0};
int step[55][55] = {0};
int hh = h;
for(int j = 0;j<cnt;++j)
{
if(1<<j&i) vis[b[j].x][b[j].y] = 1,hh-=b[j].h;//如果选怪物,就标记一下让这条
//路可以走
else vis[b[j].x][b[j].y] = 0;
if(hh<=0) continue;//如果选怪物所需血量大于当前血量肯定不行的啦
for(int i = 1;i<=n;++i)//初始化步数数组
for(int j = 1;j<=m;++j)
step[i][j] = -1;
queue<pair<int,int>> q;
step[1][1] = 0;
q.push(make_pair(1,1));
while(!q.empty())//bfs板子
{
if(step[n][m]!=-1) break;
int xx = q.front().first,yy = q.front().second;
q.pop();
for(int i = 0;i<4;++i)
{
int xxx = xx+dx[i],yyy = yy+dy[i];
if(xxx==n&&yyy==m)
{
step[xxx][yyy] = step[xx][yy]+1;
break;
}
if((ma[xxx][yyy] == '.'||vis[xxx][yyy])&&step[xxx][yyy] == -1)
{
q.push(make_pair(xxx,yyy));
step[xxx][yyy] = step[xx][yy]+1;
}
}
}
if(step[n][m]!=-1)
ans = min(ans,step[n][m]);
}
if(ans>=0x3f3f3f3f) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
F:小红的375:
一题简单的构造题(虽然我没写呜呜呜),
这题第一眼看像数位dp哈哈哈但是只需要输出一个答案就行。而且是重排一个数,10^300000全排列莽过估计得跑几小时
所以我们再看一下题目,需要是375的倍数,那为什么是375呢？那肯定有他的特殊性嘛
375可以分解成125*3所以他只需要是125和3的倍数就行了,对于3只需要所有位加起来为3的倍数就行了,对于125只需要后3位为125的倍数就行了(000也算)
所以我们只需要打个表判断这个数有没有后4位能构造成125倍数的情况，所以我们可以用一个哈希表存储每一个数字有多少位,枚举后三位为125,250,375...的情况,当然因为不能含有前导0所以我们需要尽量先把含有0的情况放在后三位比如说000,250等情况需要优先处理。
构造完后三位之后剩余的情况随便构造就行了,这里建议从大到小排数字肯定能过不用担心前导0
事后补救code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int has[10];
string bs[8] = {"000","500","750","250","625","375","875","125"};
ll sum;
int main()
{
char c;
while(cin>>c)
has[c-'0']++,sum+=c-'0';
if(sum%3){
cout<<-1<<endl;
return 0;
}
for(int i = 0;i<8;++i)
{
int j = 0;
for(j = 0;j<3;++j)
has[bs[i][j]-'0']--;
for(j = 0;j<=9;++j)
if(has[j]<0) break;
if(j==10)
{
for(j = 9;j>=0;--j)
{
while(has[j]--)
cout<<j;
}
for(j = 0;j<3;++j)
cout<<bs[i][j];
return 0;
}
for(j = 0;j<3;++j)
has[bs[i][j]-'0']++;
}
cout<<-1;
return 0;
}
