首页 > 代码库 > Code[VS] 1230 题解
Code[VS] 1230 题解
1230 元素查找
题目描述 Description
给出n个正整数，然后有m个询问，每个询问一个整数，询问该整数是否在n个正整数中出现过。
输入描述 Input Description
第一行两个整数 n 和m。
第二行n个正整数（1<=n<= 100000）
第三行m个整数(1<=m<=100000)
输出描述 Output Description
一共m行，若出现则输出YES，否则输出NO
样例输入 Sample Input
4 2
2 1 3 4
1 9
样例输出 Sample Output
YES
NO
数据范围及提示 Data Size & Hint
所有数据都不超过10^8
———————————————分割线———————————————
Hash Table 练习题
#include "bits/stdc++.h"using namespace std ;const int MOD = 10000007 ;const int maxN = 1e5 + 1e3 ; typedef long long QAQ ;int cnt ;int Next[ MOD << 1 ] , Head[ MOD << 1 ] , End[ MOD << 1 ] ;int A[ maxN ] ;inline int INPUT ( ) { int x = 0 , f = 1 ; char ch = getchar ( ) ; while ( ch < ‘0‘ || ‘9‘ < ch ) { if ( ch == ‘-‘ ) f = -1 ; ch = getchar ( ) ; } while ( ‘0‘ <= ch && ch <= ‘9‘ ) { x = ( x << 1 ) + ( x << 3 ) + ch - ‘0‘ ; ch = getchar ( ) ; } return x * f ; }inline int Hash_Function ( int x ) {return ( ( x % MOD ) + MOD ) % MOD ; }inline bool Find ( const int tmp ) { int pos = Hash_Function ( tmp ) , y ; for ( int i=Head[ pos ] ; y = End[ i ] , i ; i = Next[ i ] ) if ( y == tmp ) return true ; return false ; }inline void Hash_Link ( const int tmp , const int pos ) { Next[ ++cnt ] = Head[ pos ] ; Head[ pos ] = cnt ; End[ cnt ] = tmp ; }inline void Hash_Add ( const int tmp ) { int pos = Hash_Function ( tmp ) , y ; for ( int i=Head[ pos ] ; y = End[ i ] , i ; i = Next[ i ] ) if ( y == tmp ) return ; Hash_Link ( tmp , pos ) ; }int main ( ) { int N = INPUT ( ) , Q = INPUT ( ) ; for ( int i=1 ; i<=N ; ++i ) { A[ i ] = INPUT ( ) ; if ( !Find ( A[ i ] ) ) Hash_Add ( A[ i ] ) ; } while ( Q -- ) { if ( Find ( INPUT ( ) ) ) cout << "YES" << endl ; else cout << "NO" << endl ; } return 0 ; }
2016-10-26 00:14:00
Code[VS] 1230 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。