网易后端2022.3.27题解和笔试情况
## 小红杀怪
枚举使用烈焰风暴的次数，然后可以O(1)算出需要使用火球术的次数。总复杂度 $O(n)$
枚举使用烈焰风暴的次数，然后可以O(1)算出需要使用火球术的次数。总复杂度 $O(n)$
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y, a, b, i;
cin >> x >> y >> a >> b;
int ma = 1e9;
for (i = 0; i <= 1e6; i++)
{
int c1 = 0, c2 = 0;
if ((x - i * b) > 0)
c1 = max(c1, (x - i * b) / a + ((x - i * b) % a != 0));
if ((y - i * b) > 0)
c2 = max(c2, (y - i * b) / a + ((y - i * b) % a != 0));
ma = min(ma, i + c1 + c2);
}
cout << ma;
} 这道题数据较小，可以直接暴力dfs。
后面我还想到了O(1)的贪心做法，根据 $x$ 和 $y$ 的大小关系进行分类讨论即可（这样1e9的数据也可以过）：
后面我还想到了O(1)的贪心做法，根据 $x$ 和 $y$ 的大小关系进行分类讨论即可（这样1e9的数据也可以过）：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y, a, b, i;
cin >> a >> b >> x >> y;
if (y >= max(a, b))
cout << 1;
else if (y > x)
{
a = max(a, b);
cout << a / y + (a % y != 0);
}
else if (x > 2 * y)
{
cout << a / x + b / x + (a % x != 0) + (b % x != 0);
}
else
{
if (a > b) swap(a, b);
int cnt = a / y + (a % y != 0);
b -= y * cnt;
cout << b / x + (b % x != 0) + cnt;
}
} 小红标字母
线性dp即可，设 $dp[i]$ 为字符串前 $i$ 项可以获得的最大分数，然后转移。
#include <bits/stdc++.h>
using namespace std;
int dp[201010];
int main()
{
string s;
cin >> s;
int i;
for (i = 1; i < s.length(); i++)
{
dp[i + 1] = dp[i];
if (abs(s[i] - s[i - 1]) <= 1)
{
dp[i + 1] = max(dp[i + 1], dp[i - 1] + (s[i] - 'a' + 1) + (s[i - 1] - 'a' + 1));
}
}
cout << dp[s.length()];
} 小红的完全二叉树构造
题目要求任意两个相邻点乘积是偶数，也就是说不能有两个奇数相邻。我们发现完全二叉树是个二分图，所以让奇数和偶数间隔开，其中偶数放少的那一部分就行了。
还有一种简单的方法是：先打印所有根节点为偶数，再打印奇数就行了
#include <bits/stdc++.h>
using namespace std;
int out[101010];
int main()
{
int n, i;
cin >> n;
int temp = 1, c1 = 0, c2 = 0, jud = 1, nn = n;
while (temp <= n)
{
n -= temp;
if (jud & 1)
c1 += temp;
else
c2 += temp;
temp *= 2;
jud++;
}
if (jud & 1)
c1 += n;
else
c2 += n;
n = nn;
int ji = 1, ou = 2;
if (c1 < c2)
{
int temp = 2;
jud = 0;
for (i = 1; i <= n; i++)
{
if (temp == i)
jud = !jud, temp *= 2;
if (!jud)
{
if (ou > n)
{
cout << ji;
ji += 2;
}
else
{
cout << ou;
ou += 2;
}
}
else
{
if (ji > n)
{
cout << ou;
ou += 2;
}
else
{
cout << ji;
ji += 2;
}
}
cout << ' ';
}
}
else
{
int temp = 2;
jud = 0;
for (i = 1; i <= n; i++)
{
if (temp == i)
jud = !jud, temp *= 2;
if (jud)
{
if (ou > n)
{
cout << ji;
ji += 2;
}
else
{
cout << ou;
ou += 2;
}
}
else
{
if (ji > n)
{
cout << ou;
ou += 2;
}
else
{
cout << ji;
ji += 2;
}
}
cout << ' ';
}
}
}
小红闯沼泽地
其实就是个图论题，每个边权要么是1，要么是2，求最短路。所以可以通过dijkstra或者bfs求出来（bfs的话 需要把边长为2的边变成两个边长为1的边，有点麻烦，所以直接dijk解决了）
或者看成DP，类似于龙与地下城游戏:
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int dx[] = {1, 0, 0};
const int dy[] = {0, 1, -1};
const int N = 503;
struct Node
{
int x, y, w;
bool operator<(const Node &b) const { return w > b.w; }
};
int n, m;
int a[N][N];
priority_queue<Node> q;
int d[N][N];
bool vis[N][N];
int get(int x, int y)
{
return (x - 1) * m + y;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> a[i][j];
}
}
memset(d, 0x3f, sizeof(d));
d[1][1] = 0;
q.push({1, 1});
while (q.size())
{
int x = q.top().x, y = q.top().y;
q.pop();
if (vis[x][y])
continue;
vis[x][y] = true;
for (int i = 0; i < 3; ++i)
{
int tx = dx[i] + x, ty = dy[i] + y;
int w = (a[x][y] ^ a[tx][ty]) ? 2 : 1;
if (tx && ty && tx <= n && ty <= m)
{
if (d[tx][ty] > d[x][y] + w)
{
d[tx][ty] = d[x][y] + w;
q.push((Node){tx, ty, d[tx][ty]});
}
}
}
}
cout << d[n][m] << endl;
return 0;
} 
