专栏文章

题解：P13703 [NWERC 2023] Date Picker

DDoraeman
P13703题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miob3yxj
此快照首次捕获于
2025/12/02 16:19
3 个月前
此快照最后确认于
2025/12/02 16:19
3 个月前
查看原文
我看到英文题意时，实在是不理解什么叫“hour/day combinations”。
当然不是因为我英语不好。

题意

已知一个日期表格，画出了一周 77 天每天 2424 小时。
在 77 天中任选至少 dd 天，在 2424 小时中任选至少 hh 小时。设选择 xx 天，yy 小时。
注意：此处“天”两两不同，“小时”也两两不同。
接着，在 x×yx\times y 种 “天与小时的组合（hour/day combinations）”中，等概率选择 11 种，求选中的格子在日期表格中为 . 的概率。

样例分析

为了方便理解题意，现在给出自测样例 #2 的分析。
已经看懂“hour/day combinations”的大佬可以直接跳到下一部分。
在这个样例中，我们选择第 1,2,31,2,3 天，并选择第 10,11,12,13,14,16,17,1810,11,12,13,14,16,17,18 小时。
days/hours10101111121213131414161617171818
11∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet
22∙\bullet×\times∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet
33∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet∙\bullet
在以上表格中列举出的全部 2424 种“小时 / 天”的组合中，只有“第 22 天的第 1212 小时”这个组合在日期表格上对应着 x，其余的组合都对应着 .。
所以答案是 2324=0.9583˙≈0.985333\frac{23}{24}=0.958\dot3\approx0.985333，与样例输出相符。

分析

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

思路

思路中涉及到排列组合知识中的组合数。
首先，我们要确定：总共挑选 xx 天（x≥dx\ge d）。

组合数求 days 可能性

使用组合数求 C⁡7x\operatorname{C}_7^x 的值，并列出所有 1∼71\sim7 中选择 xx 个数的情况。
这部分的内容与题目 P1061 [NOIP2006 普及组] Jam 的计数法 的内容非常相似，写法可以参考当时我那篇格式问题审核不通过的题解。
核心思路就是：
  1. 如果第 nn 位的字母是最大序号，应当向前找到第 11 个不相邻的字母，并将其进一位，紧随其后填上每个数。
  2. 如果第 nn 位的字母不是最大序号，直接向右移动一位。

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

CPP
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 这 33 天。
我们可以根据日期表格，分别求出第 1,2,31,2,3 天的 1∼241\sim24 小时，每个小时所包含的 .。
CPP
xxxxxxxxx.....x...xxxxxx
xxxxxxxx..x...x...xxxxxx
xxxxxxxx......x...x.xxxx
xxxxxxxx...xxxxxxxxxxxxx
xxxxxxxx...xxxxxxxxxxxxx
xxxxxxxx...xxxxxxxx.xxxx
......xxxxxxxxxxxxxxxxxx
在以上这个日期表格中：
  • 第 1,2,31,2,3 天的第 9,119,11 小时都包含 22 个 .；
  • 第 1,2,31,2,3 天的第 10,12,13,14,16,17,1810,12,13,14,16,17,18 小时都包含 33 个 .；
  • 第 1,2,31,2,3 天的第 2020 小时包含 11 个 .；
  • 第 1,2,31,2,3 天的其它的小时不包含任何 .。
求出 1∼241\sim24 这 2424 个小时的 . 的数量之后，对它们进行从大到小排序。
以上这个样例中，排序后序列为：3 3 3 3 3 3 3 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。
从有序的序列中选择至少 hh 个元素求包含 . 的总数并求和。
最后，题目要求概率的最大值，即以上序列中选择 yy 个元素（y≥hy\ge h）的总和与 (x×y)(x\times y)（小时 / 天的组合） 的比值的最大值。
xx 已知，所以可以在单调不减的序列中从前到后循环求当前的元素总和（即包含 . 的数量）。如果已选择的元素大于等于 hh 就考虑更新概率最大值。

细节

题目使用 SPJ，要求误差不超过 10−610^{-6}，所以输出时保留 77 位小数比较合适。

代码

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

bool cal[10][30];
int a[10], b[30], 
    C7[] = {1, 7, 21, 35, 35, 21, 7, 1};
	// C(7,n)有C7[n]种情况
double ans = -1;

// 求C(7,n)的下一种情况 
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;
		}
}

void go(int n, int m){
	// 7天中选择n天, 24小时中选择m小时 
	for(int i=1; i<=n; i++)
		a[i] = i;
	
	for(int _=1; _<=C7[n]; _++){
        memset(b, 0, sizeof(b));
		for(int j=1; j<=24; j++) // 遍历小时 
			for(int i=1; i<=n; i++) // 遍历序列中的所有天 
				b[j] += cal[a[i]][j];
		sort(b + 1, b + 25, greater<int>());
		
		double sum = 0, p = 0, maxi = -1;
		for(int i=1; i<=24; i++){
			sum += b[i], // 元素求和 
			p = sum / (i * n); // 计算概率 
			if(i >= m) // 如果大于等于m, 可以更新概率最大值
				maxi = max(p, maxi);
		}

		ans = max(maxi, ans);
		Cnext(n);
	}
}

int main(){
	for(int i=1; i<=7; i++)
		for(int j=1; j<=24; j++){
			char x; cin >> x;
			cal[i][j] = (x == '.');
		}
    int n, m; cin >> n >> m;
    
    // 分别枚举选择n,n+1,...,7天 
    for(int i=n; i<=7; i++)
    	go(i, m);
    
    // 输出答案 
    printf("%.7lf",ans);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...