[SPOJ] ABCDEF – ABCDEF
原题:http://www.spoj.com/problems/ABCDEF/ 题目大意:计算一个集合S,范围在[-30000,30000], 其中所有的可能的整数abcdef. 满足: (a*b+c)/d-e=f, where d !=0. 问多少种情况 分析: 公式题, 首先是整数取值, 所以就不难.先化简成a*b+c=d(e+f), 然后数一下左边集合中每个在右边的的个数. 注意: 这里是每个元素, 包括重复的. SPOJ真是卡空间, 用map直接TLE, 好好自己写counter吧. d不能是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 |
public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = in.readInt(); } Arrays.sort(nums); int[] left = new int[n*n*n]; int p = 0; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { for (int k = 0; k < nums.length; k++) { left[p++] = nums[i] * nums[j] + nums[k]; } } } Arrays.sort(left, 0, n*n*n); int[][] range = new int[2][left.length]; p = 0; long count = 0; int tmp = Integer.MAX_VALUE; for (int i = 0; i < left.length; i++) { if (tmp != left[i]){ range[0][p] = left[i]; range[1][p]++; p++; } else { range[1][p-1]++; } tmp = left[i]; } for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { for (int k = 0; k < nums.length; k++) { if (nums[i] == 0) continue; else { int right = nums[i]*(nums[j]+nums[k]); int b = Arrays.binarySearch(range[0], 0, p, right); if (b >= 0) count+= range[1][b]; } } } } out.print(count); } |