3508. 【NOIP2013模拟11.5B组】好元素(good)
(File IO): input:good.in output:good.out
Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits
Goto ProblemSet做法:预处理ai + aj可以达到的值,用hash存起来,然后枚举l, k就好了
代码如下:
View Code
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <iostream> 5 #include <algorithm> 6 #define N 5007 7 #define mo 14150547 8 #define z 2000000000 9 #define LL long long 10 using namespace std; 11 LL n, a[N], h[mo + 1]; 12 int ans; 13 bool f; 14 15 LL hash(LL x) 16 { 17 LL p = x % mo; 18 while (h[p] != 0 && h[p] != x - z && p <= mo) p = (p + 1) % mo; 19 return p; 20 } 21 22 void work() 23 { 24 for (int i = 1; i <= n; i++) 25 { 26 for (int j = 1; j < i; j++) 27 if (h[hash(a[i] - a[j] + z)] == a[i] - a[j] && a[i] - a[j] != 0) 28 { 29 ans++; 30 break; 31 } 32 else if (a[i] - a[j] == 0) 33 { 34 if (f) 35 { 36 ans++; 37 break; 38 } 39 } 40 for (int j = 1; j <= i; j++) 41 { 42 LL p = (a[i] + a[j] + z) % mo; 43 while (h[p] != a[i] + a[j] && h[p] != 0 && p <= mo) p = (p + 1) % mo; 44 if (a[i] + a[j] != 0) h[p] = a[i] + a[j]; 45 else f = true; 46 } 47 } 48 } 49 50 int main() 51 { 52 freopen("good.in", "r", stdin); 53 freopen("good.out", "w", stdout); 54 scanf("%lld", &n); 55 for (int i = 1; i <= n; i++) 56 scanf("%lld", &a[i]); 57 work(); 58 cout << ans; 59 }