周末打了个GDUT的校赛，也是作为SCAU的一场个人排位。

比赛中竟然卡了个特判，1个半钟就切了5条了，然后一直卡。

还有其他两条可以做的题也没法做了，性格太执着对ACM来说也是错呀。

 

讲回正题 。

A  游戏王 . 

目的是集齐6张卡， 然后n个小伙伴手上持有卡num, 给出m种集合 , Stubird需要有某个集合中的卡片才能用c的花费去买这张卡片。

做法是状压dp ， 开一个 dp[st] ， 表示st（ 0 <= st < (1<<6) ） 这个集合最小花费 。

然后开一个邻接链表 g[st] 这样， 存着st这个状态可以去到那些状态 ， 费用是多少 。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std ; typedef long long LL ;typedef pair
           
             pii;#define X first#define Y secondconst int inf = 1e9+7;const int N = 1<<6 ; vector
            
             g[N];LL dp[N] ; int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int _ ; scanf("%d",&_); while( _-- ) { for( int i = 0 ; i < N ; ++i ) g[i].clear() , dp[i] = inf ; int n ; scanf("%d",&n); for( int i = 0 ; i < n ; ++i ) { int m , num ; scanf("%d%d",&m,&num); for( int j = 0 ; j < m ; ++j ) { int k ; scanf("%d",&k); int st = 0 , vst , c ; while( k-- ) { scanf("%d",&vst); st |= (1<
            
           
          
         
        
       
      

 

B.完美串  

给出一个01串，要该串取反再翻转后与原串相同，至少要多加多少个 0 or 1 。

输入串a后 ， 构造一个串b （ a取反再翻转 ） 求它们的最长公共子序列，这里是个dp ..

答案就是 n - dp[n][n] , 首先要证明 n - dp[n][n]  这个答案是无误的 。

要符合条件串长要偶数， 前半段跟后半段的以中线反对称的 。

设 最长公共子序列长度为 x  , 补充 n - x 个 0 ， 1 之后必然会符合题目要求，因为添加的时候符合反对称的性质。

那为何是 这个答案是最优？ 反证吧。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std ;const int N = 1010;int dp[N][N] , a[N] , b[N] ;char s[N];int main () {    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif // LOCAL    int _ ; scanf("%d",&_);    while( _-- ) {        int n ;        scanf("%d",&n);        memset( dp , 0, sizeof dp );        scanf("%s",s);        for( int i = 0 ; i < n ; ++i ) {            a[i+1] = s[i] - '0' ;        }        for( int i = n ; i > 0 ; --i ) {            b[i] = a[n-i+1] ;            b[i] ^= 1 ;        }//        for( int i = 1 ; i <= n ; ++i ) cout << a[i] ; cout <
         
        
       
      

 

C .  GCD = n ,  LCM = m 的对数

其实就是对 n , m 分解之后。 对其不同次幂质因子的分配方案数 。 比赛过程中加了一个错的特判。 搞得一直wa~

#include 
      
       #include 
       
        using namespace std ;const int N = 100010;long long fac[N] , cnt[N] , tot ;void solve( long long x ) {    for( long long i = 2 ; i * i <= x ; ++i ) if( x % i == 0 ){        fac[tot] = i ; cnt[tot] = 0 ;        while( x % i == 0 ) { x /= i ; cnt[tot]++ ; }        tot++ ;    }    if( x != 1 ) { fac[tot] = x ; cnt[tot] = 1 ; tot++ ; }}int main () {    int _ ; scanf("%d",&_);    while( _-- ) {        long long n , m ;        tot = 0 ;        scanf("%lld%lld",&n,&m);        if( m % n ) { puts("0"); continue ; }        solve(n); int c = 0 ;        for( int i = 0 ; i < tot ; ++i ) if( m % fac[i] == 0 ) {            int cc = 0 ;            while( m % fac[i] == 0 ) { m /= fac[i] ; cc++ ;}            if( cc != cnt[i] ) c++ ;        }        tot = 0 ; solve( m ) ; c += tot ;        long long ans = 1 ;        for( int i = 0 ; i < c - 1 ; ++i ) ans = ans * 2 ;        printf("%lld\n",ans);    }}
       
      

 

D . 煮菜 ， 一分钟可以同时煮 m 个菜 。

ti 为每个菜需要的时间， 若 sum = sigma(ti) ,  总时间 T = sum/m + ( sum % m ==0 ? 0 : 1 )  。

若 T   >  Max ( ti ) .. 是必然能够很配出方案使得时间为T 的 ， 否则结果就是 Max(ti) .

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std ;typedef pair
           
             pii;#define X first#define Y secondconst int N = 10010 ;int main () { int _ ; scanf("%d",&_); while( _-- ) { int sum = 0 , n , m , mx = -1 , x ; scanf("%d%d",&n,&m); for( int i = 0 ; i < n ; ++i ) { scanf("%d",&x); mx = max( mx , x ); sum += x ; } int t = ( sum / m ) + ( sum % m == 0 ? 0 : 1 ) ; int ans = max( mx , t ); printf("%d\n",ans); }}
           
          
         
        
       
      

 

E. 强迫症关灯

因为 n , m 只有100，直接暴力， 如果 n , m 达到1e6 的话就线段树吧

#include 
      
       #include 
       
        using namespace std ;int b[101];int main () {    int _ ; scanf("%d",&_);    while( _-- ) {        memset( b , 0 , sizeof b );        int n , m ; scanf("%d%d",&n,&m);        while( m-- ) {            int x ; scanf("%d",&x);            for( int i = x ; i <= n ; ++i ) {                if( !b[i] ) b[i] = x ;                else break ;            }        }        printf("%d",b[1]);        for( int i = 2 ; i <= n ; ++i ) {            printf(" %d",b[i]);        }puts("");    }}
       
      

 

F.找规律

题目都说了找规律，然后就暴力一下前100个看看规律，然后就可以看出来了

#include 
      
       using namespace std ;int main () {    int n ;    while( ~scanf("%d",&n) ) {        printf("%d\n",( n / 3 * 2 + ( n % 3 > 1 ? 1 : 0 ) ) );    }} /**************************************************************    Problem: 1122    User: hl_mark    Language: C++    Result: Accepted    Time:32 ms    Memory:964 kb****************************************************************/
      

 

G. 用多少条边可以把玩具连起来， 就是求连通分量个数，再-1

写并查集就可以实现了

#include 
      
       #include 
       
        using namespace std ;const int N = 100010;int fa[N] ;bool vis[N] ;inline int find( int k ) { return fa[k] = ( fa[k] == k ? k : find(fa[k])); }int main () {    int _ ; scanf("%d",&_);    while( _-- ) {        int n , m ; scanf("%d%d",&n,&m);        for( int i = 0 ; i <= n ; ++i ) fa[i] = i , vis[i] = false ;        while( m-- ) {            int x , y ; scanf("%d%d",&x,&y);            int fx = find(x) , fy = find(y);            fa[fy] = fx ;        }        int cnt = 0 ;        for( int i = 1 ; i <= n ; ++i )  {            int fx = find(i);            if( !vis[fx] ) { vis[fx] = true ; cnt++; }        }        printf("%d\n",cnt-1);    }} /**************************************************************    Problem: 1118    User: hl_mark    Language: C++    Result: Accepted    Time:132 ms    Memory:1972 kb****************************************************************/
       
      

 

F. 移动2只手指，点音符 。。

简单dp .. dp[i][j][k] 表示点到第i 个音符 , 第一只手指在 j , 第2只手指在 k 的最小花费

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std ;typedef pair
           
             pii;#define X first#define Y secondconst int N = 10010 ;int dp[N][6][6] , x[N] ;int main () { int _ ; scanf("%d",&_); while( _-- ) { int n ; scanf("%d",&n); for( int i = 1 ; i <= n ; ++i ) scanf("%d",&x[i]); memset( dp , 0x3f , sizeof dp ); int inf = dp[0][0][0] ; dp[0][0][0] = 0 ; for( int i = 0 ; i < n ; ++i ) { for( int j = 0 ; j < 5 ; ++j ) { for( int k = 0 ; k < 5 ; ++k ) { if( dp[i][j][k] >= inf ) continue ; dp[i+1][j][ x[i+1] ] = min( dp[i+1][j][ x[i+1] ] , dp[i][j][k] + abs( x[i+1] - k ) ); dp[i+1][ x[i+1] ][k] = min( dp[i+1][ x[i+1] ][k] , dp[i][j][k] + abs( x[i+1] - j ) ); } } } int ans = inf ; for( int i = 0 ; i < 5 ; ++i ) for( int j = 0 ; j < 5 ; ++j ) ans = min( ans , dp[n][i][j] ); printf("%d\n",ans); }} /************************************************************** Problem: 1115 User: hl_mark Language: C++ Result: Accepted Time:92 ms Memory:2932 kb****************************************************************/