企业官网建设流程全解析

开公司先建设网站,joomla 2.5:你的网站建设_使用与管理,秦皇岛百度网站排名,昆明seo案例题目大意 你有 MMM 张贺卡#xff08;1≤M≤51 \leq M \leq 51≤M≤5#xff09;和 NNN 种信封#xff08;M≤N≤10M \leq N \leq 10M≤N≤10#xff09;可以选择。每张贺卡需要放入一个独立的信封中#xff0c;贺卡可以任意角度旋转#xff08;包括斜着放#xff09;1≤M≤51 \leq M \leq 51≤M≤5和NNN种信封M≤N≤10M \leq N \leq 10M≤N≤10可以选择。每张贺卡需要放入一个独立的信封中贺卡可以任意角度旋转包括斜着放只要它能完全装入信封内即可。每种信封有特定的尺寸长LiL_iLi​宽WiW_iWi​和价格CiC_iCi​。你需要为每张贺卡分配一个信封不能重复使用同一种信封的同一实体使得总花费最小。如果无法为所有贺卡分配信封则输出cannot buy否则输出最小花费对应的信封编号按输入顺序从111开始编号。如果有多组解输出任意一组即可。题目分析这道题看似简单但实际上涉及几何判断和组合优化两个难点几何判断判断一张尺寸为l×wl \times wl×w的贺卡能否放入一个尺寸为L×WL \times WL×W的信封中。贺卡可以任意旋转包括斜放因此不能简单地比较长宽。组合优化在NNN种信封中为MMM张贺卡分配信封每种信封只能使用一次要求总花费最小。由于M≤5M \leq 5M≤5且N≤10N \leq 10N≤10数据规模很小可以直接使用回溯搜索。几何判断部分对于贺卡尺寸amax⁡(l,w)a \max(l,w)amax(l,w)bmin⁡(l,w)b \min(l,w)bmin(l,w)和信封尺寸Amax⁡(L,W)A \max(L,W)Amax(L,W)Bmin⁡(L,W)B \min(L,W)Bmin(L,W)贺卡可以放入信封的条件是存在一个旋转角度θ\thetaθ使得贺卡在水平和垂直方向上的投影长度同时不超过信封的对应边长。用公式表示就是存在θ∈[0,π/2]\theta \in [0, \pi/2]θ∈[0,π/2]使得acos⁡θbsin⁡θ≤A a \cos\theta b \sin\theta \leq Aacosθbsinθ≤Aasin⁡θbcos⁡θ≤B a \sin\theta b \cos\theta \leq Basinθbcosθ≤B同时成立。特殊情况当a≤Aa \leq Aa≤A且b≤Bb \leq Bb≤B时可以直接对齐放置θ0\theta 0θ0或π/2\pi/2π/2。当bBb BbB时无论怎么旋转短边投影至少为bbb因此不可能放入。当b≤Bb \leq Bb≤B但aAa AaA时需要通过斜放来减小长边方向的投影。在代码实现中我们采用数值方法在[0,π/2][0, \pi/2][0,π/2]区间内以较小步长如0.0010.0010.001弧度搜索θ\thetaθ检查是否存在满足条件的角度。组合优化部分由于MMM很小最多555我们可以使用回溯法DFS\texttt{DFS}DFS枚举所有可能的分配方案。状态表示为当前已分配的贺卡数量idx和当前总花费currentCost。使用一个布尔数组used记录每种信封是否已被使用。剪枝优化当currentCost已经大于等于当前找到的最小花费minCost时直接返回不再继续搜索。复杂度分析最坏情况下需要检查P(N,M)N!(N−M)!P(N, M) \frac{N!}{(N-M)!}P(N,M)(N−M)!N!​种分配方案当N10N10N10M5M5M5时这个值约为302403024030240加上几何判断的开销完全在可接受范围内。解题步骤读入数据注意输入可能包含多个测试用例以0 0结束。预处理对每张贺卡和每种信封判断贺卡能否放入信封考虑斜放。回溯搜索从第000张贺卡开始尝试为它分配一个未被使用且能放入的信封。标记该信封为已使用更新花费递归处理下一张贺卡。回溯时恢复信封的未使用状态。当所有贺卡都分配完毕时更新最小花费和最优分配方案。输出结果按照题目格式输出测试用例编号。如果找到可行方案输出每个贺卡对应的信封编号输入顺序从111开始。否则输出cannot buy。注意相邻测试用例之间输出一个空行。代码实现// Envelopes// UVa ID: 10053// Verdict: Accepted// Submission Date: 2025-12-25// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structCard{intl,w;};structEnvelope{intL,W,cost,id;};intm,n,minCost;vectorCardcards;vectorEnvelopeenvelopes;vectorintbestAssign,currentAssign;vectorboolused;boolfound;constdoublePIacos(-1.0);constdoubleEPS1e-8;// 判断贺卡能否放入信封考虑斜放boolcanFit(constCardcard,constEnvelopeenv){doubleamax(card.l,card.w);doublebmin(card.l,card.w);doubleAmax(env.L,env.W);doubleBmin(env.L,env.W);// 检查是否可以直接对齐放不旋转或旋转90度if(aAEPSbBEPS)returntrue;if(aBEPSbAEPS)returntrue;// 旋转90度// 如果短边b B且长边a A不可能放因为旋转只会让投影更大if(bBEPS)returnfalse;// 现在 b B但 a A需要斜着放// 数值搜索 θ 在 [0, π/2] 之间for(doubletheta0.0;thetaPI/2.0;theta0.001){doubleproj1a*cos(theta)b*sin(theta);doubleproj2a*sin(theta)b*cos(theta);if(proj1AEPSproj2BEPS)returntrue;if(proj1BEPSproj2AEPS)returntrue;// 信封可旋转}returnfalse;}// 回溯搜索voidbacktrack(intidx,intcurrentCost){if(currentCostminCost)return;// 剪枝if(idxm){minCostcurrentCost;bestAssigncurrentAssign;foundtrue;return;}for(inti0;in;i){if(!used[i]canFit(cards[idx],envelopes[i])){used[i]true;currentAssign[idx]i;backtrack(idx1,currentCostenvelopes[i].cost);used[i]false;}}}intmain(){intcaseNum1;while(cinmn(m||n)){cards.resize(m);for(inti0;im;i)cincards[i].lcards[i].w;envelopes.resize(n);for(inti0;in;i){cinenvelopes[i].Lenvelopes[i].Wenvelopes[i].cost;envelopes[i].idi1;}foundfalse;minCostINT_MAX;currentAssign.resize(m);bestAssign.resize(m);used.assign(n,false);backtrack(0,0);if(caseNum1)coutendl;coutCase #caseNumendl;if(found){for(inti0;im;i)coutenvelopes[bestAssign[i]].idendl;}else{coutcannot buyendl;}}return0;}算法要点总结几何判断是核心正确判断贺卡能否斜放入信封是本題的关键。采用数值搜索方法简单可靠。回溯搜索可行由于数据规模小回溯法足以在时限内找到最优解。剪枝优化必要即使数据小简单的剪枝也能显著减少搜索空间。注意输出格式测试用例编号、空行、信封编号从111开始等细节。复杂度分析几何判断每次判断最多搜索约157015701570个角度π/2÷0.001\pi/2 \div 0.001π/2÷0.001常数较大但可接受。回溯搜索最坏情况约302403024030240种分配每种分配需要MMM次几何判断。总复杂度约为O(M!⋅N⋅K)O(M! \cdot N \cdot K)O(M!⋅N⋅K)其中KKK是几何判断的常数因子。在实际测试中运行速度很快。拓展思考如果MMM和NNN更大可能需要使用状态压缩动态规划DP\texttt{DP}DP。几何判断可以进一步优化使用解析方法直接计算而不需要数值搜索。题目中“信封纸张很薄”意味着可以紧密贴合因此我们的几何模型是合理的。关键点理解贺卡可以斜放的条件并采用合适的数值方法进行判断再结合回溯搜索找到最小花费的分配方案。