暴力枚举三角
油菜花这是暴力枚举类型的一道算法题
妖梦拼木棒
题目描述
有n根木棒,现在从中选4根,想要组成一个正三角形,问有几种选法?
输入格式
第一行一个整数n;第二行往下n 行,每行一个整数,代表木棒的长度
解释
1.先统计最小的ai和最大的ai,和每个长度木棒各有几根,即bi;
2.4根木棒中,必须有两根木棒长度相等且不是最短的;
3.从第二小的开始枚举(因为最小的不能通过别的木棒合成),看此木棒是不是有两根,没有就下一个;
4.通过i/2和bi来确定用来合成的第一根木棒j,通过i-j确定另一根
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include<iostream> #include<fstream> #include<cstdio> #include<cmath> #include<queue> #include<string> #include<cstring> #include<string.h> #include<algorithm> #include<iomanip> using namespace std; int n,b[5010],a[1000010],minn=1e9,maxx; long long ans; const int mod=1e9+7; int main() { cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; minn=min(minn,a[i]); maxx=max(maxx,a[i]); b[a[i]]++; } for(int i=minn+1; i<=maxx; i++) { if(b[i]>1) for(int j=minn; j<=i/2; j++) if(b[j]>=1&&b[i-j]>=1) { if(j*2!=i)ans=(ans+(b[i]*(b[i]-1)/2)*b[j]*b[i-j]%mod)%mod; else if(b[j]>1)ans=(ans+((b[i]*(b[i]-1)/2)*(b[j]*(b[j]-1)/2)%mod)%mod)%mod; } } cout<<ans%mod; return 0; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| import java.util.Scanner;
public class Main { static Scanner sc; static int MO = 1000000007; static int n; static int[] num; static int max = 0; static int temp; static int sum = 0; public static void main(String[] args) { sc = new Scanner(System.in); n = sc.nextInt(); num = new int[5001]; for (int i = 0; i < n; i++) { temp = sc.nextInt(); if (temp > max) { max = temp; } num[temp]++; }
for (int i = 2; i <= max; i++) { if (num[i] >= 2) { int fs = C(num[i], 2) % MO; for (int j = 1; j <= i / 2; j++) { if (j == i - j && num[j] >= 2) { sum = (sum + fs * C(num[j], 2)) % MO; } if (j != i - j && num[j] >= 1 && num[i-j] >= 1) { sum = (sum + fs * C(num[j], 1) * C(num[i-j], 1)) % MO; } } } } System.out.println(sum); }
public static int C(int k, int r) { if (r == 1) { return k % MO; } return (k * (k - 1) / 2) % MO; } }
|