2022-08-06-美团笔试-无算法存模拟-约82分

3个多选20分：

1. 哪些是优化算法：牛顿法、拉格朗日法、梯度下降法、共轭梯度法（全选？）

2. 错误的是：

   最常用的核函数是高斯核，
   可以认为高斯核在执行一种模板匹配。训练标签y相关的训练样本x变成了类别y的模板。当测试点x'到x的欧几里得距离很小，对应的高斯核相应很大时，表明x'和模板x非常相似。（正确）
   核技巧表现好其一是因为能使用保证有效收敛的凸优化学习非线性模型，优化算法可以将决策函数视为不同空间中的线性函数
   核技巧表现好其二是因为其实现方法比直接构建再算点积高效很多（正确）

3. 正确的是：ac
   非参数估计

        可用于任意分布
        需要预设观测数据符合某数学模型
        不需要假定数学模型
        包括最大似然估计

1. x个a，y个b，2a1b或者 1a2b拼成一盒，最多拼成多少盒

#include
using namespace std;

int main(){
  int t=0;cin>>t;
  int x,y;
  while(t--){
    cin>>x>>y;
    if(x>y){
      swap(x,y);
    }
    int c=0;
    if(2*x<=y){
      cout<<x<<"\n";
    }
    else{
      int q=(2*x-y)/3;
      int p=min(x-2*q,(y-q)/2);
      cout<<min(q+p,(x+y)/3)<<"\n";
    }
  }
  return 0;
}

2. 
#include
#include
using namespace std;

int main(){
  int t=0;cin>>t;
  vector a(t);
  for(int i=0;i<t;i++)
    cin>>a[i];
  int zeros=0;
  vector pospre(t,0);
  vector negpost(t,0);
  if(a[0]>0) pospre[0]=1;
  if(a[t-1]<0) negpost[t-1]=1;
  if(a[0]==0) zeros=1;
  for(int i=1;i<t;i++){
    pospre[i]=a[i]>0?pospre[i-1]+1:pospre[i-1];
    negpost[t-1-i]=a[t-i-1]<0?negpost[t-i]+1:negpost[t-i];
    if(a[i]==0) zeros++;
  }
  int minI=min(negpost[0],pospre[t-1]);
  for(int i=0;i<t-1;i++){
    minI=min(minI,pospre[i]+negpost[i+1]);
  }
  cout<<minI+zeros;
  return 0;
}

3. 
#include
#include
#include
using namespace std;

int main(){
  int n;cin>>n;
  vector a(n,0);
  vector b(n,0);
  unordered_map c;
  for(int i=0;i<n;i++){
    cin>>a[i];
    c[a[i]]++;
  }
  for(int i=0;i<n;i++){
    cin>>b[i];
    c[b[i]]++;
  }
  vector z;
  for(auto& [v,cnt]:c){
    if(cnt>=(n+1)/2)
      z.push_back(v);
  }
  if(z.size()==0){
    cout<<"-1";
  }
  else{
    int minr=(n+1)/2;
    for(auto i:z){
      int posn=0;
      for(auto j:a){
        if(j==i)
          posn++;
      }
      if(posn>(n+1)/2)
      {
        cout<<0;
        return 0;
      }
      minr=min(minr,(n+1)/2-posn);
    }
    cout<<minr;
  }
  return 0;
}

4. 
#include
#include
#include
#include
using namespace std;

int main(){
  int n, k, t;cin>>n>>k;
  vector> c(k+1,vector(0));
  for(int i=1;i<=n;i++){
    cin>>t;
    c[t].push_back(i);
  }
  vector train,test;
  for(auto& cl:c){
    for(int i=0;i<(cl.size()+1)/2;i++){
      train.push_back(cl[i]);
    }
    for(int i=(cl.size()+1)/2;i<cl.size();i++){
      test.push_back(cl[i]);
    }      
  }
  sort(train.begin(),train.end());
  sort(test.begin(),test.end());
  for(int i=0;i<train.size()-1;i++)
    cout<<train[i]<<" ";
  cout<<train[train.size()-1]<<"\n";
  for(int i=0;i<test.size()-1;i++)
    cout<<test[i]<<" ";
  cout<<test[test.size()-1];
  return 0;
}