P10467 建议使用4重哈希
  • 板块灌水区
  • 楼主A_chicken_boy
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/22 15:01
  • 上次更新2024/7/22 15:27:45
查看原帖
P10467 建议使用4重哈希
774204
A_chicken_boy楼主2024/7/22 15:01

题目

#include <bits/stdc++.h>

using namespace std ;

#define f(i,a,b) for ( int i = (a) ; i<=(b) ; ++i )

#define base 1331

#define base2 1293331
#define base3 73495
#define base4 324235
#define mod 7037021
#define mod2 9247332
#define mod3 3489753
#define mod4 353549
#define N 10000005
#define ull unsigned long long 
int n ;
int a[10] ;
int ni1[10] , ni2[10] , ni3[10]  , ni4[10] , cnt4 ,cnt1 , cnt2 , cnt3 ;
int p1[N] , p2[N] , p3[N] , p4[N];	
unsigned long long  s1 , s2 , s3 , s4 , s5 , s6 , s7 , s8 ;
int main ( ){
	cin >> n ;
	f(i,1,n){
		f(j,1,6){
			cin >> a[j] ;
		}
		f(j,1,6){
			cnt1 = cnt2 = cnt3 = cnt4 = 0 ;
		 	s1 = s2 = s3 = s7 = 0 ;
			int cnt = j ;
			f(i,1,6){
				s1 = (s1 * base) ;
				s2 = (s2 * base2) ;	
				s3 = ( s3 * base3 ) ;			
				s7 = ( s7 * base4 ) ;
				s1 += a[cnt] ;
				s2 += a[cnt] ;
				s3+=a[cnt] ;
				s7 += a[cnt] ;
				if ( cnt == 6 ) cnt = 1 ;
				else cnt++ ;
			}
			s4 = s5 = s6  = s8 = 0 ;
			f(i,1,6){
				s4 = (s4 * base)   + a[cnt]  ;
				s5 = (s5 * base2)  + a[cnt] ;
				s6 = ( s6 * base3 ) + a[cnt] ;
				s8 = ( s8 * base4 ) + a[cnt] ;
				if ( cnt == 1 ) cnt = 6 ;
				else cnt-- ;
			}
			ull nihao = s1+ s4 ;
			nihao %= mod ;
			ni1[++cnt1] = nihao ;
			ull nihao2 = s2 + s5 ;	
			nihao2 %= mod2 ;
			ni2[++cnt2] = nihao2 ;
			ull nihao3 = s3 + s6 ;
			nihao3 %= mod3 ;
			ni3[++cnt3] = nihao3 ;
			ull nihao4 = s7 + s8 ;
			nihao4 %= mod4 ;
			ni4[++cnt4] = nihao4 ;
			//cout << j << " " << nihao << " " << nihao2 << endl ;
			if (  p1[nihao] == 1 && p2[nihao2] == 1 && p3[nihao3] == 1 && p4[nihao4] == 1 ){
				cout << "Twin snowflakes found." ;	
				return 0 ;
			}
		}		
			for ( int o = 1 ; o <= 6 ; ++o ){
				p1[ni1[o]] = 1  , p2 [ni2[o]] = 1 , p3[ni3[o]] = 1 , p4[ni4[o]] = 1 ;					
			}
	}
	cout << "No two snowflakes are alike." ;
	return 0 ;

}
2024/7/22 15:01
加载中...