竞赛讨论区 > 牛客小白月赛51题解~
头像
沙烬
编辑于 2022-06-04 15:49
+ 关注

牛客小白月赛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;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
京东2019春招京东算法类试卷
百度23届秋招研发岗B卷
图森未来2020校招笔试卷（三）
全部 >
面经
面试常考问题整理
Springboot全套注解解析《看不懂算我输》
0928携程笔试题解
硬件/IC/嵌入式高薪--你应该看看这些公司和岗位
全部 >
内推
员工内推码获取
体验中心实习生招募 - 淘天集团
【美团】校招社招内推，简历免筛，所有岗位，进度可查，消息必回
拼多多暑期实习
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(3) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”