[语言月赛 202308] 小粉兔的元素反应 题解

· · 题解

Source & Knowledge

2023 年 8 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定 n 和 a _ 1, a _ 2, \cdots, a _ n。当 a 序列中某两个元素相乘后是 147 或 154 的倍数，所有 a _ i 变为原来的两倍。求能否通过若干次（或 0 次）相乘，使得 a _ 1 + a _ 2 + \cdots + a _ n \geq k。

题目分析

本题考察较复杂的模拟。

不难发现这样几条性质：

  1. 单个元素（n = 1）一定无法反应。
  2. 如果两个元素 a _ i, a _ j 可以反应，那么它们就可以一直反应，使得序列无限翻倍。

因此，对于每组数据，我们可以按照以下步骤处理：

k 的处理

由性质 3 和性质 4，我们使用字符串 std::string 或 char[] 读入 k。读入后，首先判断 k 的长度是否 \geq 17。如果是，我们直接将整数类型的 k 设为 10 ^ {16}；否则，我们手动模拟/使用库函数，将字符串类型的 k 转换为整数类型。

C++ 的 std::stoll() 可以将 std::string 转换为 long long 类型，这里使用这种方法进行转换。

string s;
cin >> s;
if (s.length() < 17) {
    k = stoll(s);
} else {
    k = 1e16;
}

对 n = 1 的特殊处理

对于 n = 1，由于单个元素无法反应（性质 1），因此只需要判断仅有的一个元素 a _ 1 和 k 的大小关系。

if (n == 1) {
    if (a[1] >= k) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    continue;
}

直接判断当前元素是否总和 \geq k

我们只需读入时将所有元素相加，并与处理后的整数 k 作比较，即可得到一个初步判断。

找到可能反应的元素

由性质 5 和性质 6，我们可以遍历一次数组，找到能够整除 14, 22, 77, 21, 49 的元素。但是，对于另一个元素，如果我们再进行同样的遍历，时间复杂度为 O(n ^ 2)，不能接受。

所以我们考虑分别记录能够整除 2, 3, 7, 11 的元素的数量。

int cnt[15];
int ops[] = { 2, 3, 7, 11 };
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) {
    for (int j = 0 ; j < 4; ++j) {
        if (a[i] % ops[j] == 0) {
            ++cnt[ops[j]];
        }
    }
}

首先我们可以扫描查找是否有直接为 147 或 154 的倍数的元素，如果有则直接输出 Yes，进行下一组数据的运算。

如果没有，接下来，遍历数组查找能够整除 14, 22, 77, 21, 49 的元素，并分别判断有多少能够整除 11, 7, 2, 7, 3 的元素。对于 14, 22, 77, 49，只要有一个对应的另一个元素即可；但是对于 21，由于 21 本身可以整除 7，因此需要有至少两个对应的元素。

int flag = 0;
for (int i = 1; i <= n; ++i) {
    if (a[i] % 154 == 0 || a[i] % 147 == 0) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 21 == 0 && cnt[7] >= 2) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 49 == 0 && cnt[3]) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 77 == 0 && cnt[2]) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 14 == 0 && cnt[11]) { cout << "Yes" << endl; flag = 1; break; }
    if (a[i] % 22 == 0 && cnt[7]) { cout << "Yes" << endl; flag = 1; break; }
}
if (!flag)
    cout << "No" << endl;

通过以上步骤，我们就可以完成所有判断。

视频讲解

视频题解后续将会上传。