本文主要是介绍【UVALive】2965 Jurassic Remains 中途相遇法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【UVALive】2965 Jurassic Remains
题目分析：本题用了一个很不错的思想——中途相遇法。
因为题目的数据很小，我们很容易想到暴力，但是2^24次方的枚举依旧复杂度太大，因此我们可以这么做：将一半的串枚举异或能得到的所有的值，插入到map中，然后再枚举异或另一半的串能得到的所有的值，然后查找map中的与这个值相同的有没有，更新一下能得到的最大数量即可。
成功将复杂度降低了一大半。
也算是一个蛮重要的思想吧
代码如下：
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )const int MAXN = 30 ;
const int MAXM = 10005 ;map < int , int > mp ;
int a[MAXN] ;
int n ;
int cnt[MAXM] ;
char s[MAXM] ;int count ( int x ) {int res = 0 ;while ( x ) {if ( x & 1 )++ res ;x >>= 1 ;}return res ;
}void insert ( int key , int value ) {map < int , int > :: iterator it = mp.find ( key ) ;if ( it == mp.end () )mp.insert ( map < int , int > :: value_type ( key , value ) ) ;else if ( cnt[it -> second] < cnt[value] )it -> second = value ;
}void solve () {mp.clear () ;CLR ( a , 0 ) ;REP ( i , 0 , n ) {scanf ( "%s" , s ) ;for ( int j = 0 ; j < s[j] ; ++ j )a[i] ^= ( 1 << ( s[j] - 'A' ) ) ;}int nn = n / 2 , m = ( 1 << nn ) ;REP ( S , 0 , m ) {int key = 0 ;REP ( i , 0 , nn )if ( S & ( 1 << i ) )key ^= a[i] ;insert ( key , S ) ;}m = ( 1 << ( n - nn ) ) ;int ans = 0 ;int buf = 0 ;REP ( S , 0 , m ) {int key = 0 ;REP ( i , 0 , n - nn )if ( S & ( 1 << i ) )key ^= a[i + nn] ;map < int , int > :: iterator it = mp.find ( key ) ;if ( it != mp.end () ) {int tmp = cnt[S] + cnt[it -> second] ;int value = ( S << nn ) | ( it -> second ) ;if ( tmp > ans ) {ans = tmp ;buf = value ;}}}int flag = 0 ;printf ( "%d\n" , ans ) ;REP ( i , 0 , n )if ( buf & ( 1 << i ) ) {if ( flag )printf ( " " ) ;flag = 1 ;printf ( "%d" , i + 1 ) ;}printf ( "\n" ) ;
}int main () {REP ( i , 0 , MAXM )cnt[i] = count ( i ) ;while ( ~scanf ( "%d" , &n ) )solve () ;return 0 ;
}这篇关于【UVALive】2965 Jurassic Remains 中途相遇法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
