20161022 NOIP模拟赛解题报告

好元素

【问题描述】

小A一直认为，如果在一个由N个整数组成的数列{An}中，存在以下情况：

Am+An+Ap = Ai (1 <= m, n, p < i <= N , m,n,p可以相同)，那么Ai就是一个好元素。

现在小A有一个数列，请你计算数列中好元素的数目。

【输入格式】

第一行只有一个正整数N，意义如上。

第二行包含N个整数，表示数列{An}。

【输出格式】

输出一个整数，表示这个数列中好元素的个数。

【输入样例】

Sample1

1 3

Sample2

1 2 3 5 7 10

Sample3

-1 2 0

【输出样例】

Sample1	1
Sample2	4
Sample3	1

【数据范围】

对于10%的数据1<=N<=10

对于40%的数据1<=N<=500 -10^5<=Ai<=10^5

对于70%的数据1<=N<=5000 -10^6<=Ai<=10^6

对于100%的数据1<=N<=5000 -10^9<=Ai<=10^9

————————————分割线————————————

10% n^4 随便做。

40% n^3 用布尔数组保存存在的元素，用三层枚举a[i],a[j],a[k]，如果a[i]+a[j]+a[k]存在，那么答案加1。注意枚举顺序和判重。

70% n^2 预处理两个数的和，再枚举，因为每一个元素值比较小，开一个数组来存储是否存在。(其实n^3的方法加上剪枝也可以过)

100% n^2 因为元素的值比较大，在70%的思想上用哈希进行判断即可。

拉链法Hash即可。

 1 #include "cstdio"
 2 #include "cstring"
 3 #include "algorithm"
 4 #include "iostream"
 5 #include "fstream"
 6 #include "stack"
 7 #include "set"
 8 #include "queue"
 9 #include "deque"
10 #include "ctime"
11 #include "cstdlib"
12 #include "sstream"
13 #include "cctype"
14 #include "cmath"
15 
16 using namespace std ;
17 const int MOD = 10000007 ;
18 const int maxN = 5e3 + 1e2 ; 
19 const int _max_ = 5e7 + 1e2 ; 
20 typedef long long QAQ ;
21 
22 int cnt ;
23 int Next[ MOD << 1 ] , Head[ MOD << 1 ] , End[ MOD << 1 ] ;
24 int A[ maxN ] ;
25 
26 inline int INPUT ( ) {
27         int x = 0 , f = 1 ; char ch = getchar ( ) ;
28         while ( ch < '0' || '9' < ch ) { if ( ch == '-' ) f = -1 ; ch = getchar ( ) ; }
29         while ( '0' <= ch && ch <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ; }
30         return x * f ; 
31 }
32 
33 inline int Hash_Function ( int x ) {return ( ( x % MOD ) + MOD ) % MOD ; }//散列函数 
34 
35 inline bool Find ( const int tmp ) {
36         int pos = Hash_Function ( tmp ) ;
37         int y ; 
38         for ( int i=Head[ pos ] ; y = End[ i ] , i ; i = Next[ i ] ) {//查找 
39                 if ( y == tmp ) return true ;
40         }
41         return false ; 
42 }
43 
44 inline void Hash_Link ( const int tmp , const int pos ) {//用链表拉链 
45         Next[ ++cnt ] = Head[ pos ] ; 
46         Head[ pos ] = cnt ;
47         End[ cnt ] = tmp ; 
48 }
49 
50 inline void Hash_Add ( const int tmp ) {
51         int pos = Hash_Function ( tmp ) ;
52         int y ;
53         for ( int i=Head[ pos ] ; y = End[ i ] , i ; i = Next[ i ] ) {
54                 if ( y == tmp ) return ; //判重 
55         }
56         Hash_Link ( tmp , pos ) ;   
57 }
58 
59 int main ( ) {
60         freopen ( "good.in" , "r" , stdin ) ;
61         freopen ( "good.out" , "w" , stdout ) ;
62         int N = INPUT ( ) ;
63         QAQ Ans = 0 ; 
64         for ( int i=1 ; i<=N ; ++i ) {
65                 A[ i ] = INPUT ( ) ;
66                 for ( int j=1 ; j<i ; ++j ) if ( Find ( A[ i ] - A[ j ] ) ) { ++Ans ; goto Loop ; }
67                 Loop : 
68                 for ( int j=1 ; j<=i ; ++j ) Hash_Add ( A[ i ] + A[ j ] ) ;
69         }
70         //cout << endl ;  
71         cout << Ans << endl ; 
72         return 0 ; 
73 }

View Code

2016-10-24 15:04:28

20161022 NOIP模拟赛 解题报告

20161022 NOIP模拟赛解题报告