首页 > 笔经面经 > 小马智行笔试第二批ak经

小马智行笔试第二批ak经

头像
lduhengheng #2021届秋招进度交流#
发布于 2021-09-26 21:32:44 APP内打开
赞 3 | 收藏 17 | 回复4 | 浏览1043
有什么问题可私
因为看到队友在牛客认识了很多小伙伴,所以也来写写笔试经了
擅长ak各种笔试并挂各种面试,这次ak的慢了些(滑稽保命),50min,最后一个题有个地方写错了多花了点时间
q 2271277728
1
// 排个序 还用想? 因为是平方呀 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,n) for(ll i=j;i<=n;i++)
const int maxx=1e5+7;
ll a[maxx];
ll n,m,p;
int main(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=1;i<n;i++){
        ans+=(a[i+1]-a[i])*(a[i+1]-a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

2
// 这题可能有点麻烦?   首先求最小肯定可以二分 
// 主要是看枚举每个字母看一段区间里面有没有  我直接用前缀和差的, 这样写起来方便些
// 其实也可以直接记录一个最尾部的字母位置来判断 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,n) for(ll i=j;i<=n;i++)
const int maxx=1e5+7;
char a[maxx];
int sum[28][maxx];
ll n,m,p;
int judge(int x){
    ll pos=0;
    for(int j=1;j<=26;j++){
        ll posl=0;
        int num=0;
        rep(i,x,n)
        {
            if(sum[j][i]-sum[j][i-x] >=1 ) num++;
        }
        if(num == n-x+1) return 1;
    }
    return 0;
    
}
int main(){
    scanf("%s",a+1);
    n=strlen(a+1);
    rep(i,1,n){
        int p=a[i]-'a'+1;
        rep(j,1,26) sum[j][i]=sum[j][i-1];
        sum[p][i]++;
    } 
    
    ll l=1,r=n;
    ll ans=n;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(judge(mid)){
            ans=min(ans,mid);
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    
    return 0;
}
3
//  这个题比较明显,其实一开始想的是并查集,但一想不就是个联通分量吗,直接dfs即可 
//    每次dfs 找到所有人中最小权值的加上就行
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,n) for(ll i=j;i<=n;i++)
const int maxx=1e5+7;
const int inf=1e9+7;
int a[maxx];
vector<int>v[maxx];
ll n,m,p;
int fa[maxx];
int vis[maxx];
int num=inf;
void dfs(int x){
    num=min(num,a[x]);
    vis[x]=1;
    for(auto e:v[x]){
        if(!vis[e]){
            dfs(e);
        }
    }
}

int main(){
    cin>>n>>m;
    rep(i,1,n) cin>>a[i];
    memset(vis,0,sizeof(vis));
    rep(i,1,m){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ll ans=0;
    rep(i,1,n){
        if(!vis[i]) {
            num=inf;
            dfs(i);
            ans+=num;
        }
    }
    cout<<ans<<endl;
    return 0;
}

4.  这个题我喜欢
首先根据第二个样例就能发现难点在哪里
到底在哪里呢?
1 1 1 1
前两个[1,1] 可以和后两个[1,1] 组合
也就是说前面如果有一段 合法组合 后面也有一段合法组合 ,那么就能合并
如何合并呢?
我们先想不合并的:
    如果以i为起点的话,后面的选择是不是c(n-i,a[i])  (组合数从i+1到n中选a[i]个 )
加上合并不合法的就是 :
    从i开头选一个第一段的结束位置  ,假设这个位置是j , 那么以i开头的方案数 就是(i到j)的方案数 *(后面以j+1,j+2,j+3.....开头的方案数+1)
组合数用的打表 加 乘法逆元,大家没acm基础的可以看这个:

当然这题目应该有直接计数dp的写法,我感觉我的思路比较明显就直接写了
#include<bits/stdc++.h> using namespace std;
#define ll long long
#define rep(i,j,n) for(ll i=j;i<=n;i++)
const int maxx=1e5+7;
const ll mod=998244353;
ll a[maxx];
ll n,m,p;
ll dp[maxx];
ll sum[maxx];
ll fic[maxx];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
ll c(int n,int m){
    if(m==0 || n==0) return 1;
    ll num=qpow(fic[m],mod-2)*qpow(fic[n-m],mod-2)%mod;
    return fic[n]*num%mod  ;
}
int main(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    fic[0]=1;
    rep(i,1,n+2) fic[i]=fic[i-1]*i%mod;
    
    memset(dp,0,sizeof(dp));
    ll ans=0;
    for(int i=n;i>=1;i--){
        if(a[i]<=0) ;
        else {
            int posl=i+a[i];
            for(int j=posl;j<=n;j++){
                ll num=c(j-i-1,a[i]-1);
                // 后面的
                //printf("%d %d %d\n",j-i-1,a[i]-1,num);
                dp[i]=(dp[i] + num*(sum[j+1]+1) )%mod; // 应该是j+1,因为是后面的 这个地方卡了我10分钟
            }
        }
        
        //cout<<dp[i]<<endl;
        sum[i]=(sum[i+1]+dp[i])%mod;
        ans=(ans+dp[i])%mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}






4条回帖

回帖
加载中...
话题 回帖

相关热帖

笔经面经近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐