第20届纪念款-牛客周赛 Round 20 全部题解

A.赝品

考察暴力

我们只需要直接排序不等于最大的数就是赝品即可

void solve()
{
    cin>>n;
    vector<int>a(n);
    for(auto&v:a) cin>>v;
    sort(a.begin(),a.end());
    int cnt=0;
    for(auto&v:a) if(v!=a[n-1]) cnt++;
    cout<<cnt<<endl;
    return ;
}

B.小红的01连续段

考察简单性质

要是最后答案最长的是0,那么我们全部的问号变成0一定是最优的,1同理,也可以用一个虚假的dp看每一位是啥的时候的 最长连续长度

int dp[N][2];

void solve()
{
    string s; cin>>s;
    n=s.size(); s=' '+s;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='?'){
            dp[i][1]=dp[i-1][1]+1;
            dp[i][0]=dp[i-1][0]+1;
        }
        else{
            dp[i][s[i]-'0']=dp[i-1][s[i]-'0']+1;
        }
        ans=max({ans,dp[i][0],dp[i][1]});
    }
    cout<<ans<<endl;
    return ;
}

C.小红的01串构造

考察简单性质

我们可以发现需要t对11至少需要t+1个1全部排列到一起

1.k<t+1 -1

2.接着我们优先排好t+1个1如果还有1就必须隔一个0来放,如果最后长度不够就补0,反之无解

void solve()
{
    cin>>n>>k>>t;
    string s;
    t++;
    k-=t;
    if(k<0){
        cout<<-1<<endl;
        return ;
    }
    while(t--) s+='1';
    while(k--){
        s+='0'; s+='1';
    }
    if(s.size()>n){
        cout<<-1<<endl;
        return ;
    }
    while(s.size()<n) s+='0';
    cout<<s<<endl;
    
    return ;
}

D.小红的数位删除

考察二进制暴力枚举

我们可以发现数位只有9位我们可以直接暴力枚举每个数的删除位置,这里考虑使用二进制暴力枚举比较好

void solve()
{
    int a,b; cin>>a>>b;
    string x=to_string(a),y=to_string(b);
    int cnt1=x.size(),cnt2=y.size();
    int ans=INF;
    for(int i=1;i<1<<cnt1;i++){
        int v=0;
        for(int j=0;j<cnt1;j++){
            if(i>>j&1) v=v*10+(x[j]-'0');
        }
        
        for(int j=1;j<1<<cnt2;j++){
            int w=0;
            for(int k=0;k<cnt2;k++){
                 if(j>>k&1) w=w*10+(y[k]-'0');
             }
             // 防止mod0
             if(v==0 || w==0) ans=min(ans,cnt1-(int)__builtin_popcountll(i)+cnt2-__builtin_popcountll(j));
             else if(v%w==0 || w%v==0){
                 ans=min(ans,cnt1-(int)__builtin_popcountll(i)+cnt2-__builtin_popcountll(j));
             }
        }
    }
    cout<<(ans==INF ? -1 : ans)<<endl;
    return ;

E.小红的漂亮串

考察记忆化搜索

我们明显的发现是一段很长的串当中是否有red和没有der我们可以使用数位dp记录上2个位置是什么上1个位置是什么,最后是否满足有“red”

我们可以这样思考如果当前数位确定同时前面两个字母也确定我们可以依照数位来排可以转移所以不会漏状态

int dp[N][4][4][2];
int dfs(int pos,int u1,int u2,bool ok){
    int &v=dp[pos][u1][u2];// 考虑当前位置是不是会影响后面的位置
    
    if(!pos) return ok;
    if(~v)   return v;
    int  res=0;
    for(int i=0;i<3;i++){
        if(u1==0 && u2==1 && i==2) continue;// 我们按照 d  e  r 映射一手 这个是不合理
        res+=dfs(pos-1,u2,i,ok | (u1==2&&u2==1&&i==0));
        res%=mod;
    }
    res+=23*dfs(pos-1,u2,3,ok);// 其他23个位置是一样的默认为3即可
    res%=mod;
    return v=res;
}

void solve(){
    memset(dp,-1,sizeof dp);
    cin>>n;
    cout<<dfs(n,3,3,0)<<endl;
    return ;
}

F.小红的零

考察思维+树状数组

解析参考代码内部

代码参考咸鱼小孩

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int w[N];
int cnt5[N],cnt2[N];
LL  sum5[N],sum2[N];

LL ct5[N],ct2[N];
LL sm5[N],sm2[N];

void add(LL tr[],int x,LL k){
    for(int i=x;i<=m;i+=lowbit(i)) tr[i]+=k;
}

LL query(LL tr[],int x){
    LL res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        while(x%2==0) cnt2[i]++,x/=2;
        while(x%5==0) cnt5[i]++,x/=5;
        sum2[i]=sum2[i-1]+cnt2[i];
        sum5[i]=sum5[i-1]+cnt5[i];
    }
    
    // 求出前缀2 和  5 的数量
    vector<int> res;
    for(int i=1;i<=n;i++) res.push_back(sum2[i]-sum5[i]);
    
    // 我们假设固定了右端点,对于r 我们考虑左边的区间为[1,r-1],那么我们有两种情况要处理
    // 1. 对于sum5[r]-sum5[l]>=sum2[r]-sum2[l]
    // 我们考虑带来的贡献就是 满足条件的1都数量 y-> y*sum2[r]-这y个sum2[l]的和
    // 进一步推导式子可以变为 sum5[r]-sum2[r]>=sum5[l]-sum2[l]// 满足这个要求的
    // 这个时候我们就是可以来考虑前缀中满足小于这个的数量的 
    // 我们考虑树状数组来维护,同时把每一个位置的数量加入其中考虑到   有负数重复 我们离散处理即可
    
    // 2.对于sum2[r]-sum2[l]>=sum5[r]-sum5[l] 同理变形-> sum2[r]-sum5[r]>=sum2[l]-sum5[l]
    // 接着我们如果按照上面的排序的话就是和2是反过来的情况所以2就是倒着来求即可
    
    sort(res.begin(),res.end());
    
    res.erase(unique(res.begin(),res.end()),res.end());
    
    m=res.size();
    
    int pos=lower_bound(res.begin(),res.end(),0)-res.begin()+1;
    
    // 为什么要加因为考虑前缀和到0的位置
    add(ct2,pos,1ll);
    add(ct5,pos,1ll);
    
    LL ans=0;
    for(int i=1;i<=n;i++){
        int pos=lower_bound(res.begin(),res.end(),sum2[i]-sum5[i])-res.begin()+1;
        ans+=(LL)query(ct5,pos)*sum5[i]-query(sm5,pos);
        ans+=(LL)(query(ct2,m)-query(ct2,pos))*sum2[i]-(query(sm2,m)-query(sm2,pos));
        add(ct2,pos,1ll);
        add(ct5,pos,1ll);
        add(sm2,pos,sum2[i]);
        add(sm5,pos,sum5[i]);
    }
    cout<<ans<<endl;
    return ;
}
signed main ()
{
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
    	 solve();
    }
}