牛客小白月赛37 选做

太菜了，做不来题，来冲一篇题解……

B

因为概率独立且相同，故猜中的期望次数为 $1/E$ ， $E$ 表示单次猜中概率。

C

没看懂，弃了。。。

E

并不会构造。
观察到两种字符串加起来即为 R，P 个数乘积。
那么取尽量靠近 $\sqrt{n+m}$ 的两个数即可。
构造就很简单了。

F

利用对称的思想，以中间的点为中心点对称染色。
这就要求 $n\times m$ 必须为奇数。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
signed main() {
    int n,m;cin>>n>>m;
    if((n*m)&1) cout<<"akai\n";
    else cout<<"yukari\n";
    return 0;
}

G

注意到字符串长度在 64 以内才有解。
那么每次修改时枚举 x-60 到 x+60 更新就完了~
似乎官方题解说这是暴力？！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
const int maxn = 1e5+10;
char S[maxn];int ans,n,L,R;
signed main() {
    n=read(),L=read(),R=read();
    scanf("%s",S+1);
    for(int i=1;i<=n;i++) if(S[i]!='0')
        for(int j=i,r=0;j<=min(i+62,n);j++) {
            r=r*2+S[j]-'0';
            if(L<=r&&r<=R) ++ans;
            if(r>R) break;
        }
    int q=read();
    for(int _=q,x;_;_--) {
        x=read();
        for(int i=max(x-62,1ll);i<=min(x+62,n);i++) if(S[i]!='0')
            for(int j=i,r=0;j<=min(x+62,n);j++) {
                r=r*2+S[j]-'0';
                if(L<=r&&r<=R) --ans;
                if(r>R) break;
            }
        S[x]=((S[x]-'0')^1)+'0';
        for(int i=max(x-62,1ll);i<=min(x+62,n);i++) if(S[i]!='0')
            for(int j=i,r=0;j<=min(x+62,n);j++) {
                r=r*2+S[j]-'0';
                if(L<=r&&r<=R) ++ans;
                if(r>R) break;
            }
        cout<<ans<<'\n';
    }
    return 0;
}

I

显然答案具有单调性。
那么考虑二分，以中位数为答案，用前缀和算就完事了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
const int maxn = 1e5+10;
int a[maxn],s[maxn],n,K;
char isok(int mid) {
    int res=1e18;for(int i=mid,j=(i+1)/2+1;i<=n;i++,j++) {
        int t=a[j-1];
        res=min(res,(j-1-(i-mid))*t-(s[j-1]-s[i-mid])+(s[i]-s[j-1])-(i-j+1)*t);
    }return res<=K;
}
signed 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++) s[i]=s[i-1]+a[i];
    int l=1,r=n,ans=0,mid;
    while(l<=r)
        if(isok(mid=l+r>>1)) l=(ans=mid)+1;
        else r=mid-1;
    cout<<ans<<'\n';
    return 0;
}

J

模拟即可。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
signed main() {
    string s;getline(cin,s);
    for(int i=0;i<s.length()-3;i++) cout<<s[i];
    return 0;
}