2018.12.08【NOIP提高组】模拟B组总结

• diyiti
• 保留道路
• 进化序列
• B

• diyiti

Description

给定n 根直的木棍，要从中选出6 根木棍，满足：能用这6 根木棍拼出一个正方形。注意木棍不能弯折。问方案数。

正方形：四条边都相等、四个角都是直角的四边形。

Input

第一行一个整数n。

第二行包含n 个整数ai，代表每根木棍的长度。

Output

一行一个整数，代表方案数。

Sample Input

8

4 5 1 5 1 9 4 5

Sample Output

3

Data Constraint

对于20% 的数据，满足：n ≤ 30

对于40% 的数据，满足：n ≤ 200

对于60% 的数据，满足：n ≤ 1000

对于100% 的数据，满足：n ≤ 5000; 1 ≤ ai ≤ 10^7

个人解析

该题名字过于草率

这道题分3 1 1 1和2 2 1 1两种情况

——WMY

至于此，我们来分类讨论

1. 3 1 1 1
   
   对于此种情况，我们先枚举“1”。这应该很好操作
   
   然后，“3”让我蒙了个X。
   
   以下为上面我那无用的大脑补一下

先用n2预处理出两两交合的情况，反正数据小，开个桶也没事。

因为可能会出现重复出现的情况，所以，我们要判重

不要吝啬自己的空间，再开一个桶