小红书笔试 4.9 算法岗(3/3 附题面)
题面在代码中
A. 平衡
和昨晚的美团笔试差不多，先一遍dfs处理以sz[i], 得到以 i 为根的子树大小，枚举边求答案即可。
/*
小红书 23届补录&24届实习 【24届实习】算法笔试
*/
#include<bits/stdc++.h>
#define debug(x) std::cerr << x << '\n';
#define all(x) x.begin(), x.end()
using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
struct Edge {
int u, v;
} edge[1000005];
vi G[1000005];
int sz[1000005];
void dfs(int u, int par) {
sz[u] = 1;
for (auto v : G[u]) {
if (v == par) {
continue;
}
dfs(v, u);
sz[u] += sz[v];
}
}
int ans[1000005], fa[1000005];
void solve() {
int n;
std::cin >> n;
for (int i = 1; i <= n - 1; i++) {
int u, v;
std::cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
edge[i].u = u, edge[i].v = v;
fa[u] = v;
}
int root = 1;
for (int i = 1; i <= n; i++) {
if (!fa[i]) {
root = i;
}
}
dfs(root, 0);
int res = 1e9;
for (int i = 1; i <= n - 1; i++) {
int u = edge[i].u, father = edge[i].v;
int now = std::abs(sz[u] - (n - sz[u]));
ans[now]++;
res = std::min(res, now);
}
std::cout << res << ' ' << ans[res] << '\n';
}
int main() {
std::cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1;
//std::cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
平衡
时间限制： 1000MS
内存限制： 65536KB
题目描述：
输入一棵树 T，你需要删除一条边，这棵树会被分成A 和 B 两棵树。你需要让两部分的节点数的差的绝对值| |A|-|B| |尽可能小。输出最小的| |A|-|B| |和最优方案的数量。
输入描述
第一行一个整数 n表示节点的数量，节点从1 到 n编号。
接下来n-1行每行两个正整数 s t，表示s的父亲是t。
输入保证是一棵树。
对于所有数据 1<=n<=100000。
输出描述
输出一行，两个整数，用空格分开，分别表示最优解和最优方案数。
样例输入
3
2 1
3 1
样例输出
1 2
*/
B. 配制溶液
要配置体积为V的溶液，可以枚举子状态 i 和 V - i, 其实就是求子状态的最优策略，所以可以递归做，类似于记忆化搜索。
/*
小红书 23届补录&24届实习 【24届实习】算法笔试
*/
#include<bits/stdc++.h>
#define int long long
#define debug(x) std::cerr << x << '\n';
#define all(x) x.begin(), x.end()
using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
int A[1005], B[1005];
int dp[1005][1005];
int Max[1005], f[1005];
int n, X, C;
int dfs(int now) {
if (f[now] != -1) {
return f[now];
}
int ans = 0;
for (int i = 1; i <= now - 1; i++) {
if (!dfs(i) or !dfs(now - i)) {
continue;
}
if (i == now - i) {
ans = std::max(ans, dfs(i) + dfs(now - i) + X);
} else {
ans = std::max(ans, dfs(i) + dfs(now - i));
}
}
return f[now] = std::max(Max[now], ans);
}
void solve() {
memset(f, -1, sizeof(f));
std::cin >> n >> X >> C;
for (int i = 1; i <= n; i++) {
std::cin >> A[i];
}
for (int i = 1; i <= n; i++) {
std::cin >> B[i];
Max[A[i]] = std::max(Max[A[i]], B[i]);
}
for (int i = 1; i <= C; i++) {
std::cerr << i << ' ' << dfs(i) << '\n';
}
std::cout << dfs(C) << '\n';
}
signed main() {
std::cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1;
//std::cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
配制溶液
时间限制： 3000MS
内存限制： 589824KB
题目描述：
实验室需要配制一种溶液。现在，研究员面前有n种该物质的溶液，每一种有无限多瓶，第i种的溶液体积为xi，里面含有yi单位的该物质。研究员每次可以选择一瓶溶液，将其倒入另外一瓶（假设瓶子的容量无限），即可以看作将两个瓶子内的溶液合并。此时合并的溶液体积和物质含量都等于之前两个瓶子内的之和。
特别地，如果瓶子A与B的溶液体积相同，那么A与B合并之后该物质的含量会产生化学反应，使得该物质含量增加X单位。
研究员的任务是配制溶液体积恰好等于C的，且尽量浓的溶液（即物质含量尽量多）。研究员想要知道物质含量最多是多少。
输入描述
第一行三个正整数n,X,C；
第二行n个正整数x1,x2,...,xn，中间用空格隔开；
第三行n个正整数y1,y2,...,yn，中间用空格隔开。
对于所有数据，1≤n,X,C,yi≤1000,1≤xi≤C
数据保证至少存在一种方案能够配制溶液体积恰好等于C的溶液。
输出描述
输出一行一个整数，表示答案。
样例输入
3 4 16
5 3 4
2 4 1
样例输出
29
*/
C. 双色球
有个小坑：当红球在袋子里的时候，每过去一秒上面的数字就会增加1，蓝球上的数字则会减少1。
一开始没注意到，wa了很多次。我们只需要记录当前放了多少个红和蓝，记录编号为id的小球放进去的时间就可以了。
/*
小红书 23届补录&24届实习 【24届实习】算法笔试
*/
#include<bits/stdc++.h>
#define int long long
#define debug(x) std::cerr << x << '\n';
#define all(x) x.begin(), x.end()
using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;
using vl = std::vector<i64>;
int A[500005], B[1000005], C[1000005], in[1000005];
std::string color;
void solve() {
int n;
while (std::cin >> n) {
//std::cin >> n;
i64 sum = 0;
int red = 0, blue = 0;
for (int i = 1; i <= n; i++) {
std::cin >> A[i];
}
std::cin >> color;
color = ' ' + color;
int m;
std::cin >> m;
for (int i = 1; i <= m; i++) {
std::cin >> B[i];
}
for (int i = 1; i <= m; i++) {
std::cin >> C[i];
}
for (int i = 2; i <= m; i++) {
assert(B[i] > B[i - 1]);
}
int Nowtime = 0;
memset(in, -1, sizeof(in));
std::vector<i64> ans;
for (int i = 1; i <= m; i++) {
int TimeDet = B[i] - Nowtime;
sum += red * TimeDet;
sum -= blue * TimeDet;
if (C[i] == 0) {
ans.emplace_back(sum);
} else {
int id = std::abs(C[i]);
if (C[i] > 0) {
assert(in[id] == -1);
sum += A[id];
in[id] = B[i];
red += color[id] == 'R';
blue += color[id] == 'B';
} else if (C[i] < 0) {
sum -= A[id];
sum -= (color[id] == 'R' ? 1 : -1) * (B[i] - in[id]);
A[id] = (A[id] + (color[id] == 'R' ? 1 : -1) * (B[i] - in[id]));
red -= color[id] == 'R';
blue -= color[id] == 'B';
in[id] = -1;
}
}
//std::cerr << i << ' ' << sum << '\n';
Nowtime = B[i];
}
std::cout << ans.size();
for (auto iter : ans) {
std::cout << ' ' << iter;
}
std::cout << '\n';
}
}
signed main() {
std::cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1;
//std::cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小明有一个神奇的袋子和一堆编号为1到n的球。每个球都被涂成了红色或者蓝色，且这些球的表面上都分别写着一个数字。
当红球在袋子里的时候，每过去一秒上面的数字就会增加1，蓝球上的数字则会减少1。
小明会时不时向袋子里放入球或取出球，并且他想知道某些时刻袋子中球上写的数字之和。
输入描述
第一行有一个正整数n(1<=n<=5000)，代表小明有几个球。
第二行有n个范围在[-1000000,1000000]内的整数，第i个代表编号为1到n的球上写的数。
第三行是一个长度为n的仅由`R`和`B`构成的字符串，第i个字母代表编号为i的球是红色(R)或蓝色(B)
第四行有一个正整数m(1<=m<=100000)，代表小明进行了几次操作。
第五行有m个递增的正整数，第i个代表小明进行的第i次操作时间点。每个时间点小明只会进行至多一次操作。时间点的范围在[1,1000000000]内。
第六行有m个整数，第i个代表小明进行的操作。0为询问当前时间点袋中球上的数字之和，正数x代表放入了编号为x的球，负数-x代表取出了编号为x的球。
最开始袋子是空的。 你可以认为球上的数字变化均发生在时间点之前，而每次操作均发生在时间点之后。输入保证操作合法。
输出描述
设小明进行了k次询问。你需要在一行中先输出k，然后输出k个数，第i个代表第i次询问的答案。
题目保证小明进行过至少一次询问。
样例输入
3
-5 4 6
RBR
9
1 2 3 4 5 6 8 13 14
1 3 0 2 -3 0 -1 0 -2
样例输出
3 4 2 -5
3
1 1 1
RRB
4
1 2 3 10
1 3 -1 0
*/
#小红书##小红书实习招聘##小红书笔试##软件开发2023笔面经##小红书信息集散地#一些比赛的题解 文章被收录于专栏
一些比赛的题解
