UVa 799 Safari Holiday

题目描述有nnn个人参加游猎假期活动安排需满足以下规则每天所有人分成若干组每组人数完全相同记为kkk且kkk不得超过组织者规定的最大值kmaxkmaxkmax。每天每个人所在的组其组内其他k−1k-1k−1个人必须与之前任何一天的组员都不同即任意两人至多同组一次。游猎结束时任意两个人都必须曾在某一天同组过即任意两人至少同组一次。给定nnn和kmaxkmaxkmax要求找出满足条件的最大可能的每组人数kkkk≤kmaxk \le kmaxk≤kmax以及对应的游猎天数。若问题无解输出No solution。输入格式多组数据每组一行包含两个正整数nnn和kmaxkmaxkmax。输入直到文件结束。输出格式对每组数据输出一行格式为k persons/group, d days其中kkk为小组规模ddd为所需天数。若d1d 1d1则输出day否则输出days。若无解输出No solution。样例输入4 1 4 2 4 3 4 4样例输出No solution 2 persons/group, 3 days 2 persons/group, 3 days 4 persons/group, 1 day题目分析问题转化我们可以将问题抽象为一个组合设计问题有nnn个元素参与者。需要设计若干“块”每天的分组每个块是若干个子集组每个子集大小均为kkk且所有子集互不相交每天每人只在一个组。要求任意两个元素恰好同组一次既满足“至少一次”又满足“至多一次”。这实际上是构造一个可分解的平衡不完全区组设计Resolvable Balanced Incomplete Block Design\texttt{Resolvable Balanced Incomplete Block Design}Resolvable Balanced Incomplete Block Design简称RBIBD\texttt{RBIBD}RBIBD其中参数vnv nvn元素个数kkk块大小λ1\lambda 1λ1每对元素出现次数设计是可分解的每天的分组是一个平行类覆盖所有元素数学条件推导设游猎进行ddd天则每天产生的不同对数每天有nk\frac{n}{k}kn​个组因为kkk必须整除nnn每组有(k2)\binom{k}{2}(2k​)对不同参与者。每天总对数为nk⋅(k2)nk⋅k(k−1)2n(k−1)2 \frac{n}{k} \cdot \binom{k}{2} \frac{n}{k} \cdot \frac{k(k-1)}{2} \frac{n(k-1)}{2}kn​⋅(2k​)kn​⋅2k(k−1)​2n(k−1)​需要覆盖的总对数所有参与者两两配对的总数为(n2)n(n−1)2\binom{n}{2} \frac{n(n-1)}{2}(2n​)2n(n−1)​。天数公式由于每对恰好出现一次所以d⋅n(k−1)2n(n−1)2 d \cdot \frac{n(k-1)}{2} \frac{n(n-1)}{2}d⋅2n(k−1)​2n(n−1)​解得dn−1k−1 d \frac{n-1}{k-1}dk−1n−1​因此必要条件为k∣nk \mid nk∣n保证每天组数为整数(k−1)∣(n−1)(k-1) \mid (n-1)(k−1)∣(n−1)保证天数为整数存在性条件上述两个整除条件是必要条件。对于组合设计通常还需要满足一些其他存在性条件例如nnn和kkk的数值关系但本题的输入数据似乎默认只要满足这两个整除条件就存在合法的分组方案。因此我们只需检查这两个条件即可。特殊情况knk nkn所有人一组一天即可完成。此时公式dn−1k−1d \frac{n-1}{k-1}dk−1n−1​中k−1n−1k-1 n-1k−1n−1天数为111。注意knk nkn时必然满足两个整除条件。k1k 1k1每人一组无法满足“任意两人同组”的条件因此只有当n1n 1n1时才可能有效此时自己和自己“同组”。n1n 1n1只有一个人任意k≥1k \ge 1k≥1都无意义通常规定k1,d1k 1, d 1k1,d1。解题步骤对于给定的nnn和kmaxkmaxkmax若n≤kmaxn \le kmaxn≤kmax则最优解为knk nkn一天完成。否则从kkmaxk kmaxkkmax向下枚举到222找到第一个满足n%k0n \% k 0n%k0(n−1)%(k−1)0(n-1) \% (k-1) 0(n−1)%(k−1)0的kkk。若枚举后仍未找到且n1n 1n1且kmax≥1kmax \ge 1kmax≥1则k1k 1k1。若最终未找到任何kkk输出No solution。否则计算天数ddd若knk nkn或k1k 1k1则d1d 1d1否则d(n−1)/(k−1)d (n-1) / (k-1)d(n−1)/(k−1)按格式输出注意day和days的单复数。算法复杂度由于kmaxkmaxkmax可能很大最坏情况下需枚举O(kmax)O(kmax)O(kmax)次。但kmaxkmaxkmax本身也是输入值在合理的输入范围内例如10910^9109以内直接枚举是可行的。每个检查为O(1)O(1)O(1)总体时间复杂度O(kmax)O(kmax)O(kmax)每组数据。代码实现// Safari Holiday// UVa ID: 799// Verdict: Accepted// Submission Date: 2026-01-24// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){longlongn,kmax;while(cinnkmax){longlongbestK-1;// 如果允许所有人一组if(nkmax)bestKn;else{// 从大到小搜索第一个满足整除条件的 kfor(longlongkkmax;k2;--k)if(n%k0(n-1)%(k-1)0){bestKk;break;}}// 处理 n1 的特殊情况if(n1kmax1)bestK1;if(bestK-1)coutNo solution\n;else{longlongdays;if(bestKn||bestK1)days1;elsedays(n-1)/(bestK-1);coutbestK persons/group, days day;if(days1)couts;cout\n;}}return0;}总结本题关键在于将实际问题转化为组合设计模型并推导出两个简洁的整除条件k∣nk \mid nk∣n(k−1)∣(n−1)(k-1) \mid (n-1)(k−1)∣(n−1)然后通过从大到小枚举kkk找到满足条件且不超过kmaxkmaxkmax的最大值最后计算天数并输出即可。注意处理好边界情况knk nkn和n1n 1n1。