[机房测试]10.23

sss02 140大众低分送命了

欢迎转载ssw02的博客:https://www.cnblogs.com/ssw02/p/11728722.html

一个多次询问必经点的问题。

可以用灭绝树搞他。支配树板子

因为是DAG ，所以我们在跑DAG的是后将已经遍历过的点的父亲节点赋值为lca（前父亲，当前节点），倍增求lca的dep即可。

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 100005 ;
inline int read(){
    int s=0 ; char g=getchar() ; while( g>'9'||g<'0' )g=getchar() ;
    while( g>='0'&&g<='9' )s=s*10+g-'0',g=getchar() ; return s ;
}
int N , M , Q , dep[ MAXN ] , anc[MAXN][20] ;
int to[MAXN] , nex[MAXN] , head[MAXN] , tot = 1 ;
bool vis[MAXN] ;
void  add( int x , int y ){
    to[ ++tot ] = y , nex[ tot ] = head[ x ] , head[x] = tot ;
}
int  lca( int x , int  y ){
    if( dep[x] < dep[y] )swap( x , y ) ;
    int t = dep[x] - dep[y] ;
    for( int p = 0 ; t ; t >>= 1 , p++ )
        if( t&1 )x = anc[x][p] ;
    if( x == y )return x ;
    for( int p = 17 ; anc[x][0] != anc[y][0] ; --p )
        if( anc[x][p] != anc[y][p] )x=anc[x][p] , y=anc[y][p] ;
    return anc[x][0] ;
}
void  dfs( int u , int fa ){
    anc[u][0] = fa ;
    for( int i = 1 ; i <= 17 ; ++i )anc[u][i] = anc[ anc[u][i-1] ][i-1] ;
    for( int i = head[u] ; i ; i = nex[i] ){
        if( to[i] == fa )continue ;
        dep[ to[i] ] = dep[u] + 1 ;
        dfs( to[i] , u ) ;
    }
}
void  dfs2( int u , int fa ){
    if( !anc[u][0] ){
        anc[u][0] = fa ;
        for( int i = 1 ; i <= 17 ; ++i )anc[u][i] = anc[ anc[u][i-1] ][i-1] ;
    }
    for( int i = head[u] ; i ; i = nex[i] ){
        if( to[i] == fa )continue ;
        dep[ to[i] ] = dep[u] + 1 ;
        if( vis[to[i]] ){
            int fat = lca( anc[ to[i] ][0] , u ) ;
            anc[ to[i] ][0] = fat ; dep[ to[i] ] = dep[fat] + 1 ;
            for( int j = 1 ; j <= 17 ; ++j )anc[ to[i] ][j] = anc[ anc[to[i]][j-1] ][j-1] ;
        }
        vis[to[i]] = true ;
        dfs2( to[i] , u ) ;
    }
}
void  work1(){
    int m1 , m2 , now ;
    for( int i = 1 ; i <= M ; ++i ){
        m1 = read() , m2 = read() ;
        add( m1 , m2 ) ;
    }
    dfs( 1 , 1 ) ;
    while( Q-- ){
        m1 = read() ;
        if( m1 == 0 )printf("0\n") ;
        else if( m1 == 1 ){
            m2 = read() ;
            printf("%d\n",dep[m2]+1 ) ;
        }
        else{
            now = read() , m2 = read() ; now = lca( now , m2 ) ;
            for( int i = 3 ; i <= m1 ; ++i ){
                m2 = read() ; now = lca( now , m2 ) ;
            }
            printf("%d\n",dep[now]+1) ;
        }
    }
}
void  work2(){
    vis[1] = true;
    int m1 , m2 , now ;
    for( int i = 1 ; i <= M ; ++i ){
        m1 = read() , m2 = read() ;
        add( m1 , m2 ) ;
    }
    dfs2( 1 , 1 ) ;
    while( Q-- ){
        m1 = read() ;
        if( m1 == 0 )printf("0\n") ;
        else if( m1 == 1 ){
            m2 = read() ;
            printf("%d\n",dep[m2]+1 ) ;
        }
        else{
            now = read() , m2 = read() ; now = lca( now , m2 ) ;
            for( int i = 3 ; i <= m1 ; ++i ){
                m2 = read() ; now = lca( now , m2 ) ;
            }
            printf("%d\n", dep[now]+1 ) ;
        }
    }
}
int main(){
    freopen("attack.in","r",stdin) ;
    freopen("attack.out","w",stdout ) ;
    N = read() , M = read() , Q = read() ;
    if( M == N-1 )work1() ;
    else work2() ;
}

大水题，N^2 T 都可以过的就不用打hash了嘛。。。
题目的字典序最大是骗人的，合法最长情况只有一种

#include<bits/stdc++.h>
using namespace std ;
int T , lena , lenb , lenans=0 ;
char a[1005],b[1005],c[1005],ans[1005];
bool  check( char x[] , char  y[] ){
    int  len = strlen(x) , lenn = strlen(y) ;
    if( len != lenn )return false  ;
    for( int i = 0 ; i < len ; ++i )
        if( x[i] != y[i] )return false ;
    return true ;
}
void  updata( char x[] ){
    int len = strlen( x ) , minn = min( len , lenans ) , flag = 0 ;
    if( len < lenans )return ;
    if( len > lenans ){
        memset( ans , 0 , sizeof(ans) ) ; lenans = len ;
        for( int i = 0 ; i < len ; ++i )ans[i] = x[i] ;return ;
    }
    for( int i = 0 ; i < len ; ++i )
        if( x[i] > ans[i] ){flag=1;break;}
        else if( x[i] < ans[i] ){flag=-1;break;}
    if( flag == 0 && len > lenans )flag = 1 ;
    if( flag == 1 ){
        memset( ans , 0 , sizeof(ans) ) ;
        for( int i = 0 ; i < len ; ++i )ans[i] = x[i] ;
    }
}
void  rev(){
    memset( c , 0 , sizeof(c) ) ;
    //cout<<a<<"   YYYYY   "<<endl ;
    for( int i = 0 ; i < lena ; ++i )c[lena-i-1] = a[i] ;
    for( int i = 0 ; i < lena ; ++i )a[i] = c[i] ;
    //cout<<a<<"   XXXXX   "<<endl<<endl ;
}
void  work(){
    if( check(a,b) ){cout<<a<<endl ; return ; }
    while( lena != 0 && lenb !=0 ){
        while( lena != lenb ){
            if( lena < lenb ){swap(lena,lenb);swap(a,b);}
            lena-- ;
            if( a[lena]=='A' )a[lena]=0 ;
            else {
                a[lena] = 0 ; rev() ;
            }
        }
        if( lena == lenb ){
            if( check( a , b ) )updata( a ) ;
            lena-- ;
            if( a[lena]=='A' )a[lena]=0 ;
            else {
                a[lena] = 0 ; rev() ;
            }
        }
    }
    if( lenans == 0 )printf("-1\n");
    else cout<<ans<<endl ;
}
int main(){
    freopen("reverse.in","r",stdin);
    freopen("reverse.out","w",stdout) ;
    scanf("%d",&T);
    while( T-- ){
        memset( ans , 0 , sizeof(ans) ) ;
        lenans=0 ;
        scanf("%s",a) ; scanf("%s",b) ;
        lena = strlen(a) , lenb = strlen(b) ;
        work() ;

    }
}

分情况的期望DP

YYR讲过加强版，以后总结是一起放链接。

ssw02滚去颓废和复习概率期望了。