小马智行笔试第二批ak经
有什么问题可私
因为看到队友在牛客认识了很多小伙伴，所以也来写写笔试经了
擅长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;
} 
腾讯一面1001人在聊