题解 P6184 【[USACO08OCT]Building A Fence G】

BqtMtsZDnlpsT · 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 的值还在变大）。

• 代码

  #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记录