25暑假day5测试题解

T1

只需建立一个整型变量 $n$，然后按照给出的公式依次输出答案就可以了。要注意，由于 $n$ 可能达到 $10^6$，最后一项 $6(n−2)^2$ 的范围会达到约 $6\times 10^{12}$，超过了 int 的范围，所以需要用 long long 来存储，核心代码如下：

long long n;
cin >> n;
cout << 8 << " " << 12 * (n - 2) << " " << 6 * (n - 2) * (n - 2) << endl;

---

T2

本题考察分支结构。

本题要依次判断两个条件，第一个是楼层限制，第二个是人流量。只需按照题意依次判断即可：

• 如果 $n≤3$，则三栋楼都需要考虑，就应该从 $a,b,c$ 三个人流量中判断出最少的，输出对应的名字。

• 如果 $3<n≤5$，则只可能在综合楼和艺术楼里，就应该从 $b,c$ 两个人流量中判断哪一个较少，输出对应的名字。

• 如果 $5<n≤9$，则只可能在艺术楼里，直接输出其名字即可。

此外，输出时，如果担心出现偏差，可以直接复制题目给出的字符串，核心代码如下：

if (n <= 3)
{
    if (a < b && a < c)
    {
        cout << "library";
    }
    else if (b < c)
    {
        cout << "comprehensive";
    }
    else
        cout << "art";
}
else if (n <= 5)
{
    if (b < c)
    {
        cout << "comprehensive";
    }
    else
        cout << "art";
}
else
    cout << "art";

---

T3

本题考察简单循环。

经过简单思考可以发现，与一个同学交换位置时，由于书和人都交换了位置，所以 zyl 手上的书的数量一直不变，为 x，又因为一共交换了 $n$ 次，所以这一部分要消耗 $n×x$ 的体力值。而对于同学的书，交换位置后，就被换到了 zyl 原来的位置上，之后就不用再搬了。所以这一部分要消耗 $a_1+a_2+\cdots+a_n$ 的体力值。

只需要循环读入 $a_i$ 并求和即可，这里无需开一个数组，只需使用一个答案变量 ans，先使 $ans=n×x$，即第一部分的体力值，然后依次累加输入的信息就可以了。

这里要注意，即使输入的数据均在 int 范围内，但是 $n\times x$ 的范围达到了 $2×10^{10}$，所以 ans 要使用 long long 类型，核心代码如下：

long long ans = 1ll * n * x;
for (int i = 1; i <= n; i++)
{
    int a;
    cin >> a;
    ans += a;
}
cout << ans;

---

T4

有 $n$ 个柜子，第 $i$ 个的格子数为 $a_i×b_i$，每个格子由 $c_i$ 个学生使用。由此得到学生总数与桌子总数，按照指定列数来摆桌子，尽量摆成整齐的矩形，多余的放到最后一排的后方，求最后的排数和最后一排桌子的张数。

本题考察简单循环与简单数学推导。

本题一共分两个部分，第一个部分是求出桌子总数，第二个部分是求出摆好之后桌子的排数和最后一排的桌子数量。

对于第一部分，显然，对于第 $i$ 个柜子，应该有 $a_i\times b_i\times c_i$ 个学生使用，将所有的柜子对应的学生个数累加就得到了学生总数，等于桌子总数，这一部分代码如下：

for (int i = 1; i <= n; i++)
{
    int a, b, c;
    cin >> a >> b >> c;
    sum += a * b * c;
}

接着就是第二部分。不难发现，桌子的排数应该是总数除以列数并向上取整。因为如果恰好整除，则排数等于总数除以列数，否则，等于其加一。

然后，对于最后一排的桌子数量，显然就等于 $a\bmod b$ 了。但是要注意，当能够整除时，桌子摆成了矩形，最后一排的桌子数量应该等于 $m$，但此时 $a\bmod b=0$，所以要特判。这一部分代码如下：

int x = sum % m;
if(x == 0) x = m;
if (sum % m == 0)
    cout << sum / m << " " << x;
else
    cout << sum / m + 1 << " " << x;

---

T5

解题思路

由于 $(1,2,5)$ 和 $(2,1,5)$ 是同一种方案，那么为了在选取的过程中避免重复计算，我们可以要求选取的数必须严格单调递增，即 $i<j<k$。

考虑暴力，枚举 $i,j,k$，时间复杂度 $O(n^3\log{n})$。

• 数位拆分判断是否含有 $3$ 或 $7$ 即可。

bool check(int x)
{
    while (x)
    {
        if (x % 10 == 3 || x % 10 == 7)
            return false;
        x /= 10;
    }
    return true;
}

优化：由于 $i+j+k=n$，那么我们可以枚举 $i,j$，用 $n−i−j$ 算出 $k$ 的大小，再判断是否合法即可，时间复杂度 $O(n^2\log{n})$。

---

T6

我们可以将各个指标的平均值作为第一关键字从大到小排序。但如果平均值一样，怎么办呢？

由于题目说了：“若有多个必要性前二大的试题则选择较早出现的那个”。所以我们可以将每个试题的序号作为第二关键字从小到大排序。

排完序之后输出必要性前两大的试题的编号就可以了。

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int sum, rk;
    double avg;
} a[110];
bool cmp(node a, node b)
{
    if (a.avg != b.avg)
        return a.avg > b.avg;
    return a.rk < b.rk;
}
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            int x;
            cin >> x;
            a[i].rk = i;
            a[i].sum += x;
        }
        a[i].avg = 1.0 * a[i].sum / k;
    }
    sort(a + 1, a + n + 1, cmp);
    cout << a[1].rk << "\n" << a[2].rk;
    return 0;
}

---

T7

注意到每个人只会在左边的盘子或右边的盘子两个任选一个放下，这就是一个二选一的行为。且 $K\leq16$，因此考虑二进制枚举，枚举 $K$ 个人所有放盘子的可能。

for (int mask = 0; mask < (1 << k); mask++)

接下来需要检验每一个状态 mask 可以满足几个条件，记录满足的条件个数为 $sum$，求出 $sum$ 的最大值即可。

因此如何求出状态 mask 满足几个条件是本题的关键。

可以使用打标记的思想解决。

• 定义一个大小为 $n$ 的数组 vis，初始化 vis[i] = 0 代表第 $i$ 个盘子还没有放下球。
• 接下来对于每一个状态 mask，检验它的二进制位哪些是 $1$，哪些是 $0$。
  • for (int i = 0; i < k; i++)
  • 当满足 mask >> i & 1 时，说明 mask 二进制第 $i$ 位是 $1$，我们认为放在左边的盘子，则执行 vis[c[i]] =。
  • 反之执行 vis[d[i]] = 1。
• 接下来遍历 $m$ 个条件，若满足：vis[a[i]] == 1 && vis[b[i]] == 1，则 sum++。

• 最后对 sum 进行 max() 操作，即可求出最大值。

• 注意一些实现细节，哪些变量，哪些数组需要在什么地方重置。

时间复杂度为 $O(2^k\times(n+k+m))$。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[105], b[105], c[105], d[105], k;
bool vis[105];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
    }
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> c[i] >> d[i];
    }
    int mx = 0;
    for (int mask = 0; mask < (1 << k); mask++)
    {
        for (int i = 1; i <= n; i++) // 重置标记数组
            vis[i] = 0;
        // 检验 mask 的位的情况
        for (int i = 0; i < k; i++)
        {
            if (mask >> i & 1)
                vis[c[i]] = 1; // 放在左边，打标记
            else
                vis[d[i]] = 1; // 放在右边，打标记
        }
        int sum = 0;
        for (int i = 1; i <= m; i++)
        {
            if (vis[a[i]] == 1 && vis[b[i]] == 1)
            {
                sum++;
            }
        }
        mx = max(mx, sum);
    }
    cout << mx;
    return 0;
}