004 - 牛客大厂春招笔试001
苦练算法题，只为进面，唉。
编程题
小红的字母填写
题目
小红拿到了一排格子，每个格子的背景是红色或者蓝色。
小红希望你将每个格子上填写一个小写字母，需要满足相同的字母的背景颜色是相同的。
小红希望最终出现次数最多的字母的出现次数尽可能小。你能帮帮她吗？
输入描述：
一个仅由字符'0'和'1'组成的字符串，长度不超过200000。
字符串用于表示小红拿到的格子的颜色。第个字符为'0'代表第第个格子为蓝色背景，字符'1'代表红色背景。
输出描述：
一个仅由小写字母构成的字符串，第个字符为第个格子上填写的字母，请务必保证字符串是合法的。如果有多解，输出任意即可。
示例1
输入例子：
010
输出例子：
abc
例子说明：
'a'为蓝色，'b'为红色，'c'为蓝色。三种字母均只出现了一次
示例2
输入例子：
000000000000000000000000001
输出例子：
bbcdefghijklmnopqrstuvwxyza
例子说明：
我们这个填空方案中，两个'b'都是蓝色，符合题目要求。除了'b'出现2次以外，其余的字母均只出现了1次。
解析
求0和1的用于分配26个字母的比例，然后轮流进行分配。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
string str;
cin >> str;
int zeroCnt = 0, oneCnt = 0;
for (char ch : str)
{
if (ch == '0')
{
++zeroCnt;
}
else {
++oneCnt;
}
}
cerr << "ZeroCnt: " << zeroCnt << endl;
cerr << "OneCnt:" << oneCnt << endl;
int zeroRadio = ceil(static_cast<float>(zeroCnt) / static_cast<float>(zeroCnt + oneCnt) * 25);
int oneRadio = ceil(static_cast<float>(oneCnt) / static_cast<float>(zeroCnt + oneCnt) * 25);
if (zeroCnt == 0)
oneRadio = 26;
else if (oneCnt == 0)
zeroRadio = 26;
int zeroOffset = 0;
int oneOffset = zeroRadio;
for (char ch : str)
{
if (ch == '0')
{
cout << static_cast<char>('a' + zeroOffset);
++zeroOffset;
if (zeroOffset >= zeroRadio)
{
zeroOffset = 0;
}
}
else
{
cout << static_cast<char>('a' + oneOffset);
++oneOffset;
if (oneOffset >= 26)
{
oneOffset = zeroRadio;
}
}
}
}
反思
我烂完了，这都想了快一小时。顺便，牛客OJ上可以用cerr进行DEBUG！。
小美的外卖订单编号
题目
美团商家的订单发起时，订单编号最开始从 1 开始，后续每发起一个订单，订单编号便在上一订单编号的基础上 +1。为了防止订单号过大，商家还可以设置一个编号上限m，当订单编号超过m时，将又从 1 开始编号。 小美想知道，当订单编号上限为m时，第x个订单编号是多少？将有q次询问。
输入描述：
第一行输入一个整数。
接下来行，每行两个整数。
输出描述：
行，每行一个整数表示答案。
示例1
输入例子：
4
2 3
5 17
8 2
4 4
输出例子：
1
2
2
4
解析
使用模运算即可，但注意模为0的情况：例如要获得上限2的第四个订单，1 2 1 2应该是2。
#include <iostream>
using namespace std;
int main() {
int q;
cin >> q;
while (q--)
{
int m, x;
cin >> m >> x;
if (x > m)
{
x = (x % m == 0) ? m : (x % m);
}
cout << x << endl;
}
}
// 64 位输出请用 printf("%lld")
小美种果树
题目
小美在手机上种果树，只要成熟了就可以领到免费的水果了。
小美每天可以给果树浇水，果树的成长值加 xx。同时也可以给果树施肥，两次施肥至少需要间隔 2 天，果树的成长值加 yy。果树成长值达到 zz 就成熟了。
小红想知道，最少需要多少天可以领到免费的水果。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
输入描述：
一行三个整数 ，分别表示浇水的成长值，施肥的成长值，果树成熟的成长值。
输出描述：
一行一个整数，表示最少需要多少天可以领到免费的水果。
示例1
输入例子：
1 2 10
输出例子：
6
例子说明：
第一天施肥浇水，成长值为 3。
第二天浇水，成长值为 3 + 1 = 4。
第三天浇水，成长值为 4 + 1 = 5。
第四天施肥浇水，成长值为 5 + 3 = 8。
第五天浇水，成长值为 8 + 1 = 9。
第六天浇水，成长值为 9 + 1 = 10。
果树成熟了，可以领到免费水果了！
解析
模拟题，注意处理浇水间距：
#include <iostream>
using namespace std;
int main()
{
int x, y, z;
cin >> x >> y >> z;
int lastWaterDay = -3;
int day = 0;
int score = 0;
while (score < z)
{
cerr << "Day " << day;
if (day - lastWaterDay == 3)
{
lastWaterDay = day;
cerr << " water, ";
score += y;
}
cerr << "fuel\n";
score += x;
++day;
}
cout << day;
}
// 64 位输出请用 printf("%lld")
小美的数组构造
题目
解析
应该使用动态规划来解题，dp[i][j]的含义是前i个数之和为j的总方案数，状态转移方程为dp[i][j] = dp[i - 1][j - k1] + dp[i - 1][j - k2]...。其中，为了满足条件1，有k != a[i - 1]。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
constexpr int MOD = 1e9 + 7;
int main() {
int n;
cin >> n;
int targetSum = 0;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
targetSum += a[i];
}
// dp[i][j]: 前i个数之和为j 的构造方案数
// dp[i][j] = dp[i - 1][j - k1] + dp[i - 1][j - k2] + ...
vector<vector<int>> dp(n + 1, vector<int>(targetSum + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= targetSum; ++j)
{
for (int k = 1; k <= j; ++k)
{
if (k != a[i - 1])
{
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
}
}
}
}
cout << dp[n][targetSum];
}
// 64 位输出请用 printf("%lld")
反思
唉，不看别人解析写不出来。
小球投盒
题目
解析
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int ans = 0;
set<int> doOp1, doOp2;
while (m--)
{
++ans;
int op, x;
cin >> op >> x;
if (op == 1)
{
doOp1.insert(x);
// insert(x)后, 都有球 ||
// insert(x)后, 并且除了x都有球
if (doOp1.size() >= n || doOp2.count(x))
{
cout << ans;
return 0;
}
}
else
{
doOp2.insert(x);
// 除了y,其他都有一个球, 并且insert(x)后除了x, 其他都有一个球 ||
// 除了x, 其他都有一个球,并且x有球
if (doOp2.size() > 1 || doOp1.count(x))
{
cout << ans;
return 0;
}
}
}
cout << -1;
}
// 64 位输出请用 printf("%lld")
反思
唉，阅读理解能力不行。
小美的树上染色
题目
解析
这道题是树形DP类型：
dp[u][0]：不染色节点u的情况下，染色节点数最大值；dp[u][1]：染色节点u的情况下，染色节点数最大值。
然后是状态转移方程：
dp[u][0] += max(dp[i][0], dp[i][1])，其中i和u在一个图中。不染色u的情况下，染色节点数最大值为它周围子节点的染色节点数最大值之和。dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[i][0], dp[i][1]) + dp[i][0] + 2)，其中i和u在一个图中。染色u的情况下，染色节点数最大值需要好好解释。由于题中限制若当前节点染色，那么它相邻的节点只能有一个染色，因此我们需要选择一个相邻节点，使得染色节点数最大。接下来是计算，在节点U不染色且节点I不染色（dp[u][0] - max(dp[i][0], dp[i][1]) + dp[i][0]）的情况下，将两个节点都染色（+2）。
代码如下：
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
using namespace std;
struct Graph
{
vector<int> value;
vector<list<int>> g;
Graph(int n)
{
value.resize(n + 1);
g.resize(n + 1);
}
};
int main() {
int n;
cin >> n;
Graph graph(n);
for (int i = 1; i <= n; ++i)
{
cin >> graph.value[i];
}
for (int i = 0; i < n - 1; ++i)
{
int from, to;
cin >> from >> to;
graph.g[from].push_back(to);
graph.g[to].push_back(from);
}
// 树形DP:
// dp[u][0]: 不染红u情况下, 染红节点数最大值
// dp[u][0] = sum(max(dp[i][0], dp[i][1]), ...), 其中i和u在一个图中
// dp[u][1]: 染红u情况下, 染红节点数最大值
// dp[u][1] = max(dp[u][0] - max(dp[i][0], dp[i][1]) + dp[i][0] + 2), 其中i和u在一个图中
// U不染色 且 I不染色的情况下, 让U和I染色
vector<vector<int>> dp(n + 1, vector<int>(2));
auto DFS = [&](auto&& DFS, int u, int parent) -> void
{
// 先求dp[u][0]
for (int i : graph.g[u])
{
// 防止重复求值
if (parent == i)
{
continue;
}
DFS(DFS, i, u);
dp[u][0] += max(dp[i][0], dp[i][1]);
}
// 再求dp[u][1]
for (int i : graph.g[u])
{
// 防止重复求值
if (parent == i)
{
continue;
}
int root = static_cast<int>(sqrt(graph.value[i] * graph.value[u]));
if (root * root == graph.value[i] * graph.value[u])
{
dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[i][0], dp[i][1]) + dp[i][0] + 2);
}
}
};
DFS(DFS, 1, 0);
cout << max(dp[1][0], dp[1][1]);
}
// 64 位输出请用 printf("%lld")
在代码实现中，需要注意的是将子节点和父节点进行比较，避免进行重复计算导致超时，或者结果错误。
反思
同样是不看题解写不出来，需要反复练习。。。