题目描述Rick\texttt{Rick}Rick有一个边长为LLL米的正方形花园被划分为L2L^2L2个边长为111米的正方形模块。他需要选择NNN个模块进行种植并希望所选区域的周长尽可能大因为更大的周长意味着更好的灌溉效果。灌溉软管沿着所选区域的外围铺设。需要求出在L×LL \times LL×L的网格中选择NNN个格子所能得到的最大周长。输入格式输入包含多组测试数据每组一行包含两个整数LLL和NNN分别表示花园边长和需要种植的格子数满足1≤L≤1061 \le L \le 10^61≤L≤1060≤N≤L20 \le N \le L^20≤N≤L2。输入以一行0 0结束。输出格式对于每组数据输出一行一个整数表示能达到的最大周长。样例输入1 0 1 1 2 3 3 8 0 0输出0 4 8 16题目分析本题的核心是在L×LL \times LL×L的网格中选取NNN个格子使得这些格子组成的图形周长最大。周长计算方式每个格子的444条边中如果相邻格子也被选中则共享的边不计入周长。因此总周长为周长4N−2×(相邻格子对数) \text{周长} 4N - 2 \times (\text{相邻格子对数})周长4N−2×(相邻格子对数)其中相邻定义为共享一条边四连通。要最大化周长就需要最小化相邻格子对数。换句话说我们希望选中的格子尽可能分散避免相互接触。但是随着NNN的增大格子必然会出现相邻因此需要找到一个最优的排列方式。解题思路贪心策略一个经典的贪心思路是将格子按照对周长的“贡献”分类。每增加一个格子它对周长的贡献可以是444、000、−2-2−2或−4-4−4取决于它与已选格子的相邻情况。具体地可以将格子分为四类孤立格子按“跳棋”方式选取每个格子与四周格子都不相邻。这类格子每选一个周长增加444。角点格子四个角上的格子。在最优排列中选角点不会改变周长净贡献000。边界格子非角位于边界但不是角的格子。每选一个周长减少222。内部格子完全被包围的格子。每选一个周长减少444。因此最优策略是按照贡献从大到小的顺序选取格子先尽可能多地选孤立格子再选角点再选边界格子最后才选内部格子。关键参数的计算孤立格子的最大数量aaa取决于LLL的奇偶性因为网格的“棋盘染色”性质决定了最大独立集的大小。情况一LLL为偶数网格可以完美划分为两个颜色类每类恰好L2/2L^2 / 2L2/2个格子。一类中的格子互不相邻因此aL2/2a L^2 / 2aL2/2孤立格子数b2b 2b2贡献为000的角点可额外选的数量c(L/2−1)×4c (L/2 - 1) \times 4c(L/2−1)×4边界格子可额外选的数量情况二LLL为奇数奇数的棋盘染色不均等两类格子数相差111。最优排列有两种可能需要取最大值方式一选较少的那一类作为孤立格子a⌊L2/2⌋a \lfloor L^2 / 2 \rfloora⌊L2/2⌋b1b 1b1当L1L1L1时或444c(L−3)/2×4c (L - 3) / 2 \times 4c(L−3)/2×4方式二选较多的那一类作为孤立格子a⌊L2/2⌋1a \lfloor L^2 / 2 \rfloor 1a⌊L2/2⌋1b0b 0b0c(L−1)/2×4c (L - 1) / 2 \times 4c(L−1)/2×4周长计算函数给定a,b,ca, b, ca,b,c设当前需要选取NNN个格子则最大周长可以通过如下分段函数计算周长(N){4Nif N≤a4aif aN≤ab4a−2(N−a−b)if abN≤abc4a−2c−4(N−a−b−c)if Nabc \text{周长}(N) \begin{cases} 4N \text{if } N \le a \\ 4a \text{if } a N \le a b \\ 4a - 2(N - a - b) \text{if } a b N \le a b c \\ 4a - 2c - 4(N - a - b - c) \text{if } N a b c \end{cases}周长(N)⎩⎨⎧​4N4a4a−2(N−a−b)4a−2c−4(N−a−b−c)​ifN≤aifaN≤abifabN≤abcifNabc​解释第一阶段只选孤立格子每个贡献444。第二阶段选角点贡献为000周长不变。第三阶段选边界格子每个贡献−2-2−2。第四阶段选内部格子每个贡献−4-4−4。复杂度分析每组数据仅需常数次运算时间复杂度O(1)O(1)O(1)。空间复杂度O(1)O(1)O(1)。非常适合LLL高达10610^6106的情况。代码实现// Square Garden// UVa ID: 12520// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongll;// 计算最大周长的函数llcalcularMaxPerimetro(ll a,ll b,ll c,ll N){if(Na)returnN*4;if(Nab)returna*4;if(Nabc)returna*4-(N-a-b)*2;returna*4-c*2-(N-a-b-c)*4;}intmain(){ll L,N;while(cinLN,L||N){ll ans0;// L为偶数的情况if(L%20){ll aL*L/2;ll b2;ll c(L/2-1)*4;anscalcularMaxPerimetro(a,b,c,N);}// L为奇数的情况分两种排列方式取最大值else{// 方式1ll a1L*L/2;ll b1(L1)?1:4;ll c1(L-3)/2*4;ll ans1calcularMaxPerimetro(a1,b1,c1,N);// 方式2ll a2L*L/21;ll b20;ll c2(L-1)/2*4;ll ans2calcularMaxPerimetro(a2,b2,c2,N);ansmax(ans1,ans2);}coutansendl;}return0;}总结本题的关键洞察在于将问题转化为最小化相邻对数周长4N−2×相邻对数 4N - 2 \times \text{相邻对数}4N−2×相邻对数。贪心分类思想按照格子对周长的贡献4,0,−2,−44, 0, -2, -44,0,−2,−4从大到小选取。分奇偶性讨论棋盘染色的性质决定了最大孤立集的大小需要根据LLL的奇偶性分别处理。封闭形式计算最终得到一个O(1)O(1)O(1)的分段公式高效解决了LLL高达10610^6106的大数据问题。这种“分类贡献”的贪心思路在很多网格选择问题中都具有通用性值得深入理解和掌握。