合并检测

原题链接：https://edu.csdn.net/skill/practice/algorithm-6437a69f581f4821a5cbd4267304a905/2315 新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情，A 国准 备给大量民众进病毒核酸检测。 然而，用于检测的试剂盒紧缺。为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k 个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k 个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明 至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看， 如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中 不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用 了 k + 1 个试剂盒完成了 k 个人的检测。 A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？ 以下程序实现了这一功能，请你补全以下空白处内容：

#include <stdio.h>
int main()
{
    double m = 4537;
    double min = 9999999;
    double k, sum, ans;
    for (k = 1; k <= 100; k++)
    {
        sum = (m - k) / k + 0.01 * m * k + 1;
        __________________;
    }
    printf("%d\n", (int)ans);
    return 0;
}

挖的坑并不难，但由于这其实是一个数学题，如果纯手敲的话，可能有点费劲，想不到这个方法。

正确答案：

if (sum < min)
{
    min = sum;
    ans = k;
}

逐行分析一下官方给的代码。

首先定义了m和min变量。

• m是检测的总人数。
• min是最小值，初始值为随便取的一个较大的值。目的是在之后的对比中，及时更新min。

然后定义了k、sum、ans。

• k为每组检测的人数。
• sum为当前人数时，消耗的试剂数量。
• ans为截止到目前，消耗的试剂数量最少时的k值，即为最后的答案。

for循环内，对k逐个取值，求对应取值时的sum值。 sum = (m - k) / k + 0.01 * m * k + 1;

• m-k是没出现问题的人数，由于他们每k人共用一盒试剂，因此共消耗(m - k) / k盒试剂。
• 0.01 * m * k中0.01*m是出现问题的人数，在发现试剂盒出现问题后，他们所在的小组需要消耗k盒试剂。
• 由于发现问题还需要一盒试剂，因此最后还需要+1。

也可以这样理解：

对于m个人，每k人一组，共消耗m/k盒试剂。 每盒有0.01的概率出现问题，由于均匀分布，出现问题的盒数可以认为是0.01*k。 每组出现问题后，需要对组内的所有成员检测，消耗0.01*k*k盒试剂。 共有m/k个小组，因此需消耗0.01*k*k*m/k盒试剂。 一共m/k+0.01*m*k盒试剂，结果是与原题一样的。

星期一

原题链接：https://edu.csdn.net/skill/practice/algorithm-b788a09cd8e647738a9ac6aea903aadb/2367 整个20世纪（1901年1月1日至2000年12月31日之间），一共有多少个星期一？(不要告诉我你不知道今天是星期几) 以下程序实现了这一功能，请你补全以下空白处内容：

#include <stdio.h>
int main()
{
    int year, day, dayrun = 0, dayping = 0, sumday = 0;
    int count = 0;

    for (year = 1901; year <= 2000; year++)
    {
        if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
        {
            dayrun += 366;
        }
        else
        {
            dayping += 365;
        }
    }

    sumday = dayrun + dayping;

    __________________________;
    printf("%d", count);
    return 0;
}

正确答案：

for (day = 2; day <= sumday - 7; day += 7)
{
    count++;
}

逐行分析一下

int year, day, dayrun = 0, dayping = 0, sumday = 0; int count = 0; 定义了一些变量，后面用到的时候再说。 for (year = 1901; year <= 2000; year++) 从1901年循环到2000年，根据每年的情况判断闰年还是平年，以此判断周一个数。

if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
{
    dayrun += 366;
}
else
{
    dayping += 365;
}

sumday = dayrun + dayping;

代码中的if...else是在循环体内的，也就是判断每年是平年还是闰年，然后加到sumday中，求出总的天数，其实也可以sumday+=而不使用dayrun和dayping两个变量。

for (day = 2; day <= sumday - 7; day += 7)
{
    count++;
}

由于1901年1月1日是周二，因此默认的day是2，然后循环判断当前天数是否离总天数差一周，如果是的话，day往后推一周。每周只会有一次星期一。 最后还有一种可能，离总天数差6天，这样的话最后一天就是周一，但原题中并未判断这一条件，并且由于事实上，最后一天也不是周一，因此本题的结果是正确的。

至于没有判断的原因，可能是由于这道题的背景，就在考试当天，不需要特别说明日期。（我蒙的，不严谨，当个笑话就可以）

特别数的和

原题链接：https://edu.csdn.net/skill/practice/algorithm-ef2760aef95742c49f78c313d1ff2eb1/2311

#include <iostream>

using namespace std;

int ans, n;

bool check(int n)
{
    while (n)
    {
        int tmpn = n % 10;
        if (tmpn == 2 || tmpn == 0 || tmpn == 1 || tmpn == 9)
            return true;
        __________________;
    }
    return false;
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        if (check(i))
            ans += i;
    }

    cout << ans << endl;

    return 0;
}

正确答案

n /= 10;

这个没什么可说的，简单粗暴。

#include <iostream> using namespace std; 首先包含C++的标准输入输出头文件，使用std命名空间。 bool check(int n) 把判断部分单独封装，用于检查是否为特别数。

总结

这三道题并不难。 但经常做那些比较复杂的、用到下标访问的题，突然做这种题，就有点无从下手。 感觉总想写一个最优、最精妙的解。 有些题就是一个单纯的数学题，思考的方向可能就偏了。 第一步应该是先把需求解决掉，然后再考虑优化。