小马智行笔试第二批ak经

有什么问题可私

因为看到队友在牛客认识了很多小伙伴，所以也来写写笔试经了

擅长ak各种笔试并挂各种面试，这次ak的慢了些(滑稽保命)，50min，最后一个题有个地方写错了多花了点时间

q 2271277728

// 排个序 还用想？ 因为是平方呀 
#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;
}

// 这题可能有点麻烦？   首先求最小肯定可以二分 
// 主要是看枚举每个字母看一段区间里面有没有  我直接用前缀和差的， 这样写起来方便些
// 其实也可以直接记录一个最尾部的字母位置来判断 
#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;
}

//  这个题比较明显，其实一开始想的是并查集，但一想不就是个联通分量吗，直接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)

小马智行笔试第二批ak经

全站热榜