牛客小白月赛 53 赛后总结及题解

牛客小白月赛 53 赛后总结及题解

本次比赛共 7 人 AK，Rank 1 为 kano_2525，用时 32 分钟。

膜拜鹿乃！！11

六道题目的 AC 情况如下：

• A - Raining：

  • 首 A：摸鱼酱（0:50）
  • 通过率：

• B - Kissing：

  • 首 A：kano_2525（2:00）
  • 通过率：

• C - Missing

  • 首 A：纯铁匠（5:11）
  • 通过率：

• D - Breezing

  • 首 A：kano_2525（7:23）
  • 通过率：

• E - Calling

  • 首 A：木之本樱_Sakura（22:58）
  • 通过率：

• F - Freezing

  • 首 A：kano_2525（29:24）
  • 通过率：

一些问题

1. CD 可能有点语言上的表述问题，不过不影响做题。
2. 中途把题目上的引用删了，原因不说。
3. 然后 E 题我 std 就写了 20 多行，码量也不是很大吧
4. F 题好像有的老哥被评测姬波动卡了（std 不加取模优化 0.3s，就是换成递归都只跑了 0.6s，所以如果写的正解应该不存在被卡的现象。如果你写的真的是正解，那我谢罪；但如果你写奇怪做法被卡我就没办法了），还有老哥暴力草过去了，谢罪。

有问题可以在 B 站也可以在这里说。

大概就这样。

题解

A - Raining

按题意直接输出 即可。

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c, d, x; cin >> a >> b >> c >> d >> x;
  cout << max(x - a, 0) << ' ' << max(x - b, 0) << ' ' << max(x - c, 0) << ' ' << max(x - d, 0) << endl;
}

B - Kissing

化简得 然后你发现 就是

所以答案为

n = int(input())
print(pow(n, 2, 998244353))

C - Missing

使用一个结构体，存放的单词 和与标准答案不同字母的数量 ，如果这个单词的长度就与标准答案不一样了，那么就把 赋值为 ，找到 的最大值，然后把所有 的单词扔到一个 vector 里，排序输出即可。

#include<bits/stdc++.h>
using namespace std;

struct Node {
  string s; int k;
} a[110];

vector <string> v;

int main() {
  string answer; cin >> answer;
  int n; cin >> n;
  int ansLen = answer.size();
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].s;
    if ((int)(a[i].s.size()) != ansLen) {
      a[i].k = 0;
    }
    else {
      for (int j = 0; j < ansLen; ++j) {
        a[i].k += (a[i].s[j] == answer[j]);
      }
    }
  }
  int mxk = 0;
  for (int i = 1; i <= n; ++i) {
    mxk = max(mxk, a[i].k); 
  }
  for (int i = 1; i <= n; ++i) {
    if (a[i].k == mxk) {
      v.push_back(a[i].s);
    }
  }
  sort(v.begin(), v.end());
  for (auto i : v) {
    cout << i << endl;
  }
}

D - Breezing

为了让 取最大值， 显然是 或者 ，于是可以 dp。

当 ， 表示 的前 个元素的最大值。

当 ， 表示 前 个元素的最大值。

对于 ，显然是等于 （上一个取 ，这一个也取 ）和 （上一个取 ，这一个取 ）的较大值。

对于 ，显然是等于 （上一个取 ，这一个取 ）和 （上一个取 ，这一个取 ）的较大值。

然后最后答案显然就是 。

#include<bits/stdc++.h>
using namespace std;

int a[100005], f[100005][2];

int main() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n - 1; i++) {
    f[i][0] = max(f[i - 1][0], f[i - 1][1] + abs(a[i] - 1));
    f[i][1] = max(f[i - 1][0] + abs(a[i + 1] - 1), f[i - 1][1] + abs(a[i + 1] - a[i]));
  }
  cout << max(f[n - 1][0], f[n - 1][1]) << endl;
}

E - Calling

简单的贪心。

1. 对于边长为 6 的正方形纸片：显然一个纸片就要一个框，所以答案加 。

2. 对于边长为 5 的正方形纸片：显然一个纸片就要一个框，所以答案加 。

3. 对于边长为 4 的正方形纸片：显然一个纸片就要一个框，所以答案加 。

4. 对于边长为 3 的正方形纸片：一个框能放 4 个，所以答案加 。

5. 对于边长为 2 的正方形纸片：

   1. 我们可以把他和边长为 4 的放在一起，不难发现在每个框还可以放得下 5 个。

   2. 放完了之后可以把他和边长为 3 的放在一起。

      1. 如果还有多出来 1 个边长为 3 的，那么就可以放 5 个边长为 2 的。
      2. 如果还有多出来 2 个边长为 3 的，那么就可以放 3 个边长为 2 的。
      3. 如果还有多出来 3 个边长为 3 的，那么就可以放 1 个边长为 2 的。

   3. 如果还有多的，就单独放。

6. 对于边长为 1 的正方形纸片：哪里有空就往哪放，如果还有多的就单独放。

我 std 好像写的比较简洁，可以看看（

#include<bits/stdc++.h>
using namespace std;

int main() {
  int t; cin >> t;
  while (t--) {
    int s; cin >> s;
    double a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
    int nowAns;
    nowAns = d + e + f + ceil(c / 4);
    int putB = d * 5;
    if ((int)c % 4 != 0) {
      if ((int)c % 4 == 1) putB += 5;
      if ((int)c % 4 == 2) putB += 3;
      if ((int)c % 4 == 3) putB += 1;
    } 
    if (b > putB) { // 还有剩余 
      nowAns += ceil((b - putB) / 9);
    }
    int used;
    used = 6 * 6 * f + 5 * 5 * e + 4 * 4 * d + 3 * 3 * c + 2 * 2 * b;
    int putA;
    putA = 6 * 6 * nowAns - used;
    if (a > putA) { // 还有剩余 
      nowAns += ceil((a - putA) / 36);
    }
    cout << (nowAns <= s ? "Yes" : "No") << endl;
  }
}

F - Freezing

其实数据范围里给了点提示（

首先转化一下题意，把字符串看做一个二进制数， 看作 1， 看作 0，那么这题就是要求有多少非空子序列满足序列中任意两个相邻的数的按位并为 0，即两个数没有任何一位同时为 1。

很容易想到一个 naive 的 dp，令 表示只考虑前 个数，以 结尾的满足要求的子序列的方案数，那么有如下转移：先将 复制到 ，令 表示第 个字符串对应的二进制数，则 应该加上 ，最后的答案即为 。

这个 dp 的正确性是显然的（因为它本质就是模拟了一遍题意），但是它的时间复杂度是 的，无法接受。

考虑优化，容易想到使用高维前缀和的相关 trick 来维护子集和，但是这种做法难写难理解且严重超纲，因此不再赘述。

令 表示只考虑前 个数，结尾的数的高 位为 ，低 位与 的按位并为 0 的满足要求的子序列的方案数，那么有如下转移：先将 复制到 ，令 表示 的高 位， 表示 的低 位，那么对于 ，有 应当加上 。容易发现，我们对 这两个数的限制巧妙地满足了题目所给的要求，我们用两次 的操作完成了暴力做法中 要完成的东西。

等等， 的空间复杂度是 ？！这显然是不可接受的，但是容易发现 这一维并没有用，我们可以先求和再对数组进行更新。

于是我们以 的时间复杂度和 的空间复杂度解决了本题。

#include<bits/stdc++.h>
using namespace std;

const int mod = 998244353;
int f[1 << 8][1 << 8];
char s[17];

int main() {
  int n, m; cin >> n >> m;
  int ans = 0;
  while (n--) {
    cin >> s;
    int a = 0;
    for (int i = 0; i < m; ++i) {
      a = (a << 1) | (s[i] == 'o');
    }
    int x = a >> 8, y = a & 255, z = 1;
    for (int i = 0; i < (1 << 8); ++i) {
      if (!(x & i)) {
        (z += f[i][y]) %= mod;
      }
    }
    (ans += z) %= mod;
    for (int i = 0; i < (1 << 8); ++i) {
      if (!(y & i)) {
        (f[x][i] += z) %= mod;
      }
    }
  }
  cout << ans << endl;
}

Q & A

1. Q：

   不懂就问，题目名字是基于什么想法起的[doge]

   A：

   有一首歌叫 Ref:rain。
   当时我不知道怎么起名字，然后就在「我喜欢的歌曲」里面随了一首，正好抽到了这个。
   这些题目都是一些形如「xxxxxx yyyyyyyyy」（x 是英语，y 是日语）歌词里面的英语部分，然后就拉过来了，如果你开题开的比较早你会发现题目上第一行的引用就是那一句完整的歌词（

2. Q：

   

   A：

   

qwqwqwqwqwq
2022.07.08 21:00:50`