网站备案查询系统wordpress唱片公司模板

网站备案查询系统,wordpress唱片公司模板,那个网站招丑的人做网红,wordpress改变语言题目描述 教授 X 要给 NNN 个学生分组完成学期任务#xff0c;他希望每个小组恰好有 KKK 个学生。 当无法让所有小组都恰好有 KKK 个学生时#xff0c;最多可以有一个小组的学生数少于 KKK 。 学生用前 NNN 个大写英文字母表示#xff08; A 到 A N - 1 #xff09;。 我们…题目描述教授 X 要给NNN个学生分组完成学期任务他希望每个小组恰好有KKK个学生。 当无法让所有小组都恰好有KKK个学生时最多可以有一个小组的学生数少于KKK。 学生用前NNN个大写英文字母表示 A 到 A N - 1 。我们需要处理两种查询COUNT\texttt{COUNT}COUNTNNNKKK计算可以组成小组的方式数量GENERATE\texttt{GENERATE}GENERATENNNKKK生成所有可能的分组方式列表分组规则每个学生只能属于一个小组小组内学生的不同排列顺序被视为相同即组内无序组内学生按字母顺序排列组间按字典序排列使用 ASCII 值比较所有解按字典序排序输入限制最多 1200 个测试用例COUNT\texttt{COUNT}COUNT查询1≤N,K≤301 \le N, K \le 301≤N,K≤30GENERATE\texttt{GENERATE}GENERATE查询1≤N,K≤151 \le N, K \le 151≤N,K≤15每个GENERATE\texttt{GENERATE}GENERATE查询的解不超过100001000010000行所有GENERATE\texttt{GENERATE}GENERATE查询的总解不超过300003000030000行题目分析分组情况分析设总人数为NNN理想小组大小为KKK则整除情况当N mod K0N \bmod K 0NmodK0时所有小组大小都为KKK小组数gN/Kg N / KgN/K非整除情况当N mod Kr0N \bmod K r 0NmodKr0时有一个小组大小为rrr其余g−1g-1g−1个小组大小都为KKK小组数g⌈N/K⌉g \lceil N/K \rceilg⌈N/K⌉数学建模这是一个集合划分问题需要考虑以下关键点组内无序小组内学生的排列顺序不重要组间有序性当所有小组大小相同时组间是无序的当有不同大小的小组时大小不同的小组是独特的字母顺序组内按字母顺序排列这简化了生成过程计数公式推导情况1整除情况N mod K0N \bmod K 0NmodK0小组数gN/Kg N/KgN/K所有小组大小都为KKK。计算步骤将NNN个不同学生分配到ggg个小组中每个小组大小为KKK由于组间无序需要除以g!g!g!公式countN!(K!)g⋅g! \texttt{count} \frac{N!}{(K!)^g \cdot g!}count(K!)g⋅g!N!​情况2非整除情况N mod Kr0N \bmod K r 0NmodKr0小组数g⌈N/K⌉g \lceil N/K \rceilg⌈N/K⌉有一个小组大小为rrr其余g−1g-1g−1个小组大小为KKK。计算步骤从NNN个学生中选择rrr个给较小的组C(N,r)C(N, r)C(N,r)将剩余N−rN-rN−r个学生分配到g−1g-1g−1个大小为KKK的组中大小为KKK的组之间无序需要除以(g−1)!(g-1)!(g−1)!公式countC(N,r)⋅(N−r)!(K!)g−1⋅(g−1)! \texttt{count} C(N, r) \cdot \frac{(N-r)!}{(K!)^{g-1} \cdot (g-1)!}countC(N,r)⋅(K!)g−1⋅(g−1)!(N−r)!​大数处理对于 COUNT 查询N,K≤30N, K \le 30N,K≤30最大的阶乘30!≈2.65×103230! \approx 2.65 \times 10^{32}30!≈2.65×1032这超出了 64 位无符号整数的范围最大值约1.84×10191.84 \times 10^{19}1.84×1019。 因此需要使用128128128位整数来避免溢出。解题思路1.COUNT\texttt{COUNT}COUNT查询实现使用__int128类型处理大数计算预计算阶乘表factorial[0..30]根据NNN和KKK的关系选择公式使用组合数函数计算C(N,r)C(N, r)C(N,r)使用阶乘除法计算结果将__int128转换为字符串输出2.GENERATE\texttt{GENERATE}GENERATE查询实现使用回溯法DFS\texttt{DFS}DFS生成所有解算法步骤表示方法用字符串表示小组如ABC表示包含学生 A、B、C 的小组状态表示currentGroups当前已形成的小组列表used标记哪些学生已被分配currentGroupSize当前小组的当前大小currentGroupStart当前小组的下一个学生起始索引保证组内字母顺序递归过程如果所有学生都已分配idx N检查是否满足小组大小约束最多一个小组小于KKK如果满足则保存解否则尝试将当前学生加入现有小组如果小组未满尝试开始一个新小组排序规则组内按字母顺序通过currentGroupStart参数保证组间按字符串字典序所有解按组序列的字典序排序剪枝优化通过currentGroupStart参数避免生成组内无序的重复解只在必要时开始新小组及时检查小组大小约束时间复杂度分析COUNT\texttt{COUNT}COUNT查询预计算阶乘O(30)O(30)O(30)每次查询O(1)O(1)O(1)GENERATE\texttt{GENERATE}GENERATE查询最坏情况N15,K1N15, K1N15,K1解数为15!130767436800015! 130767436800015!1307674368000但题目保证不超过 10000 个解实际运行由于N≤15N \le 15N≤15且解数有限回溯法可以接受代码实现// n Group k// UVa ID: 10568// Verdict: Accepted// Submission Date: 2025-12-14// UVa Run Time: 0.320s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;usingullunsignedlonglong;usingint128__int128;// 预计算阶乘vectorint128factorial(31);voidprecomputeFactorial(){factorial[0]1;for(inti1;i30;i)factorial[i]factorial[i-1]*i;}// 组合数计算 C(n, k)int128combination(intn,intk){if(k0||kn)return0;if(kn-k)kn-k;int128 result1;for(inti1;ik;i){resultresult*(n-ki)/i;}returnresult;}// 计算分组数int128countWays(intn,intk){intgroups(nk-1)/k;// ceil(n/k)intremaindern%k;if(remainder0){// 所有组大小都是kint128 waysfactorial[n];// 除以 (k!)^groupsint128 kFactorialfactorial[k];for(inti0;igroups;i)ways/kFactorial;// 除以 groups! (组间无序)ways/factorial[groups];returnways;}else{// 有一个大小为remainder的组其余groups-1个组大小为k// 1. 选择remainder个学生给较小的组int128 wayscombination(n,remainder);// 2. 剩余学生分配到groups-1个大小为k的组中intremainingn-remainder;ways*factorial[remaining];// 除以 (k!)^(groups-1)int128 kFactorialfactorial[k];for(inti0;igroups-1;i)ways/kFactorial;// 除以 (groups-1)! (大小为k的组之间无序)ways/factorial[groups-1];returnways;}}// 生成所有解的数据结构vectorvectorstringallSolutions;string students;intN,K;voidgenerateSolutions(intidx,vectorstringcurrentGroups,vectorboolused,intcurrentGroupSize,intcurrentGroupStart){if(idxN){intsmallGroups0;for(constautogroup:currentGroups){if((int)group.size()K)smallGroups;}if(smallGroups1)allSolutions.push_back(currentGroups);return;}// 尝试加入当前组if(!currentGroups.empty()currentGroupSizeK){for(inticurrentGroupStart;iN;i){if(!used[i]){used[i]true;currentGroups.back().push_back(students[i]);generateSolutions(idx1,currentGroups,used,currentGroupSize1,i1);currentGroups.back().pop_back();used[i]false;}}}// 开始新组if((int)currentGroups.size()(NK-1)/K){for(inti0;iN;i){if(!used[i]){used[i]true;currentGroups.push_back(string(1,students[i]));generateSolutions(idx1,currentGroups,used,1,i1);currentGroups.pop_back();used[i]false;break;}}}}// 将int128转换为字符串stringint128ToString(int128 n){if(n0)return0;string result;boolnegativefalse;if(n0){negativetrue;n-n;}while(n0){resultchar(0(n%10))result;n/10;}if(negative)result-result;returnresult;}intmain(){precomputeFactorial();string query;while(cinquery){if(queryEND)break;intn,k;cinnk;if(queryCOUNT){int128 resultcountWays(n,k);coutint128ToString(result)endl;}elseif(queryGENERATE){Nn;Kk;students;for(inti0;in;i)studentschar(Ai);allSolutions.clear();vectorstringcurrentGroups;vectorboolused(n,false);// 开始第一个组if(n0){used[0]true;currentGroups.push_back(string(1,students[0]));generateSolutions(1,currentGroups,used,1,1);}else{allSolutions.push_back({});}// 排序解sort(allSolutions.begin(),allSolutions.end());// 输出数量coutallSolutions.size()endl;// 输出具体解for(constautosol:allSolutions){for(size_t i0;isol.size();i){if(i0)cout ;coutsol[i];}coutendl;}}}return0;}总结本题的核心在于数学推导正确推导分组计数的组合数学公式注意区分整除和非整除情况正确处理组间无序性大数处理使用__int128避免阶乘计算溢出回溯生成使用DFS\texttt{DFS}DFS生成所有解通过参数控制避免重复和保证排序规则排序实现严格按照题目要求的三种排序规则实现关键难点在于处理COUNT\texttt{COUNT}COUNT查询时的大数计算和GENERATE\texttt{GENERATE}GENERATE查询时的排序约束。 通过预计算阶乘、使用__int128类型和精心设计的回溯算法可以高效解决这两个问题。