小马智行笔试第二批ak经

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

#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;
}