美团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，bij。当行人处在i行j列的路口，对于任意非负整数k: 当时间处在[k*aij+k*bij), (k+1)*aij+k*bij)时，行人可以选择走到i±1行j列的路口。 当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij)时，行人可以选择走到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;
}