美团2021笔试通用卷08

美团2021笔试通用卷08

美团的题真的一如既往有水平 太难了

01 - 小美的暑假

小美的书架上有很多书。小美是个爱读书的新时代好青年。 小团虽然也喜欢看书，但小团大多数时候都更喜欢来小美家蹭书读。 这就导致小美的书架上很多书都会被小团借走。 小美很烦这一点，就想出了一个招数，小美的书架是一行一行的，他会对一些行加锁，这样小团就借不走了。 现在小团想要借书，请你帮忙看看小团能不能借到书，如果可以借到的话在哪一行书架上有这本书。 为了简单起见，每本书将用一个正整数进行编号，小美的书架一共有N行。

---

这题模拟题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std;
int n, m, T;

vector<int> shelf;
vector<bool> isonshelf, locker, ismei;

void add(int a, int b)
{
    if(!ismei[a] ||locker[shelf[a]] || locker[b])
        return;
    isonshelf[a] = true;
    ismei[a] = true;
    shelf[a] = b;
}
void lockered(int a)
{
    locker[a] = true;
}
void unlockered(int a)
{
    locker[a] = false;
}
int borrow(int a)
{
    if(!isonshelf[a] || locker[shelf[a]]) return -1;
    isonshelf[a] = false;
    ismei[a] = false;
    int ans = shelf[a];
    shelf[a] = 0;
    return ans;
}
void getback(int a)
{
    ismei[a] = true;
}
int main()
{
    scanf("%d%d%d", &n, &m, &T);
    shelf = vector<int>(2 * n + m + 10, 0); 
    isonshelf = vector<bool>(2 * n + m + 10, false);
    ismei = vector<bool>(2 * n + m + 10, true);
    locker = vector<bool>(2 * n + m + 10, false);
    while(T--)
    {
        int op, a, b;
        scanf("%d%d", &op, &a);
        if(op == 1)
        {
            scanf("%d", &b);
            add(a, b);
        } else if (op == 2)
        {
            lockered(a);
        } else if (op == 3)
        {
            unlockered(a);
        } else if(op == 4)
        {
            cout << borrow(a) << endl;
        } 
        else if (op == 5){
            getback(a);
        }
    }
    return 0;
}

02 - 偏爱字母

小美喜欢字母E，讨厌字母F。在小美生日时，小团送了小美一个仅包含字母E和F的字符串，小美想从中选出一个包含字母E数量与字母F数量之差最大的子串。

*子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如abcab是fabcab的子串，而不是abcad的子串。我们将空串看作所有字符串的子串。

---

最大连续子序列和 -> 最大的前缀和 和最小的前缀和之差 就是最大的连续子序列和

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    vector<int> f(n + 1);
    // 1. 預處理前綴和
    for(int i = 1; i <= n; i++)
    {
        if(s[i - 1] == 'E')
            f[i] = f[i - 1] + 1;
        else
            f[i] = f[i - 1] - 1;
    }
    int res = 0, minv = 0;
     
    for(int i = 0; i <= n; i++)
    {
        res = max(res, f[i] - minv);
        minv = min(minv, f[i]);
    }
    cout << res << endl;
    return 0;
}

03 - 搭配出售

服装店新进了a条领带，b条裤子，c个帽子，d件衬衫，现在要把这些搭配起来售卖。有三种搭配方式，一条领带和一件衬衫，一条裤子和一件衬衫，一个帽子和一件衬衫。卖出一套领带加衬衫可以得到e元，卖出一套裤子加衬衫可以得到f元，卖出一套帽子加衬衫可以得到g元。现在你需要输出最大的获利方式;

---

这题 看起来是分组背包 实际上是多重背包 这里以衬衫的数量作为体积（因为每一组都是用到衬衫） 这里多重背包的二进制优化复习一下

while(cin >> a >> b >> s)
{
    int k = 1;
    while(k <= s)
    {
        cnt++;
        w[cnt] = b * k;
        v[cnt] = a * k;
        s -= k;
        k *= 2;
    }
    if(s > 0)
    {
        cnt++;
        w[cnt] = b * s;
        v[cnt] = a * s;
    }
}
// 打包完就是0 1 背包了
for(int i = 1; i <= cnt; i++)
    for(int j = V; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

#include <iostream>
#include <algorithm>
#include <cstring>
  
using namespace std;
using LL = long long;
const int N = 1000010;
LL dp[N];
LL w[N], v[N];
int tmps[4], tmpw[4];
int n = 3, V, cnt = 0;;
  
int main()
{
      
    int a, b, c, d, e, f, g;
    cin >> a >> b >> c >> d >> e >>f >>g;
    V = d; // 以
    tmps[0] = a, tmpw[0] = e;
    tmps[1] = b, tmpw[1] = f;
    tmps[2] = c, tmpw[2] = g;
    for(int i = 0; i < n; i++)
    {
        int ia, ib, is;
        ia = 1, ib = tmpw[i], is = tmps[i];
        LL k = 1;
        while(k <= is)
        {
            cnt++;
            v[cnt] = (LL)ia * k;
            w[cnt] = (LL)ib * k;
            is -= k;
            k *= 2;
        }
        if(is > 0)
        {
            cnt ++;
            v[cnt] = (LL)ia * is;
            w[cnt] = (LL)ib * is;
        }
  
    }
    // 轉化為多重背包問題
    for(int i = 1; i <= cnt; i++)
        for(int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;
    return 0;
}

04 - 十字路口

在小美和小团生活的城市中，有n行m列共计nm个十字路口，第i行j列的十字路口有两个属性aij，b­ij。当行人处在i行j列的路口，对于任意非负整数k: 当时间处在[k*aij+k*b­ij), (k+1)*aij+k*bij)时，行人可以选择走到i±1行j列的路口。 当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*b­ij)时，行人可以选择走到i行j±1列的路口。 每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于nm个路口当中。可以选择原地静止不动。 在第0时刻，小美处在xs行ys列的十字路口处，要去xt行yt列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?

---

哇这题真的是学到了 这题很有水平

开始以为这种带时间的最短路只能搜索（搜索的只能过40%）来着 后来发现其实并非依赖整个路程的时间 只是依赖上一个状态的时间而已-> 完全可以利用最短路的解法来做这个题 只不过路径权值并非固定 要根据从上一个状态转移来的计算

简单来说 这里的路径长度就是时间 学到了 第一次做这样的题555

如果在这个时间区间内（这里用余（ai + bi)来计算) 可以直接转移 不然就得等一会到下个区间的起点 （这里最优性应该是显然的）

这里等的时间一个是0-> 直接可以走 要么就是区间端点减去当前余值-> 最优的等待值

最短路的框架就用Dijktra好了

很有水平的一道题 最近做题学到最多的一道了（流泪）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;
int n, m, sx, sy, ex, ey;
int a[N][N], b[N][N], s[N][N];
bool st[N][N];
int dist[N][N];
int dx[2] = {1, -1}, dy[2] = {1, -1};

struct Node
{
    int x, y, dist;
    Node( ) : x(0), y(0), dist(0) {}
    Node(int _x, int _y, int _dist) : x(_x), y(_y), dist(_dist) {}

    bool operator<(const Node& t) const{
        return dist > t.dist;
    }
};
priority_queue<Node> q;
void add_x(int x, int y, int distance, int cost)
{
    for(int i = 0; i < 2; i++)
    {
        int nx = x + dx[i];
        if(nx <= 0 || nx > n) continue;
        if(dist[nx][y] > distance + cost+ 1)
        {
            dist[nx][y] = distance+cost + 1;
            q.emplace(nx, y, distance+cost + 1);
        }
   }
}

void add_y(int x, int y, int distance, int cost)
{
    for(int i = 0; i < 2; i++)
    {
        int ny = y + dy[i];
        if(ny <= 0 || ny > m) continue;
        if(dist[x][ny] > distance + cost+ 1)
        {
            dist[x][ny] = distance+cost + 1;
            q.emplace(x, ny, distance+cost + 1);
        }
   }
}
int main()
{
    memset(dist, 0x3f, sizeof dist);
    scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] += a[i][j];
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &b[i][j]);
            s[i][j] += b[i][j];
        }
    
    dist[sx][sy] = 0;
    q.emplace(sx, sy, 0);
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int x = t.x, y = t.y, distance = t.dist;
        if(st[x][y]) continue;
        st[x][y] = true;
        // 扩展
        if(distance % (s[x][y]) < a[x][y])
        {
            // 上下
            add_x(x, y, distance, 0);
            // 左右 -> 等到可以转移的时候
            int cost = a[x][y] - distance % (s[x][y]);
            add_y(x, y, distance, cost);
        } else{
            add_y(x, y, distance, 0);
            int cost = s[x][y] - distance %(s[x][y]);
            add_x(x, y, distance, cost);
        }
    }
    cout << dist[ex][ey] << endl;
    return 0;
}