自动搬运

查看原文

来自洛谷，原作者为

	BqtMtsZDnlpsT **

搬运于2025-08-24 22:18:18，当前版本为作者最后更新于2021-02-16 22:30:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

• 本题思路：暴 力 出 奇 迹。

  1. 首先设四条边长分别为 $a , b , c , d$ 且 $a \ge b \ge c \ge d$。

  2. 由初二所学内容可以发现 $a$ 的取值范围为是 $ \left \lceil \frac{N}{4}\right \rceil\le a < \left \lceil \frac{N}{2}\right \rceil $(下面一些题解上好像写 $a < \left \lfloor \frac{N}{2}\right \rfloor$，但是仔细一想就会发现，当 $a$ 为奇数时后者是错的)

  3. $\because\left\{\begin{matrix}b+c+d=N-a\\b \ge c\ge d\\ b \le a\end{matrix}\right.\; \therefore \left\lceil\frac{N-a}{3}\right \rceil \le b \le a$

  4. 同理，得 $\left\lceil\frac{N-a-b}{2}\right \rceil \le c \le b$。

  5. 所以，若求出 $a,b,c$，就可以得到 $d=N-a-b-c$。

• 所以，3重循环枚举 $a,b,c$，再根据 $a,b,c$ 算出 $d$。

• 由于要考虑顺序，手动枚举可以发现：

  | 情况 | 种数 | | :----------: | :----------: | :----------: | | $a=b=c=d$ | $1$ | | $a=b=c$ 或 $b=c=d$ | $4$ | | $a=b$ 且 $c=d$ | $6$ | | $a=b$ 或 $b=c$ 或 $c=d$ | $12$ | | $a>b>c>d$ | $24$ |

• 几个注意点

  1. 循环过程中 $d$ 的值计算出来可能小于等于 $0$，此时可以直接退出循环（因为 $c$ 的值还在变大）。
  2. $d$ 的值计算出来可能大于 $c$，不符合定义，此时不能退出循环（因为 $c$ 的值变大后 $d$ 会变小）。

• 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,s;
int S(int a,int b,int c,int d)//计算情况数
{
	if(a==b&&a==c&&a==d)return 1;
	if((a==b&&a==c)||(b==c&&c==d))return 4;
	if(a==b&&c==d)return 6;
	if(a==b||b==c||c==d)return 12;
	return 24;
}
int main()
{
	scanf("%d",&n);
	for(int i=(n+3)/4;i<(n+1)/2;i++)//i对应a
		for(int j=(n-i+2)/3;j<=i;j++)//j对应b
			for(int k=(n-i-j+1)/2;k<=j;k++)//k对应c
			{
				int l=n-i-j-k;//计算d
				if(l<=0)break;
				if(l>k)continue;
				s+=S(i,j,k,l);
			}
	printf("%d",s);
}

• AC记录