牛客小白月赛51题解~

小白月赛51题解

大家好哇，这里是51的出题人小沙，相信本场之后大家都体会到小沙改过自新了吧，这么良心的小沙应该都喜欢吧~

A:选择题

首先你需要选择一个奇数和一个偶数，我们发现一个奇数和一个偶数的和一定是一个奇数，所以我们得到的和一定是一个奇数，其次我们需要这个和小于n
所以我们需要找小于n的奇数，也就是对于偶数，我们只需要减一就可以了，对于奇数，我们需要减二才能的到小于n的奇数。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    assert(n<=1e9);
    cout<<n/2*2-1;
}

B:填空题

首先我们需要使得构造的数组的和尽可能小，其次还需要使得数组严格上升，所以我们需要将整个数组中的0变成大于前一个数+1的值，这样才能保证这两个数字保持上升的情况下，和尽可能小，并且这样还有助于后面的数尽可能小。
所以我们可以扫一遍，发现0就使他等于前一个数+1,最后在判断整个数组是否上升就好了。

#include<bits/stdc++.h>
using namespace std;

int main()
{
 int i,n,ans=0,a[105]={0};
 scanf("%d",&n);
 assert(n>=1&&n<=100);
 for(i=1;i<=n;i++)
 {
  scanf("%d",&a[i]);
  assert(a[i]>=0&&a[i]<=1e5);
  if(!a[i])a[i]=a[i-1]+1;
  else if(a[i]<=a[i-1])break;
  ans+=a[i];
 }
 if(i<=n)ans=-1;
 printf("%d\n",ans);
    return 0;
}

C:零一题

首先要知道我们构造的字符串一定需要01相间的，如果出现有两个相同数字相同的，那么他们一定会被消掉，所以我们可以构造出一个长度为的010101序列。
如果无法构造出长度为x的那么就无法构造而成。
其次我们要保证剩余下来的0或1的数量都是偶数，否则他们消除之后一定会剩余下一个数，对我们构造的01序列造成影响。
知道这些之后，我们就可以先输出长度为的01序列之后，按顺序输出剩下的所有0或1就可以了。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,x;
    cin>>a>>b>>x;
    if(a<x/2||b<x/2)return cout<<"-1\n",0;
    a-=x/2,b-=x/2;
    if(a%2||b%2)return cout<<"-1\n",0;
    for(int i=0;i<a;i++)cout<<"0";
    for(int i=0;i<x/2;i++)cout<<"01";
    for(int i=0;i<b;i++)cout<<"1";
}

D:操作题

本题的话其实是为了给大家科普一下关于快速幂这一方法的原理，如果你会快速幂的话你一定能很快速将这个题秒杀。
如果你不懂快速幂的话，你也可以通过进制分解的思路来解决此题。
思路一
考虑需要构造出一个值为，那么我们的构造方式一定要和这个n有关，我们发现一个b等于1，所以对%x%取余之后等到的值就是我们需要自己加上的值，否则当乘以之后，我们就无法将这一部分的值添加上去了。
随后我们将的值乘以之后，我就可以可以补充对取余的值了，同理可以一直补充到。
思路二
保证一直为1，然后将从高位往低位贪心，优先补充高位的值，尽可能减少需要的次数。

#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define lowit(x) (x&-x)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                             \
    std::ios::sync_with_stdio(false);   \
    std::cin.tie(nullptr);              \
    std::cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;

inline ll read(){
 ll x=0;char ch;bool f=true;
 for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
 for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
 return f?x:-x;
}
//#define LOCAL_DEFINE
#define DEBUG(x) cerr<<(#x)<<'='<<(x)<<endl
const int N=1e5+7;
ll a[N],b[N];
typedef pair<int,char> PIC;
void solve(){
 ll n=read(),x=read();
 vector<PIC> ans;
 while(n){
  for(int i=0;i<n%x;i++)
   ans.push_back({1,'a'});
  ans.push_back({2,'b'});
  n/=x;
 }
 cout<<ans.size()<<"\n";
 for(auto x:ans)
  cout<<x.first<<" "<<x.second<<"\n";
}

int main(){
 #ifdef ONLINE_JUDGE
 #else
  //fre("1");
 #endif
 ll T=1;
 T=read();
 for(int i=1;i<=T;i++)solve();
 #ifdef LOCAL_DEFINE
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
 #endif
 return 0;
}

E:语法题

本题其实可以发现只有当a单调上升的情况下，才会有意义，如果比之前小，那么本次就不需要计算。
其次我们需要能够快速求出 / 等于 的的取值范围，我们可以发现，他的取值范围为。然后他和我们的条件语句的区间相交的地方就是所有符合情况的解，计算之后即可得到答案。
对于我们的条件语句，显然他的有效范围为[ {},-1]。
最后还需要判断一点，如果原并没有进入一个条件语句，那么他也是合法的。此时有一个答案。
这里埋了一个小逻辑谜题，可能有很多没有发现，我们都知道long long int 类型的值的大小不能超过1e18数量级，但是这里乘法可能会导致超过，但是其实可以发现，如果一个数能够进入条件语句，那么他一定小于1e9,1e9除以一个正整数是一定不会得到一个1e9以上的结果的，所以如果n大于1e9,我们可以直接return。

#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define lowit(x) (x&-x)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                             \
    std::ios::sync_with_stdio(false);   \
    std::cin.tie(nullptr);              \
    std::cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;

inline ll read(){
 ll x=0;char ch;bool f=true;
 for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
 for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
 return f?x:-x;
}
//#define LOCAL_DEFINE
#define DEBUG(x) cerr<<(#x)<<'='<<(x)<<endl
const int N=1e5+7;
ll a[N],b[N];
void solve(){
 int n=read();
 for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),assert(1<=a[i]&&a[i]<=1e9),assert(1<=b[i]&&b[i]<=1e9);
 ll x=read(),ans=0,last=1;
    assert(0<=x&&x<=1e18);
    for(int i=1;i<=n;i++)last=max(last,a[i]);
    if(x>=last)ans++;
    last=1;
 if(x>1e9)return cout<<ans,void();
 for(int i=1;i<=n;i++){
  ll l=x*b[i],r=x*b[i]+b[i]-1;
  l=max(l,last),r=min(r,a[i]-1);
  last=max(a[i],last);
  //last=a[i];
        if(r<l)continue;
  ans+=r-l+1;
 }
 cout<<ans<<"\n";
}

int main(){
 #ifdef ONLINE_JUDGE
 #else
  //fre("1");
 #endif
 ll T=1;
 //T=read();
 for(int i=1;i<=T;i++)solve();
 #ifdef LOCAL_DEFINE
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
 #endif
 return 0;
}

F:平均题

首先我们可以先把所有区间中，所有区间长度相同的和先合起来。
例如：
当长度为1的时候，所有长度为1的区间的和之和等于整个区间的和。
当长度为2的时间，所有长度为2的区间的和之和等于。
我们可以发现，这个式子还可以等于。
当长度增加之后，我们可以发现长度为的区间的和等于长度为的区间的和加上，当之后，他的值又等于，所以我们把之前计算的储存一下即可。
最后你需要知道一个叫做逆元的一个知识点，使得能够处理模数情况下的除法。

#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define lowit(x) (x&-x)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                             \
    std::ios::sync_with_stdio(false);   \
    std::cin.tie(nullptr);              \
    std::cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;

inline ll read(){
 ll x=0;char ch;bool f=true;
 for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
 for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
 return f?x:-x;
}
//#define LOCAL_DEFINE
#define DEBUG(x) cerr<<(#x)<<'='<<(x)<<endl
const int N=1e5+7;
const int mod=1e9+7;
ll dp[N],s[N],f[N];
ll ksm(ll n,ll m){
 ll res=1;
 for(;n;n>>=1,m=m*m%mod)if(n&1)res=res*m%mod;
 return res;
}
void solve(){
 ll n=read(),fn=1,ans=0;
 for(int i=1;i<=n;i++)s[i]=read()+s[i-1];
    for(int i=1;i<=n;i++)s[i]%=mod;
 for(int i=1;i<=n;i++)fn=fn*i%mod;
 f[1]=1;for(int i=2;i<=n;i++)f[i]=(-mod/i*f[mod%i]%mod+mod)%mod;
 for(int i=1;i<=(n+1)/2;i++)dp[i]=dp[n-i+1]=(dp[i-1]+s[n-i+1]-s[i-1]+mod)%mod;
 for(int i=1;i<=n;i++)dp[i]=dp[i]*fn%mod*f[i]%mod;
 for(int i=1;i<=n;i++)ans+=dp[i];
 cout<<ans%mod*ksm(mod-2,fn)%mod;
}

int main(){
 #ifdef ONLINE_JUDGE
 #else
  //fre("13");
 #endif
 ll T=1;
 //T=read();
 for(int i=1;i<=T;i++)solve();
 #ifdef LOCAL_DEFINE
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
 #endif
 return 0;
}

G:计算题

对于本题，首先你需要能够快速的计算出一个带单次不匹配的回文串，有两种方法。
方法一：
在同一hash规则下，从先往后hash和从后往前hash的值相等即可保证该串是回文，如果不相等，可以将该字符串切分成两段，如果存在一段相等一段不等，那么继续判断不等的那一串，如果都不相等，那么他一定会存在两个不相等的地方。
方法二：
通过二分将第前缀相等的地方计算出来，然后跳过不等的字符，继续判断剩下的字符串是否相等。

当你知道上述方法之后答案基本上就计算出来了。
然后分类讨论一下，如果一个串是回文串，且他是一个偶数长度串，那么他无法随意改变，字符串本质不变，贡献1。
如果是回文串，并且他是一个奇数回文串，那么我们可以更改中间的字符，贡献2.
如果一个串是一个只有一个位置不等的伪回文串，那么我们可以修改不等的地方，左右两遍都可以修改成对方的样子，贡献2。

#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                             \
    std::ios::sync_with_stdio(false);   \
    std::cin.tie(nullptr);              \
    std::cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;

ll lowit(ll x){
 return x&-x;
}

inline ll read(){
 ll x=0;char ch;bool f=true;
 for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
 for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
 return f?x:-x;
}
//#define LOCAL_DEFINE
#define DEBUG(x) cerr<<(#x)<<'='<<(x)<<endl
template<int T>
struct ModInt {
    const static int MD = T;
    int x;
    ModInt(ll x = 0) : x(x % MD) {}
    int get() { return x; }
    ModInt operator + (const ModInt &that) const { int x0 = x + that.x; return ModInt(x0 < MD ? x0 : x0 - MD); }
    ModInt operator - (const ModInt &that) const { int x0 = x - that.x; return ModInt(x0 < MD ? x0 + MD : x0); }
    ModInt operator * (const ModInt &that) const { return ModInt((long long)x * that.x % MD); }
    ModInt operator / (const ModInt &that) const { return *this * that.inverse(); }
    void operator += (const ModInt &that) { x += that.x; if (x >= MD) x -= MD; }
    void operator -= (const ModInt &that) { x -= that.x; if (x < 0) x += MD; }
    void operator *= (const ModInt &that) { x = (long long)x * that.x % MD; }
    void operator /= (const ModInt &that) { *this = *this / that; }
    ModInt inverse() const {
        int a = x, b = MD, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        if (u < 0) u += MD;
        return u;
    }
};
const int mod=1e9+7,p=131;
const int N=1e6+7;
typedef ModInt<mod> mint;
char s[N];
mint q[N],h[N],len[N];
mint askq(int l,int r){
 if(l>r)return 0;
 mint c=r-l,ans=q[r]-q[l-1]*len[c.x+1];
 return ans;
}
mint askh(int l,int r){
 if(l>r)return 0;
 mint c=r-l,ans=h[l]-h[r+1]*len[c.x+1];
 return ans;
}
#define mid (l+r>>1)
int ask(int l,int r,int L,int R){
 if(l==r)return l;
 int len=mid-l+1;
 if(askq(l,l+len-1).x!=askh(R-len+1,R).x)return ask(l,l+len-1,R-len+1,R);
 else return ask(l+len,r,L,R-len);
}
int check(int r){
 if(askq(1,r).x==askh(1,r).x)return 2;
 int x=ask(1,r,1,r),y=1+r-x;
 mint qa=askq(1,x-1)*p,qb=askq(x+1,y-1)*p,qc=askq(y+1,r),
  ha=askh(1,x-1),hb=askh(x+1,y-1)*p,hc=askh(y+1,r)*p;
 mint qq=(qa*len[y-1-x]+qb)*len[r-y]+qc,
  hh=(hc*len[y-1-x]+hb)*len[x-1]+ha;
 if(qq.x==hh.x)return 1;
 return 0;
}
void solve(){
 int n=read();
 scanf("%s",s+1);
 for(int i=1;i<=n;i++)q[i]=q[i-1]*p+s[i]-'a';
 for(int i=n;i;i--)h[i]=h[i+1]*p+s[i]-'a';
 len[0]=1;for(int i=1;i<=n;i++)len[i]=len[i-1]*p;
 ll ans=0;
 for(int i=1;i<=n;i++){
  int x=check(i);
  if(i%2&&x==2)ans+=26;
        else if(x==2)ans++;
  else if(x==1)ans+=2;
 }
 cout<<ans<<"\n";
}

int main(){
 #ifdef ONLINE_JUDGE
 #else
  //fre("22");
 #endif
 ll T=1;
 //T=read();
 for(int i=1;i<=T;i++)solve();
 #ifdef LOCAL_DEFINE
     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
 #endif
 return 0;
}
全部评论
您好，,C题输入3 4 5，可以构造出0101011，满足去重后长度为5的条件，但您的程序输出-1，是否有问题呢？
点赞 回复 分享
发布于 2022-06-04 09:10
你好，F数据有负吗？
点赞 回复 分享
发布于 2022-06-07 01:02
代码没正常显示
点赞 回复 分享
发布于 2022-06-03 21:21

相关推荐

05-13 20:22
清华大学 机械设计/制造
机械专业目前的真实就业情况是什么？
大家好，今天给大家分享一下机械专业目前的真实就业情况。目前很多企业招的人数都不多。下面给你们分享最近的一些校招工资。1、双非机械硕士。岗位：机械技术。地点：大冶。薪资：13w。公司缴纳五险二金，公积金单边12％，餐补300，食堂提供宿舍，提供两人一间的单身公寓，12辆通勤车接送，早上八点上班，下午四点十分下班，双休且所有法定节假日休息。2、211机械硕士。岗位：机械工程师。地点：广州。薪资：16k*14。加班没有加班费只能调休。3、双非机械硕士。岗位：机械助理工程师。地点：广州。薪资：8k*13。底薪5-6k（实习期转正后涨幅5-15%），13薪，绩效奖金为底薪30%，13薪。大小周，有加班费...
牛客创作赏金赛
点赞 评论 收藏
分享
05-14 19:08
滴滴_运维开发工程师(准入职员工)
滴滴内推-滴滴内推码
薪资：&nbsp;我是运营岗，本科生&nbsp;150/d，工作时间是早10晚7，弹性打卡（但其实每天打卡四小时就算一天），午休&nbsp;2&nbsp;小时（不过中午休息区比较难抢）&nbsp;交通：&nbsp;我在东软职场，每天上下班有西二旗到公司往返的摆渡车，不同职场之间往来打车可以报销，21:00&nbsp;下班回家也可以报销（但我从来没用过，没加过班）&nbsp;福利：&nbsp;开水畅饮，特定节假日有礼盒，公司经常会举办各种活动，参加会有小礼品和积分，积分可以在商城兑换物品。&nbsp;吃饭：&nbsp;午饭需要自己解决，每晚有&nbsp;30&nbsp;的餐补，可以去周边餐馆点餐，也可以在内部软件点餐，直接送到所在楼层茶水间&nbsp;总体感觉在滴滴很舒服，工作强度不大，我所在的部门也没有太多dirt...
滴滴公司福利 667人发布
点赞 评论 收藏
分享
04-16 18:40
北华大学 嵌入式软件开发
佬们这简历能找到实习吗？
我就是0offer糕手：北大不乱杀
点赞 评论 收藏
分享
05-11 20:45
赣南科技学院 Java
难绷，这是。。
不是吧，面试都这样了 #java实习#
有担当的灰太狼又在摸鱼：零帧起手查看图片
点赞 评论 收藏
分享
05-12 22:09
门头沟学院 嵌入式软件工程师
嵌入式每日面经
ARM的体系结构了解吗？问了项目用了STM32的哪些外设？这些外设功能分别干什么？结果问到项目用了哪些数据，怎么采集的，提示我把ADC给忘记了。SD卡读写部分。FLASH读写串口+DMA收发数据，如何配置DMA我是以x86架构回答的设计rbp和rax寄存器，arm架构操作的寄存器有所区别input输入子系统，怎么实现的，怎么和中断联系起来如何在中断里面等待数据准备完成中断有传参和返回值吗，为什么bios是什么？bios有什么作用？怎么引导后续的启动？DMA的配置延时怎么写的？说systick，然后又问我systick中断相关的。高优先级中断在执行时有一个低优先级触发，高优先级结束后会不会执行？...
查看20道真题和解析 嵌入式笔面经分享 面试问题记录
点赞 评论 收藏
分享
评论
5
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛油的搬砖plog #
26261次浏览 113人参与
# 大学最后一个寒假，我想…… #
28971次浏览 274人参与
# 一人一个landing小技巧 #
23575次浏览 458人参与
# 运营每日一题 #
67608次浏览 648人参与
# 查收我的offer竞争力报告 #
176542次浏览 1066人参与
# 面试被问第一学历差时该怎么回答 #
122586次浏览 765人参与
# 电网笔面经互助 #
31644次浏览 317人参与
# 为什么那么多公司毁约 #
163470次浏览 1223人参与
# 我在牛爱网找对象 #
178396次浏览 1339人参与
# 520告白墙 #
18524次浏览 325人参与
# 找工作的破防时刻 #
25550次浏览 383人参与
# 实习学不到东西怎么办？ #
203774次浏览 2113人参与
# 2023届毁约公司名单 #
190377次浏览 938人参与
# 通信硬件知识分享 #
25550次浏览 460人参与
# 实习/项目/竞赛奖项，哪个对找工作更重要？ #
80328次浏览 1102人参与
# 腾讯音乐求职进展汇总 #
86275次浏览 484人参与
# 25届秋招公司红黑榜 #
259479次浏览 1089人参与
# 如果公司降薪，你会跳槽吗？ #
65665次浏览 515人参与
# 我想象的实习vs现实的实习 #
277613次浏览 2207人参与
# 我发现一个规律 #
3226次浏览 31人参与
牛客网
牛客企业服务