题解：P13703 [NWERC 2023] Date Picker

Doraeman · 2025-08-16 11:56:17 · 题解

我看到英文题意时，实在是不理解什么叫“hour/day combinations”。
当然不是因为我英语不好。

题意

已知一个日期表格，画出了一周 7 天每天 24 小时。

在 7 天中任选至少 d 天，在 24 小时中任选至少 h 小时。设选择 x 天，y 小时。
注意：此处“天”两两不同，“小时”也两两不同。

接着，在 x\times y 种 “天与小时的组合（hour/day combinations）”中，等概率选择 1 种，求选中的格子在日期表格中为 . 的概率。

样例分析

为了方便理解题意，现在给出自测样例 #2 的分析。
已经看懂“hour/day combinations”的大佬可以直接跳到下一部分。

在这个样例中，我们选择第 1,2,3 天，并选择第 10,11,12,13,14,16,17,18 小时。

在以上表格中列举出的全部 24 种“小时 / 天”的组合中，只有“第 2 天的第 12 小时”这个组合在日期表格上对应着 x，其余的组合都对应着 .。
所以答案是 \frac{23}{24}=0.958\dot3\approx0.985333，与样例输出相符。

分析

显然，这道题数据量非常小。因为 d,h 满足 d\le7,\ h\le24。
因此，可以暴力（非常暴力）搜索完成本题。
然而，想要获得一个靠谱的解题思路却比较困难。

思路

思路中涉及到排列组合知识中的组合数。

首先，我们要确定：总共挑选 x 天（x\ge d）。

组合数求 days 可能性

使用组合数求 \operatorname{C}_7^x 的值，并列出所有 1\sim7 中选择 x 个数的情况。
这部分的内容与题目 P1061 [NOIP2006 普及组] Jam 的计数法 的内容非常相似，写法可以参考当时我那篇格式问题审核不通过的题解。

核心思路就是：

1. 如果第 n 位的字母是最大序号，应当向前找到第 1 个不相邻的字母，并将其进一位，紧随其后填上每个数。
2. 如果第 n 位的字母不是最大序号，直接向右移动一位。

组合求 \operatorname{C}_7^x 全部情况的代码

void Cnext(int n){
    if(a[n] < 7){ // 不到临界值 
        a[n]++;
        return;
    }

    // 到临界值了, 向上一位"进位" 
    for(int i=n; i>1; i--)
        if(a[i] != a[i-1] + 1){
            a[i-1]++;
            for(int j=i; j<=n; j++)
                a[j] = a[i-1] + (j-i+1);
            return;
        }
}

根据已知的 days 求最佳的 hours

这部分仍然以自测样例 #2 作为例子。
例如：我们选取了 1,2,3 这 3 天。

我们可以根据日期表格，分别求出第 1,2,3 天的 1\sim24 小时，每个小时所包含的 .。

xxxxxxxxx.....x...xxxxxx
xxxxxxxx..x...x...xxxxxx
xxxxxxxx......x...x.xxxx
xxxxxxxx...xxxxxxxxxxxxx
xxxxxxxx...xxxxxxxxxxxxx
xxxxxxxx...xxxxxxxx.xxxx
......xxxxxxxxxxxxxxxxxx

在以上这个日期表格中：

• 第 1,2,3 天的第 9,11 小时都包含 2 个 .；
• 第 1,2,3 天的第 10,12,13,14,16,17,18 小时都包含 3 个 .；
• 第 1,2,3 天的第 20 小时包含 1 个 .；
• 第 1,2,3 天的其它的小时不包含任何 .。

求出 1\sim24 这 24 个小时的 . 的数量之后，对它们进行从大到小排序。
以上这个样例中，排序后序列为：3 3 3 3 3 3 3 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。
从有序的序列中选择至少 h 个元素求包含 . 的总数并求和。

最后，题目要求概率的最大值，即以上序列中选择 y 个元素（y\ge h）的总和与 (x\times y)（小时 / 天的组合） 的比值的最大值。