信奥赛C++提高组csp-s之组合数学专题课：鸽巢原理详解及案例实践

信奥赛C提高组csp-s之组合数学专题课鸽巢原理详解及案例实践鸽巢原理是组合数学中一个看似简单但极具威力的工具它在信奥赛提高组中常用于解决存在性证明和构造问题。下面我们将结合数学原理、实例以及编程案例实践进行详细讲解。一、数学原理鸽巢原理又称抽屉原理由德国数学家狄利克雷首先明确提出 。其核心思想非常直观可以用以下两个定理来表述定理 1基本形式如果将n 1个物体放入n个抽屉中那么无论怎么放至少有一个抽屉里含有至少两个物体 。证明反证法。假设每个抽屉最多放一个物体那么n个抽屉最多能放n个物体这与有n 1个物体矛盾。因此假设不成立原命题为真 。定理 2推广形式如果将多于k × n 1个物体放入n个抽屉中那么至少有一个抽屉里含有至少k 1个物体 。更一般地若将m个物体放入n个抽屉则至少有一个抽屉里含有不少于⌈m / n⌉个物体 。证明同样可用反证法证明。如果每个抽屉里的物体都不超过k个那么物体总数最多为k × n与总数大于k × n矛盾。这个原理虽然简单但在解决“保证存在”类型的问题时往往能发挥关键作用。解决问题的关键在于识别并构造出合适的“抽屉”和“物体”。二、数学例子基本应用在长度为n的数列中一定能找到两个数它们除以n-1的余数相同。解析一个数除以n-1的余数只能是0, 1, ..., n-2共有n-1种可能即n-1个抽屉。数列中有n个数即n个物体。根据定理1必有两个数落在同一个余数抽屉里。加强应用在一场至少进行了n1轮的比赛中一定存在某个选手连续若干轮的得分之和为n的倍数。解析设前i轮的得分总和为Sᵢ(i1…T)并考虑S₀ 0。现在看T1个前缀和S₀, S₁, ..., Sₜ。根据定理1这T1个数除以n的余数只有n种可能因此必有两个前缀和Sₐ和Sₑ(a b) 除以n的余数相同。那么从第a1轮到第b轮的得分之和Sₑ - Sₐ就是n的倍数。三、编程案例 Halloween treats题目描述每年万圣节都会遇到同样的问题每个邻居只愿意在当天给出一定数量的糖果无论有多少孩子上门因此如果去得太晚孩子可能什么也得不到。为了避免冲突孩子们决定把所有糖果放在一起然后平均分配。根据去年的万圣节经验他们知道从每个邻居那里能得到多少糖果。由于他们更关心公平而不是糖果的数量他们想选择一组邻居去拜访这样在分配时每个孩子都能得到相同数量的糖果。如果剩下任何无法分配的糖果他们不会满意。你的工作是帮助孩子们并给出一个解决方案。输入格式输入包含多个测试用例。每个测试用例的第一行包含两个整数 c 和 n 1 ≤ c ≤ n ≤ 100000 1 \leq c \leq n \leq 1000001≤c≤n≤100000分别代表孩子数量和邻居数量。下一行包含 n 个空格分隔的整数a 1 , … , a n 1 ≤ a i ≤ 100000 ) a_1, \ldots, a_n 1 \leq a_i \leq 100000 )a1​,…,an​1≤ai​≤100000)其中a i a_iai​表示孩子们拜访邻居 i 时能得到的糖果数量。最后一个测试用例后跟着两个零。输出格式对于每个测试用例输出一行包含孩子们应该选择的邻居的索引这里索引 i对应第 i个邻居他们提供a i a_iai​颗糖果。如果不存在使每个孩子至少得到一颗糖的解则输出 “no sweets”。请注意如果有多个解能使每个孩子至少得到一颗糖你可以输出其中任意一个。输入输出样例 1输入 14 5 1 2 3 7 5 3 6 7 11 2 5 13 17 0 0输出 13 5 2 3 4思路分析题目大意给定两个整数c和n以及一个由n个正整数组成的列表代表邻居给的糖果数。需要从这n个数中选出连续的一段使得这段数的和能被c整除。题目保证c ≤ n并且一定有解。要求输出这段连续数的起始编号从1开始。思路分析建立数学模型设糖果数的数组为a[1..n]。我们需要找到两个索引l和r(1 ≤ l ≤ r ≤ n)使得(a[l] a[l1] ... a[r]) % c 0。引入前缀和定义前缀和sum[i] (a[1] a[2] ... a[i]) % c并定义sum[0] 0。那么连续子段[l, r]的和能被c整除的条件就等价于(sum[r] - sum[l-1]) % c 0即sum[r] sum[l-1](模c意义下)。应用鸽巢原理现在我们有n1个前缀和sum[0], sum[1], ..., sum[n]。每个sum[i]是模c后的结果因此它的取值范围是{0, 1, ..., c-1}共有c种可能的余数即c个抽屉。因为c ≤ n所以n1 c即物体数量大于抽屉数量。根据鸽巢原理定理1这n1个前缀和sum中至少存在两个不同的索引i和j(i j)使得它们的值相等。一旦找到这样的i和j根据上面的推导从第i1个邻居到第j个邻居给出的糖果总数就是c的倍数这正是题目要求的解。特殊情况如果某个sum[j] 0那么从第1个到第j个邻居的和本身就是c的倍数同样满足条件。代码实现#includebits/stdc.husingnamespacestd;constintN100005;// 定义数组大小intc,n;// c: 需要整除的数, n: 邻居数量inta[N];// a[]: 存放每个邻居给的糖果数ints[N];// s[]: 存放前缀和模c的结果intp[N];// p[]: 用于记录某个余数第一次出现的索引 (p[余数] 索引)intmain(){while(scanf(%d%d,c,n)cn){// 循环读入直到cn0for(inti1;in;i){scanf(%d,a[i]);// 计算当前前缀和模c前一个前缀和加上当前值再取模s[i](s[i-1]a[i])%c;}// 初始化标记数组-1表示该余数还没出现过// 注意余数的范围是 [0, c-1]memset(p,-1,sizeof(p));intl0,r0;// l和r用于记录找到的连续段的起始和结束位置for(inti0;in;i){// 从0到n遍历所有前缀和if(p[s[i]]!-1){// 如果当前余数s[i]之前出现过说明找到了解// 之前出现的位置是p[s[i]]注意p[s[i]]存的是索引这个索引对应的前缀和是s[p[s[i]]]// 那么解就是从索引 p[s[i]]1 到 ilp[s[i]]1;// 起始位置是之前出现位置的下一个ri;// 结束位置是当前位置break;}else{// 如果当前余数是第一次出现记录下它出现的位置p[s[i]]i;}}// 输出结果if(l!0){// 确保找到了解for(intil;ir;i){printf(%d ,i);// 题目要求输出编号从1开始}printf(\n);}}return0;}功能分析数据结构a[N]存储输入的原始数据。s[N]存储到当前位置为止的累加和对c取模的结果。这是实现鸽巢原理的关键。p[N]这是一个“桶”或“标记”数组。p[余数值]记录了该余数第一次出现时的索引。例如当s[3] 2时我们执行p[2] 3。如果后续某个s[j]也等于2我们就能通过p[2]快速找到对应的起点。核心逻辑代码的核心是for循环它遍历了所有n1个前缀和包括s[0]。每次得到一个新的余数s[i]程序就检查这个余数是否已经在p数组中登记过即p[s[i]]是否不等于 -1。如果没有登记过说明这是该余数第一次出现我们将当前位置i记录到p[s[i]]中。如果登记过则意味着找到了两个相同余数的前缀和这正是鸽巢原理保证的结果。此时p[s[i]]存储的是之前相同余数出现的位置i那么连续段就是从p[s[i]] 1到i。正确性保证由于c ≤ n所以有n1个物体和c个抽屉满足鸽巢原理的使用条件保证了相同余数必然存在。算法的时间复杂度是 O(n)空间复杂度是 O(n)可以高效处理题目范围内的数据。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}