T1

hanoi 解题思路：

对于这道题，我们已知的是当 M = 2 时，这就是我们已知的【汉诺塔问题】。那么我们的思路就可以是用解决汉诺塔问题的思路来解决这道题。

# include <cstdio> # include <cstring> # include <iostream> # include <algorithm> using namespace std ; # define Name "hanoi" # define LL long long LL dp [70] [70] ; int main () { freopen ( Name ".in" , "r" , stdin ) ; freopen ( Name ".out" , "w" , stdout ) ; memset ( dp , 0x3f , sizeof dp ) ; int n , m ; scanf ( "%d%d" , & n , & m ) ; dp [1] [3] = 1 ; for ( int i = 2 ; i <= n ; ++ i ) dp [i] [2] = 0 , dp [i] [3] = ( 1LL << i ) - 1LL ; for ( int i = 3 ; i <= m ; ++ i ) dp [1] [i] = 1 ; for ( int i = 2 ; i <= n ; ++ i ) for ( int j = 4 ; j <= m ; ++ j ) for ( int r = 1 ; r < i ; ++ r ) dp [i] [j] = min ( dp [i] [j] , dp [ i - r ] [j] * 2 + dp [r] [ j - 1 ] ) ; printf ( "%lld" , dp [n] [m] ) ; return 0 ; }

T2

水

# include <vector> # include <cstdio> # include <cstring> # include <iostream> # include <algorithm> # define LL long long # define Name "rank" using namespace std; const int N = 2e5 + 10 ; char ch [N] ; struct P { int len , rk ; bool operator < ( const P & x ) const { return rk < x.rk ; } } a [N] ; int rk [N] ; int n ; int id ( int len ) { return n - len + 1 ; } int main () { freopen ( Name ".in" , "r" , stdin ) ; freopen ( Name ".out" , "w" , stdout ) ; memset ( ch , '\0' , sizeof ch ) ; scanf ( "%d" , & n ) ; for ( int i = 1 ; i <= n ; ++ i ) { scanf ( "%d" , & a [i].rk ) ; rk [ n - i + 1 ] = a [i].rk ; a [i].len = n - i + 1 ; } sort ( a + 1 , a + 1 + n ) ; for ( int i = 1 ; i < n ; ++ i ) { int l1 = a [i].len - 1 ; int l2 = a [ i + 1 ].len - 1 ; if ( rk [l1] > rk [l2] ) { if ( ch [ id ( l1 + 1 ) ] == '\0' ) ch [ id ( l1 + 1 ) ] = 'a' ; if ( ch [ id ( l2 + 1 ) ] == '\0' ) ch [ id ( l2 + 1 ) ] = ch [ id ( l1 + 1 ) ] + 1 ; if ( ch [ id ( l2 + 1 ) ] > ch [ id ( l1 + 1 ) ] + 1 ) { printf ( "-1" ) ; return 0 ; } } else { if ( ch [ id ( l1 + 1 ) ] == '\0' ) ch [ id ( l1 + 1 ) ] = 'a' ; if ( ch [ id ( l2 + 1 ) ] == '\0' ) ch [ id ( l2 + 1 ) ] = ch [ id ( l1 + 1 ) ] ; if ( ch [ id ( l2 + 1 ) ] != ch [ id ( l1 + 1 ) ] ) { printf ( "-1" ) ; return 0 ; } } } for ( int i = 1 ; i <= n ; ++ i ) { if ( ch [i] < 'a' || ch [i] > 'z' ) { printf ( "-1" ) ; return 0 ; } } for ( int i = 1 ; i <= n ; ++ i ) printf ( "%c" , ch [i] ) ; return 0 ; }

T3

期望概率神题：

# include <vector> # include <cstdio> # include <cstring> # include <iostream> # include <algorithm> # define LL long long # define Name "" using namespace std ; const int N = 2e5 + 10 ; const int P = 17 ; const LL Mod = 1e9 + 7 ; vector <int> G [N] ; int sz [N] , dep [N] , fa [N] [20] ; int n , q ; LL f [N] , g [N] , pw [30] ; int LCA ( int u , int v ) { if ( dep [u] < dep [v] ) swap ( u , v ) ; int t = dep [u] - dep [v] ; for ( int i = 0 ; pw [i] <= t ; ++ i ) if ( pw [i] & t ) u = fa [u] [i] ; for ( int i = P ; i >= 0 ; -- i ) { if ( fa [u] [i] != fa [v] [i] ) { u = fa [u] [i] ; v = fa [v] [i] ; } } if ( u == v ) return u ; return fa [u] [0] ; } void dfs ( int u , int fat ) { fa [u] [0] = fat ; for ( int i = 1 ; i <= P ; ++ i ) fa [u] [i] = fa [ fa [u] [ i - 1 ] ] [ i - 1 ] ; sz [u] = 1 ; for ( int i = 0 ; i < G [u].size () ; ++ i ) { int v = G [u] [i] ; if ( v == fat ) continue ; dep [v] = dep [u] + 1 ; dfs ( v , u ) ; sz [u] += sz [v] ; } } void dfs_da ( int u , int fat ) { for ( int i = 0 ; i < G [u].size () ; ++ i ){ int v = G [u] [i] ; if ( v == fat ) continue ; f [v] = ( LL ) ( f [u] + 2LL * ( n - sz [v] ) - 1LL ) % Mod ; g [v] = ( LL ) ( g [u] + 2LL * sz [v] - 1LL ) % Mod; dfs_da ( v , u ) ; } } int main () { freopen ("tree.in", "r", stdin); freopen ("tree.out", "w", stdout); pw [0] = 1 ; for ( int i = 1 ; i <= P ; ++ i ) pw [i] = pw [ i - 1 ] * 2 ; scanf ( "%d%d" , & n , & q ) ; for ( int i = 1 ; i < n ; ++ i ) { int x , y ; scanf ( "%d%d" , & x , & y ) ; G [x].push_back ( y ) ; G [y].push_back ( x ) ; } dfs ( 1 , 1 ) ; dfs_da ( 1 , 1 ) ; while ( q -- ) { int u , v ; scanf ( "%d%d" , & u , & v ) ; int x = LCA ( u , v ) ; // printf ( ">%d %d %d \n" , u , v , x ) ; printf ( "%lld\n" , ( ( f [v] - f [x] + g [u] - g [x] ) % Mod + Mod ) % Mod ) ; } return 0 ; }