2023.04.22美团笔试

4.22的美团笔试，题比较简单，写起来像在打abc。

T1

求学分和成绩的加权平均值，照着算进行。

特判一下min{b_i}<60。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Ve(T) vector<T>
/*
小美是个勤奋努力的大学生。小美想要获得奖学金。

小美总共修习了 n 门课程，每门课程都有一个学分 ai ，而这门课小美的成绩是 bi 。

小美所在的学校对于奖学金的评定非常简单：只要所有课程的均分不低于一个给定的标准 X，而且没有任何课程挂科，就可以申请奖学金。

均分是指所有课程的成绩按照学分加权的平均值，而一门课挂科即该课成绩低于60分。

现在小美会给你总共若干次询问，询问在每种课业情况下她能否申请奖学金。


*/
int PX(int Case)
{
  ll n, x;
  cin >> n >> x;
  Ve(int) a(n), b(n);
  for(auto &i:a) cin >> i;
  for(auto &i:b) cin >> i;
  ll s1=0, s2=0;
  for(int i=0; i<n; i++) {
    if(b[i] < 60) return cout << "No\n", 0;
    s1 += (a[i]*b[i]);
    s2 += a[i];
  }
  // s1 / s2 >= x
  // s1 >= x*s2
  ll res = s2*x;
  if(s1 >= res) return cout << "Yes\n", 0;
  else return cout << "No\n", 0;
  return 1;
}

int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  for(int t=1; t<=T; t++) {
    PX(t);
  }
  return 0;
}

T2

显然是第k大和第k小匹配，排序扫一遍。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Ve(T) vector<T>
#define all(T) T.begin(),T.end()
/*
小美需要制作一个骰子。

与一般的六面骰子不同，小美需要的骰子总共有 n 面，而且每一面的数字也不同于一般的，这n面的数字需要分别是a1,a2,......an 。当然，骰子是一个正n面体，而且唯一合法的要求是所有相对的两面之和都需要相等，比如一个数字分别为 1,2,3,4,2,3 的六面骰子，那么上面1，下面4，前面2，后面3，左边2，右边3就是合法的方案。

因为方案可以很多，所以小美并不在乎究竟是怎么做出这样一个骰子，小美只想知道是否能做出一个合法的骰子。

当然，保证n为偶数。


*/
int PX(int Case)
{
  int n;
  cin >> n;
  Ve(int) v(n);
  for(auto &i:v) cin >> i;
  sort(all(v));
  int s = v[0] + v[n-1];
  int l=1, r=n-2;
  while(l<r) {
    if(v[l]+v[r] != s) return cout << "NO\n", 0;
    l++, r--;
  }
  cout << "YES\n";
  return 1;
}

int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  for(int t=1; t<=T; t++) {
    PX(t);
  }
  return 0;
}

T3

每种作物的价值是b_i-a_i，花费是t_i，完全背包跑一遍。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Ve(T) vector<T>
#define all(T) T.begin(),T.end()
/*
小美最近在玩一个种田类游戏。

这个游戏的目的是赚尽可能多的钱，游戏中有 n 种作物，其中第 i 种作物从种植到作物成熟采摘需要 ti 天时间，种子买入价格为ai ，作物卖出价格为 bi（一个种子只会产出一个作物，种子可以重复购买）。 而游戏内总时间为 m 天，作物的种子种植和采摘、卖出等不耗时间，成熟之前作物没有价值。

假设小美只有一块土地（即每个时间只能有一个作物在生长），初始的钱足够多，小美想知道她最多能赚多少钱。


*/
int PX(int Case)
{
  int n, m;
  cin >> n >> m;
  Ve(int) t(n), a(n), b(n), v(n);
  for(auto &i:t) cin >> i;
  for(auto &i:a) cin >> i;
  for(auto &i:b) cin >> i;
  for(int i=0; i<n; i++) {
    v[i] = b[i] - a[i];
  }
  Ve(int) dp(m*10);
  for(int i=0; i<n; i++) {
    for(int j=t[i]; j<=m; j++) {
      dp[j] = max(dp[j], dp[j-t[i]] + v[i]);
    }
  }
  int ans = 0;
  for(int i=0; i<=m; i++) ans = max(ans, dp[i]);
  cout << ans << '\n';
  return 1;
}

int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  // cin >> T;
  for(int t=1; t<=T; t++) {
    PX(t);
  }
  return 0;
}

T4

先特判全删和不删的情况，再考虑部分保留。

枚举保留s_i，考虑前缀i-1和后缀i+1，预处理dp然后取最小。

pre_dp[i][0]：前i个前缀去掉的最小费用

pre_dp[i][1]：第i个保留的最小费用

取min(pre_dp[i-1][1],pre_dp[i-1][0])即可。

suf_dp同理。

有更短的写法，无脑dp比较显然也好写。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Ve(T) vector<T>
#define all(T) T.begin(),T.end()
/*
小美给你一个长度为 n 的01串（仅包含字符0和1的串），你可以删除这个串的一个前缀和一个后缀（可以为空），即保留一个原串的连续子串，操作之后整个串的代价为下面两部分之和：

1. 被删除的字符1的个数；

2. 剩下的子串的字符0的个数

你需要最小化操作的代价，并将其输出。

输入仅一行，一个长度为 n 的01字符串。

对于所有数据，1≤n≤105

101110110
  111011
*/
int PX(int Case)
{
  string s;
  cin >> s;
  int n = s.size();
  Ve(int) pre_0(n+3, 0), pre_1(n+3, 0);
  for(int i=1; i<=n; i++) {
    pre_0[i] = pre_0[i-1] + (s[i-1]=='0');
    pre_1[i] = pre_1[i-1] + (s[i-1]=='1');
  }
  Ve(int) suf_0(n+3, 0), suf_1(n+3, 0);
  for(int i=n; i>0; i--) {
    suf_0[i] = suf_0[i+1] + (s[i-1]=='0');
    suf_1[i] = suf_1[i+1] + (s[i-1]=='1');
  }
  vector<vector<int>> pre_dp(n+3, Ve(int)(2, 0));
  for(int i=1; i<=n; i++) {
    pre_dp[i][0] = pre_1[i];
    pre_dp[i][1] = min(pre_dp[i-1][0], pre_dp[i-1][1]) + (s[i-1]=='0');
  }
  vector<vector<int>> suf_dp(n+3, Ve(int)(2, 0));
  for(int i=n; i>=1; i--) {
    suf_dp[i][0] = suf_1[i];
    suf_dp[i][1] = min(suf_dp[i+1][0], suf_dp[i+1][1]) + (s[i-1]=='0');
  }
  int ans = min(pre_1[n], pre_0[n]);
  for(int i=1; i<=n; i++) {
    //  保留i 考虑pre[i-1] 和 suf[i+1]
    int l = min(pre_dp[i-1][0], pre_dp[i-1][1]);
    int r = min(suf_dp[i+1][0], suf_dp[i+1][1]);
    int res = l+r + (s[i-1]=='0');
    ans = min(ans, res);
  }
  cout << ans << '\n';
  return 1;
}

int main()
{
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  // cin >> T;
  for(int t=1; t<=T; t++) {
    PX(t);
  }
  return 0;
}

T5

数据很小，照着题意模拟一下就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Ve(T) vector<T>
#define all(T) T.begin(),T.end()
#define pii pair<int,int>
/*
小美正在参加一个比赛。

这个比赛总共有 2k 个人参加（包括小美），编号为1,2,...,2k，开始的时候所有人都在同一个小组。比试的规程如下：假设当前小组有 n 个人（n 为偶数），那么编号大小前 n/2 人分为一个新的小组，后 n/2 人分为一个新的小组，然后两个小组内部分别比试，决出各自的胜者，然后两个小组的胜者进行比试，胜者作为当前小组的优胜者，直到决出最初的小组的优胜者。当然一个人的小组优胜者肯定是他自己。例如如果当前小组有 4 个人，编号为1,2,3,4，那么就会将 1,2 分为一组，3,4分为一组分别比试，然后 1,2 中的胜者和 3,4 中的胜者再进行比试，决出整个小组的胜者。

由于每个人的能力各不相同，小美预测了所有人两两比试时的胜者，现在小美想知道预测最终的胜者是谁。
*/
int PX(int Case)
{
  int n;
  cin >> n;
  map<pii,int> mp;
  for(int i=1; i<=(1<<n); i++) {
    for(int j=1; j<=(1<<n); j++) {
      int x;
      cin >> x;
      mp[{i, j}] = x;
    }
  }
  Ve(int) v;
  for(int i=1; i<=(1<<n); i++) v.push_back(i);
  while(v.size() > 1) {
    Ve(int) now;
    for(int i=0; i<v.size(); i+=2) {
      int l = v[i], r = v[i+1];
      now.push_back(mp[{l, r}]);
    }
    v = now;
  }
  int ans = v[0];
  cout << ans << '\n';
  return 1;
}

int main()
{
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  // cin >> T;
  for(int t=1; t<=T; t++) {
    PX(t);
  }
  return 0;
}