本文主要是介绍【HDU】4876 ZCC loves cards 暴力,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门:【HDU】4876 ZCC loves cards
题目分析:
这题无力吐嘈。。。。能想到的优化都用上吧。。。
代码如下:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )const int MAXN = 40000 ;int n , K ;
int card[25] ;
int a[6] ;
int A[MAXN][6] ;
int cnt ;
int vis[130] ;
int G[6][6] ;
int L ;
int ans ;
int Time ;
int b[MAXN] ;
int c[7][2] ;void dfs ( int cur , int j ) {if ( cur == K ) {REP ( i , K )A[cnt][i] = a[i] ;++ cnt ;return ;}REPF ( i , j , n - 1 ) {a[cur] = card[i] ;dfs ( cur + 1 , i + 1 ) ;}
}int better ( int o ) {++ Time ;int top = 0 , tmp ;b[top ++] = 0 ;REP ( i , K ) {tmp = top ;REP ( j , top )b[tmp ++] = A[o][i] ^ b[j] ;top = tmp ;}REP ( i , top )vis[b[i]] = Time ;REPF ( i , L , ans + 1 )if ( vis[i] != Time )return 0 ;return 1 ;
}void dfs3 ( int N , int cur ) {if ( cur == K ) {++ Time ;int x = 0 ;REP ( i , K )x ^= a[i] ;REP ( i , K ) {int y = 0 ;REPF ( j , i , K - 1 ) {y ^= a[j] ;vis[y] = Time ;vis[x ^ y] = Time ;}}int tot = L - 1 ;while ( vis[tot + 1] == Time )++ tot ;if ( tot >= L )ans = max ( ans , tot ) ;return ;}REPF ( i , 1 , N )if ( c[i][1] ) {-- c[i][1] ;a[cur] = c[i][0] ;dfs3 ( N , cur + 1 ) ;++ c[i][1] ;}
}void solve () {cnt = 0 ;REP ( i , n )scanf ( "%d" , &card[i] ) ;sort ( card , card + n ) ;dfs ( 0 , 0 ) ;CLR ( vis , 0 ) ;Time = 0 ;ans = 0 ;REP ( i , cnt ) {if ( !better ( i ) )continue ;int tot = 0 ;REP ( j , K ) {if ( !j || A[i][j] != A[i][j - 1] ) {c[++ tot][0] = A[i][j] ;c[tot][1] = 0 ;}++ c[tot][1] ;}a[0] = c[1][0] ;-- c[1][1] ;dfs3 ( tot , 1 ) ;}printf ( "%d\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d%d" , &n , &K , &L ) )solve () ;return 0 ;
}
这篇关于【HDU】4876 ZCC loves cards 暴力的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!