1
#includeusing namespace std ; struct bigInt { int num[ 2000 ] ; int size ; static const int maxN = 2000 ; private : void Init ( ) { size = 0 ; for ( int i=1 ; i<=maxN ; ++i ) num[ i ] = 0 ; } public : void toInt ( char *ch ) { Init ( ) ; size = strlen ( ch ) ; for ( int i=0 ; i = 10 ) { num[ i ] -= 10 ; up = true ; } } if ( up ) num[ size++ ] = 1; } public : void print ( ) { for ( int i=size-1 ; i>=0 ; --i ) { printf ( "%d" , num[ i ] ) ; } putchar ( '\n' ) ; }} A , B; char str1[ 100 ] , str2[ 100 ] ;int main ( ) { while ( scanf ( "%s%s" , str1 , str2 ) != EOF ) { A.toInt (str1) ; B.toInt (str2) ; A.Plus ( B ) ; A.print ( ) ; } return 0 ; }
3
#includeusing namespace std ; const int maxN = 10010 ; const int maxM = 100010 ; struct Edge { int to,from,date;}e[ maxM ] ;int father[ maxM ] ; bool crash[ maxM ] ; bool cmp ( Edge a , Edge b ) { return a.date > b.date ; }int getfa ( int x ) { return father[ x ] == x ? x : father[ x ] = getfa ( father[ x ] ) ;}inline int INPUT ( ) { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}void Init ( const int N , const int M ) { for ( int i=1 ; i<=N ; ++i ) { father[ i ] = i ; } sort( e + 1 , e + M + 1 , cmp ) ;}void Debug ( int n ) { for ( int i=1 ; i<=n ; ++i ) { cout << e[ i ].date << endl ; }}int main ( ) { int N = INPUT ( ) , M = INPUT ( ) ; memset ( crash , false , sizeof ( crash ) ) ; for ( int i=1 ; i<=M ; ++i ) { e[ i ].to = INPUT ( ) ; e[ i ].from = INPUT ( ) ; e[ i ].date = INPUT ( ) ; } Init ( N , M ) ; //Debug(M); for ( int i=1 ; i<=M ; ++i ) { int px = getfa( e[ i ].to ) ; int py = getfa( e[ i ].from ) ; if ( px != py ) { father[ px ] = py ; crash[ e[ i ].date ] = true ; } } int _cnt = 0 ; for ( int i=1 ; i<=maxM ; i++ ) { if ( crash[ i ] ) _cnt++ ; } printf ( "%d\n" , _cnt ) ; return 0 ; }
4
#includeusing namespace std ; typedef long long ll ; ll k ;ll QP ( ll a , ll b ) { ll ret = 1 , base = a ; while( b ) { if ( b & 1 ) ret = ret * base % k ; base = base * base % k ; b >>= 1 ; } return ret ;}int main ( ) { ll b , n ; cin >> b >> n >> k ; cout << QP ( b , n ) % k << endl ; return 0 ; }
6
#includeusing namespace std;int ans[ 14 ][ 14 ][ 14 ][ 14 ] ;int card[ 5 ] , v[ 5 ] , buc[ 15 ] ;int IN ( ) { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int tot;bool wxn ( int s ) { for ( int i=0 ; i<=4 ; ++i ) if ( card[ i ] >= 5 ) return false ; if ( s > 10 ) return false ; return true ;}bool whn ( ) { for ( int i=0 ; i<=4 ; ++i ) if ( card[ i ] <= 10 ) return false ; return true ;}bool boom ( ) { memset ( buc , 0 , sizeof( buc ) ) ; for ( int i=0 ; i<=4 ; ++i ) if ( ( ++ buc[ card[ i ] ] )== 4 ) return true ; return false ;}bool head ( int s ) { for ( int i=0 ; i<=4 ; ++i ) for ( int j=i+1 ; j<=4 ; ++j ) if ( ( s - v[ i ] - v[ j ] ) % 10 == 0 ) return true ; return false ; }int calc ( ) { int s = 0 ; for ( int i=0 ; i<=4 ; ++i ) s += v[ i ] ; if ( wxn( s ) ) return 60 ; if ( whn( ) ) return 50 ; if ( boom ( ) ) return 40 ; if ( head( s ) ) { if ( s % 10 <= 6 && s % 10 != 0 ) return s % 10 ; else if ( s % 10 != 0 ) return ( s % 10 ) * 2 ; else return 30 ; } else return 0 ;}void init ( ) { for ( int a=1 ; a<=13 ; ++a ) for ( int b=1 ; b<=13 ; ++b ) for ( int c=1 ; c<=13 ; ++c ) for ( int d=1 ; d<=13 ; ++d ) { card[ 0 ] = a ; card[ 1 ] = b ; card[ 2 ] = c ;card[ 3 ] = d ; for ( int i=0 ; i<4 ; ++i ) v[ i ] = min ( card[ i ] , 10 ) ; for ( int i=1 ; i<=13 ; ++i ) { card[ 4 ] = i ; v[ 4 ] = min ( card[ 4 ] , 10 ) ; ans[ a ][ b ][ c ][ d ] += calc ( ) ; } }}int main ( ) { init ( ) ; for ( int T = IN ( ) ; T ; --T ) printf ( "%.0lf\n" , ( double ) ans[ IN( ) ][IN( ) ][IN( ) ][IN( ) ] / 13 ) ; return 0 ; }
14
//#include#include int INPUT ( ) { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}int main ( ) { int N = INPUT ( ) ; int cnt = 1 , tmp = -1 ; for ( int i=1 ; i<=N ; ++i ) { int aa = INPUT ( ) ; if ( aa == tmp ) ++cnt ; else --cnt ; if ( !cnt ) { cnt = 1 ; tmp = aa ; } } printf ( "%d\n" , tmp ) ; return 0 ;}
25
#include#include #include using namespace std ; typedef double db ; const double eps = 1e-10 ; const int maxN = 10010 ;int n , k ; db L[ maxN ] ; bool judge ( db mid , int k ) { int nn = 0 ; for ( int i=1 ; i<=n ; ++i ) nn += L[ i ] / mid ; return nn < k ; }int main ( ) { scanf ( "%d%d" , &n , &k ) ; for ( int i=1 ; i<=n ; ++i ) scanf ("%lf" , &L[ i ] ) ; db l = 0.000000, r = 100001.00 , mid ; while ( r - l > eps ) { mid = ( l + r ) / 2 ; if ( judge( mid , k ) ) r = mid ; else l = mid ; } printf ( "%.2lf\n" , floor ( r * 100 ) / 100 ) ; return 0 ; }
29
#includeusing namespace std ;const int maxN = 60010; const int inf = 2147483647 ;struct Tree { int l , r , mx , sum ;};struct Edge { int to , next ; };Tree tr[ maxN << 2 ] ;Edge e[ maxN << 1 ] ; int head[ maxN ], start[ maxN ] , DFN[ maxN ] , pre[ maxN ] , dep[ maxN ] , size[ maxN ] , val[ maxN ] , Rank[ maxN ]; inline int INPUT ( ) { int x = 0 , f = 1 ; char ch = getchar ( ) ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar ( ) ; } while ( ch >='0' && ch <='9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ; } return x * f ;}int _cnt , dfs_num ;inline void addEdge ( const int x , const int y ) { e[ ++_cnt ].to = y ; e[ _cnt ].next = head[ x ] ; head[ x ] = _cnt ;}void initDfs ( const int x ) { size[ x ] = 1 ; for ( int i=head[ x ] ; i ; i = e[ i ].next ) { if ( e[ i ].to != pre[ x ] ) { dep[ e[ i ].to ] = dep[ x ] + 1 ; pre[ e[ i ].to ] = x ; initDfs ( e[ i ].to ) ; size[ x ] += size[ e[ i ].to ] ; } }}void Dfs ( const int x , const int chainStart ) { DFN[ x ] = ++dfs_num ; Rank[ dfs_num ] = x ; start[ x ] = chainStart ; int heavy = 0 ; for ( int i=head[ x ] ; i ; i=e[ i ].next ) { if ( e[ i ].to != pre[ x ] && size[ e[ i ].to ] > size[ heavy ] ) { heavy = e[ i ].to ; } } if ( heavy ) Dfs ( heavy , chainStart ) ; for ( int i=head[ x ] ; i ; i=e[ i ].next ) { if ( e[ i ].to != heavy && e[ i ].to != pre[ x ] ) Dfs ( e[ i ].to , e[ i ].to ) ; }}void buildTree ( int ll ,int rr ,int i ){ tr[ i ].l = ll; tr[ i ].r = rr; if ( ll == rr ) { tr[ i ].sum = val[ Rank[ ll ] ] ; tr[ i ].mx = val[ Rank[ ll ] ] ; } else { int mid = ( ll + rr ) >> 1 ; buildTree ( ll , mid , i << 1 ) ; buildTree ( mid + 1 , rr , i << 1 | 1 ) ; tr[ i ].mx = max ( tr[ i << 1 ].mx , tr[ i << 1 | 1 ].mx ) ; tr[ i ].sum = tr[ i << 1 ].sum + tr[ i << 1 | 1 ].sum ; }}void updateTree ( int target , int val_ , int i ) { if ( tr[ i ].l == tr[ i ].r ) { tr[ i ].mx = val_ ; tr[ i ].sum = val_ ; }else { int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ; if ( target <= mid ) updateTree ( target , val_ , i << 1 ) ; else updateTree ( target , val_, i << 1 | 1 ) ; tr[ i ].mx = max ( tr[ i << 1 ].mx , tr[ i << 1 | 1 ].mx ) ; tr[ i ].sum = tr[ i << 1 ].sum + tr[ i << 1 | 1 ].sum ; }}int querySum ( const int q , const int w , const int i ) { if ( q <= tr[i].l && w >= tr[i].r ) return tr[i].sum; else { int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ; if ( q > mid ) return querySum ( q , w , i << 1 | 1) ; else if ( w <= mid ) return querySum ( q , w , i << 1 ) ; else return querySum ( q , w , i << 1 | 1 ) + querySum ( q , w , i << 1 ) ; }}int queryMax ( const int q , const int w , const int i ) { if ( q <= tr[i].l && w >= tr[i].r ) return tr[i].mx; else { int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ; if ( q > mid ) return queryMax ( q , w , i << 1 | 1) ; else if ( w <= mid ) return queryMax ( q , w , i << 1 ) ; else return max ( queryMax ( q , w , i << 1 | 1 ) , queryMax ( q , w , i << 1 ) ) ; }}int solveSum ( int x , int y ) { int ret = 0 ; while ( start[ x ] != start[ y ] ) { if ( dep[ start[ x ] ] < dep[ start[ y ]] ) swap( x , y ) ; ret += querySum ( DFN[ start[ x ]] , DFN[ x ] , 1 ) ; x = pre[ start[ x ] ] ; } if ( DFN[ x ] > DFN[ y ]) swap( x, y ) ; ret += querySum ( DFN[ x ] , DFN[ y ] , 1 ) ; return ret ;}int solveMax ( int x , int y ) { int ret = -inf ; while ( start[ x ] != start[ y ] ) { if ( dep[ start[ x ] ] < dep[ start[ y ] ] ) swap ( x , y ) ; ret = max ( ret ,queryMax ( DFN[ start[ x ] ] , DFN[ x ] , 1 ) ) ; x = pre[ start[ x ] ] ; } if ( DFN[ x ] > DFN[ y ] ) swap ( x , y ) ; ret = max ( ret , queryMax ( DFN[ x ] , DFN[ y ] , 1 ) ) ; return ret ;}int main ( ) { int N = INPUT ( ) ; for ( int i=1 ; i
31
#includeusing namespace std ; const int maxN = 100010 ; const int maxM = 1000010 ; const int inf = 2147483647 ; struct Edge { int to , next , val ; };Edge e[ maxM << 1 ] ; int head[ maxN ] , dis[ maxN ] ; bool inQ[ maxN ] ; int _cnt ; void addEdge ( const int x , const int y , const int val_ ) { e[ ++_cnt ].to = y ; e[ _cnt ].val = val_ ; e[ _cnt ].next = head[ x ] ; head[ x ] = _cnt ; }inline int INPUT ( ) { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(x=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}void Spfa ( const int S ) { memset ( dis , 0x3f3f3f , sizeof ( dis ) ) ; memset ( inQ , false , sizeof ( inQ ) ); queue Q ; Q.push( S ) ; inQ[ S ] = true ; dis[ S ] = 1 ; int p ; while ( !Q.empty ( ) ) { p = Q.front ( ) ; inQ[ p ] = false ; Q.pop ( ) ; for ( int i = head[ p ] ; i ; i = e[ i ].next ) { int to_ = e[ i ].to ; if ( dis[ to_ ] > dis[ p ] + e[ i ].val ) { dis[ to_ ] = dis[ p ] + e[ i ].val ; if ( !inQ[ to_ ] ) { Q.push ( to_ ) ; inQ[ to_ ] = true ; } } } }}void Debug ( int n ) { for ( int i=1 ; i<=n ; ++i ) { cout << dis[ i ] << ' ' ; } cout << endl ; }int main ( ) { int N = INPUT ( ) , M = INPUT ( ) , S = INPUT ( ) , m = INPUT ( ) ; for ( int i=1 ; i<=M ; ++i ) { int x = INPUT ( ) , y = INPUT ( ) ; addEdge( x , y , 1 ) ; addEdge( y , x , 1 ) ; } Spfa ( S ) ; //Debug ( N ) ; int ans = -inf ; for ( int i=1 ; i<=N ; ++i ) { ans = max ( ans , dis[ i ] ) ; } printf ( "%d\n" , ans + m ) ; return 0; }
34
#includeusing namespace std ; const int maxN = 1000010 ; struct Edge { int to , next ; };Edge e[ maxN << 1 ] ; int head[ maxN ] , size[ maxN ] , hv[ maxN ] ; int INPUT ( ) { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}int _cnt ; void addEdge ( int x , int y ) { e[ ++_cnt ].to = y ; e[ _cnt ].next = head[ x ] ; head[ x ] = _cnt ; }void Dfs ( const int x , const int fa ) { size[ x ] = 1 ; for ( int i=head[ x ] ; i ; i=e[ i ].next ) { if ( e[ i ].to != fa ) { Dfs ( e[ i ].to , x ) ; size[ x ] += size[ e[ i ].to ] ; } } int heavySon = 0 ; for ( int i=head[ x ] ; i ; i=e[ i ].next ) { if ( e[ i ].to != fa && size[ e[ i ].to ] > size[ heavySon ] ) { heavySon = e[ i ].to ; } } if ( heavySon ) hv[ x ] = heavySon ; }bool judge ( const int x , int n ) { if ( size[ hv[ x ] ] > ( int )( n / 2 ) ) return false ; if ( ( n - size[ x ] ) > ( int )( n / 2 ) ) return false ; return true ; }int main ( ) { int N = INPUT ( ) ; for ( int i=1 ; i
42
#includeusing namespace std ; typedef long long LL ; const int maxN = 5010 ; char op[ maxN ] ; int main ( ) { int t ; while ( scanf ( "%s" , op + 1 ) != EOF ) { int len = strlen ( op + 1 ) ; cin >> t ; LL xx = 0 , yy = 0 ; if ( t > len ) { for ( int i=1 ; i<=len ; ++i ) { switch ( op[ i ] ) { case 'E' : ++xx ; break ; case 'W' : --xx ; break ; case 'S' : --yy ; break ; case 'N' : ++yy ;break ; default :break ; } } if ( ( int ) t / len ) { xx *= ( int ) ( t / len ) ; yy *= ( int ) ( t / len ) ; } for ( int i=1 ; i<= t - ( int )( t / len )*len ; ++i ) { switch ( op[ i ] ) { case 'E' : ++xx ; break ; case 'W' : --xx ; break ; case 'S' : --yy ; break ; case 'N' : ++yy ;break ; default :break ; } } } else { for ( int i=1 ; i<=t ; ++i ) { switch ( op[ i ] ) { case 'E' : ++xx ; break ; case 'W' : --xx ; break ; case 'S' : --yy ; break ; case 'N' : ++yy ;break ; default :break ; } } } printf ( "%lld %lld\n" , xx , yy ) ; } return 0 ; }
50
#include "bits/stdc++.h" using namespace std ;typedef long long QAQ ;const int maxN = 1001000 ;struct SegTree { int l , r ; QAQ sum , mul , add ; } tr[ maxN ] ;QAQ MOD , val ; QAQ arr[ maxN ] ; void Push_up ( const int i ) { tr[ i ].sum = ( tr[ i << 1 | 1 ].sum + tr[ i << 1 ].sum ) % MOD ;} void Push_down ( int i , int m ) { tr[ i << 1 ].add = ( tr[ i << 1 ].add * tr[ i ].mul + tr[ i ].add ) % MOD ; tr[ i << 1 | 1 ].add = ( tr[ i << 1 | 1 ].add * tr[ i ].mul + tr[ i ].add ) % MOD ; tr[ i << 1 ].mul = tr[ i << 1 ].mul * tr[ i ].mul % MOD ; tr[ i << 1 | 1 ].mul = tr[ i << 1 | 1 ].mul * tr[ i ].mul % MOD ; tr[ i << 1 ].sum = ( tr[ i << 1].sum * tr[ i ].mul + tr[ i ].add * ( m - ( m >> 1 ) ) ) % MOD ; tr[ i << 1 | 1 ].sum = ( tr[ i << 1 | 1 ].sum * tr[ i ].mul + tr[ i ].add * ( m >> 1 ) ) % MOD ; tr[ i ].add = 0 ; tr[ i ].mul = 1 ;} void Build_Tree ( const int x , const int y , const int i ) { tr[ i ].l = x ; tr[ i ].r = y ; tr[ i ].mul = 1 ; if ( x == y ) { tr[ i ].sum = arr[ x ] ; return ; } else { int mid = ( x + y ) >> 1 ; Build_Tree ( x , mid , i << 1 ) ; Build_Tree ( mid + 1 , y , i << 1 | 1 ) ; Push_up ( i ) ; }} QAQ Query_Tree ( const int q , const int w , const int i ) { if ( q <= tr[ i ].l && tr[ i ].r <= w ) { return tr[ i ].sum % MOD ; } else { Push_down ( i , tr[ i ].r - tr[ i ].l + 1 ) ; int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ; if ( q > mid ) return Query_Tree ( q , w , i << 1 | 1 ) % MOD; else if ( w <= mid ) return Query_Tree ( q , w , i << 1 ) % MOD ; else return ( Query_Tree ( q , w , i << 1 | 1 ) + Query_Tree ( q , w , i << 1 ) ) % MOD ; Push_up ( i ) ; }} void Update_Tree ( int i , int q , int w , int _ ) { if ( q <= tr[ i ].l && tr[ i ].r <= w ) { if ( _ == 1 ) { tr[ i ].add = tr[ i ].add * val % MOD ; tr[ i ].mul = tr[ i ].mul * val % MOD ; tr[ i ].sum = tr[ i ].sum * val % MOD ; } else if ( _ == 2 ) { tr[ i ].add = ( tr[ i ].add + val ) % MOD ; tr[ i ].sum = ( tr[ i ].sum + ( QAQ ) val * ( tr[ i ].r - tr[ i ].l + 1 ) ) % MOD ; } } else { Push_down ( i , tr[ i ].r - tr[ i ].l + 1 ) ; int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ; if ( q > mid ) Update_Tree ( i << 1 | 1 , q , w , _ ) ; else if ( w <= mid ) Update_Tree ( i << 1 , q , w , _ ) ; else { Update_Tree ( i << 1 | 1 , q , w , _ ) ; Update_Tree ( i << 1 , q , w , _ ) ; } Push_up ( i ) ; }} void DEBUG_( int n ) { for ( int i=1 ; i<=n ; ++i ) { printf ( "\n%d:\nsum:%d\nadd:%d\nmul:%d\n" , i , tr[ i ].sum , tr[ i ].add , tr[ i ].mul ) ; }}int main ( ) { QAQ N , Q ; //freopen ( "sbsbs.out" , "w" , stdout ) ; scanf ( "%lld %lld" , &N , &MOD ) ; for ( int i=1 ; i<=N ; ++i ) scanf ( "%lld" , arr + i ) ; Build_Tree( 1 , N , 1 ) ; scanf ( "%lld" , &Q ) ; for ( int i=1 ; i<=Q ; ++i ){ QAQ op , l , r ; scanf ( "%lld" , &op ) ; //DEBUG_( 13 ) ; if ( op == 3 ) { scanf ( "%lld %lld" , &l , &r ) ; printf ( "%lld\n" , Query_Tree ( l , r , 1 ) ) ; } else { scanf ( "%lld %lld %lld" , &l , &r , &val ) ; Update_Tree ( 1 , l , r , op ) ; } } return 0 ;}