1
#include <bits/stdc++.h>
using namespace std ;
struct bigInt {
int num[ ] ;
int size ;
static const int maxN = ;
private :
void Init ( ) {
size = ;
for ( int i= ; i<=maxN ; ++i )
num[ i ] = ;
}
public :
void toInt ( char *ch ) {
Init ( ) ;
size = strlen ( ch ) ;
for ( int i= ; i<size ; ++i ) {
num[ i ] = ch[ size - i - ] - '' ;
}
}
public :
void Plus ( bigInt o ) {
bool up = false ;
size = max ( size , o.size ) ;
for ( int i= ; i<size ; ++i ) {
num[ i ] += o.num[ i ] + up ;
up = false ;
if ( num[ i ] >= ) {
num[ i ] -= ;
up = true ;
}
}
if ( up ) num[ size++ ] = ;
}
public :
void print ( ) {
for ( int i=size- ; i>= ; --i ) {
printf ( "%d" , num[ i ] ) ;
}
putchar ( '\n' ) ;
}
} A , B;
char str1[ ] , str2[ ] ;
int main ( ) {
while ( scanf ( "%s%s" , str1 , str2 ) != EOF ) {
A.toInt (str1) ;
B.toInt (str2) ;
A.Plus ( B ) ;
A.print ( ) ;
}
return ;
}
3
#include <bits/stdc++.h> using namespace std ;
const int maxN = ;
const int maxM = ; 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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} void Init ( const int N , const int M ) {
for ( int i= ; i<=N ; ++i ) {
father[ i ] = i ;
}
sort( e + , e + M + , cmp ) ;
} void Debug ( int n ) {
for ( int i= ; i<=n ; ++i ) {
cout << e[ i ].date << endl ;
}
}
int main ( ) {
int N = INPUT ( ) , M = INPUT ( ) ;
memset ( crash , false , sizeof ( crash ) ) ;
for ( int i= ; i<=M ; ++i ) {
e[ i ].to = INPUT ( ) ;
e[ i ].from = INPUT ( ) ;
e[ i ].date = INPUT ( ) ;
}
Init ( N , M ) ;
//Debug(M); for ( int i= ; 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 = ;
for ( int i= ; i<=maxM ; i++ ) {
if ( crash[ i ] ) _cnt++ ;
}
printf ( "%d\n" , _cnt ) ;
return ;
}
4
#include <bits/stdc++.h> using namespace std ;
typedef long long ll ;
ll k ;
ll QP ( ll a , ll b ) {
ll ret = , base = a ;
while( b ) {
if ( b & ) ret = ret * base % k ;
base = base * base % k ;
b >>= ;
}
return ret ;
} int main ( ) {
ll b , n ;
cin >> b >> n >> k ;
cout << QP ( b , n ) % k << endl ;
return ;
}
6
#include <bits/stdc++.h> using namespace std;
int ans[ ][ ][ ][ ] ;
int card[ ] , v[ ] , buc[ ] ; int IN ( ) {
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} int tot; bool wxn ( int s ) {
for ( int i= ; i<= ; ++i )
if ( card[ i ] >= ) return false ;
if ( s > ) return false ;
return true ;
} bool whn ( ) {
for ( int i= ; i<= ; ++i )
if ( card[ i ] <= ) return false ;
return true ;
} bool boom ( ) {
memset ( buc , , sizeof( buc ) ) ;
for ( int i= ; i<= ; ++i )
if ( ( ++ buc[ card[ i ] ] )== ) return true ;
return false ;
} bool head ( int s ) {
for ( int i= ; i<= ; ++i )
for ( int j=i+ ; j<= ; ++j )
if ( ( s - v[ i ] - v[ j ] ) % == ) return true ;
return false ;
}
int calc ( ) {
int s = ;
for ( int i= ; i<= ; ++i ) s += v[ i ] ;
if ( wxn( s ) ) return ;
if ( whn( ) ) return ;
if ( boom ( ) ) return ;
if ( head( s ) ) {
if ( s % <= && s % != ) return s % ;
else if ( s % != ) return ( s % ) * ;
else return ;
}
else return ;
}
void init ( ) {
for ( int a= ; a<= ; ++a )
for ( int b= ; b<= ; ++b )
for ( int c= ; c<= ; ++c )
for ( int d= ; d<= ; ++d ) {
card[ ] = a ; card[ ] = b ; card[ ] = c ;card[ ] = d ;
for ( int i= ; i< ; ++i ) v[ i ] = min ( card[ i ] , ) ;
for ( int i= ; i<= ; ++i ) {
card[ ] = i ;
v[ ] = min ( card[ ] , ) ;
ans[ a ][ b ][ c ][ d ] += calc ( ) ;
}
}
}
int main ( ) {
init ( ) ;
for ( int T = IN ( ) ; T ; --T )
printf ( "%.0lf\n" , ( double ) ans[ IN( ) ][IN( ) ][IN( ) ][IN( ) ] / ) ;
return ;
}
14
//#include <bits/stdc++.h>
#include <cstdio> int INPUT ( ) {
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int main ( ) {
int N = INPUT ( ) ;
int cnt = , tmp = - ;
for ( int i= ; i<=N ; ++i ) {
int aa = INPUT ( ) ;
if ( aa == tmp ) ++cnt ;
else --cnt ;
if ( !cnt ) {
cnt = ;
tmp = aa ;
}
}
printf ( "%d\n" , tmp ) ;
return ;
}
25
#include <cstdio>
#include <cstdlib>
#include <cmath> using namespace std ;
typedef double db ;
const double eps = 1e- ;
const int maxN = ; int n , k ;
db L[ maxN ] ;
bool judge ( db mid , int k ) {
int nn = ;
for ( int i= ; i<=n ; ++i )
nn += L[ i ] / mid ;
return nn < k ;
} int main ( ) {
scanf ( "%d%d" , &n , &k ) ;
for ( int i= ; i<=n ; ++i )
scanf ("%lf" , &L[ i ] ) ;
db l = 0.000000, r = 100001.00 , mid ;
while ( r - l > eps ) {
mid = ( l + r ) / ;
if ( judge( mid , k ) )
r = mid ;
else
l = mid ;
}
printf ( "%.2lf\n" , floor ( r * ) / ) ;
return ;
}
29
#include <bits/stdc++.h> using namespace std ;
const int maxN = ;
const int inf = ; struct Tree {
int l , r , mx , sum ;
};
struct Edge {
int to , next ;
}; Tree tr[ maxN << ] ;
Edge e[ maxN << ] ;
int head[ maxN ], start[ maxN ] , DFN[ maxN ] , pre[ maxN ] , dep[ maxN ] , size[ maxN ] , val[ maxN ] , Rank[ maxN ]; inline int INPUT ( ) {
int x = , f = ; char ch = getchar ( ) ;
while ( ch < '' || ch > '' ) {if ( ch == '-' ) f = - ; ch = getchar ( ) ; }
while ( ch >='' && ch <='' ) { x = ( x << ) + ( x << ) + ch - '' ; 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 ] = ;
for ( int i=head[ x ] ; i ; i = e[ i ].next ) {
if ( e[ i ].to != pre[ x ] ) {
dep[ e[ i ].to ] = dep[ x ] + ;
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 = ;
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 ) >> ;
buildTree ( ll , mid , i << ) ;
buildTree ( mid + , rr , i << | ) ;
tr[ i ].mx = max ( tr[ i << ].mx , tr[ i << | ].mx ) ;
tr[ i ].sum = tr[ i << ].sum + tr[ i << | ].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 ) >> ;
if ( target <= mid )
updateTree ( target , val_ , i << ) ;
else
updateTree ( target , val_, i << | ) ;
tr[ i ].mx = max ( tr[ i << ].mx , tr[ i << | ].mx ) ;
tr[ i ].sum = tr[ i << ].sum + tr[ i << | ].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 ) >> ;
if ( q > mid ) return querySum ( q , w , i << | ) ;
else if ( w <= mid ) return querySum ( q , w , i << ) ;
else return querySum ( q , w , i << | ) + querySum ( q , w , i << ) ;
}
} 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 ) >> ;
if ( q > mid ) return queryMax ( q , w , i << | ) ;
else if ( w <= mid ) return queryMax ( q , w , i << ) ;
else return max ( queryMax ( q , w , i << | ) , queryMax ( q , w , i << ) ) ;
}
}
int solveSum ( int x , int y ) {
int ret = ;
while ( start[ x ] != start[ y ] ) {
if ( dep[ start[ x ] ] < dep[ start[ y ]] ) swap( x , y ) ;
ret += querySum ( DFN[ start[ x ]] , DFN[ x ] , ) ;
x = pre[ start[ x ] ] ;
}
if ( DFN[ x ] > DFN[ y ]) swap( x, y ) ;
ret += querySum ( DFN[ x ] , DFN[ y ] , ) ;
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 ] , ) ) ;
x = pre[ start[ x ] ] ;
}
if ( DFN[ x ] > DFN[ y ] ) swap ( x , y ) ;
ret = max ( ret , queryMax ( DFN[ x ] , DFN[ y ] , ) ) ;
return ret ;
}
int main ( ) {
int N = INPUT ( ) ;
for ( int i= ; i<N ; ++i ) {
int x = INPUT ( ) , y = INPUT ( ) ;
addEdge ( x , y ) ;
addEdge ( y , x ) ;
}
for ( int i= ; i<=N ; ++i ) val[ i ] = INPUT ( ) ;
initDfs ( ) ;
Dfs( , ) ;
buildTree ( , N , ) ;
int Q = INPUT ( ) ;
char op[ ] ;
for ( int i= ; i<=Q ; ++i ) {
scanf ( "%s" , op ) ;
int x = INPUT ( ) , y = INPUT ( ) ;
if ( op[ ] == 'H' ) {
updateTree ( DFN[ x ] , y , ) ;
}else
if ( op[ ] == 'S' ) {
printf ( "%d\n" , solveSum ( x , y ) ) ;
}else {
printf ( "%d\n" , solveMax ( x , y ) ) ;
}
}
return ;
}
31
#include <bits/stdc++.h> using namespace std ;
const int maxN = ;
const int maxM = ;
const int inf = ; struct Edge {
int to , next , val ;
}; Edge e[ maxM << ] ;
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=,f=;char ch=getchar();
while(ch<''||ch>''){if(x=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} void Spfa ( const int S ) {
memset ( dis , 0x3f3f3f , sizeof ( dis ) ) ;
memset ( inQ , false , sizeof ( inQ ) );
queue<int> Q ;
Q.push( S ) ;
inQ[ S ] = true ;
dis[ S ] = ;
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= ; i<=n ; ++i ) {
cout << dis[ i ] << ' ' ;
}
cout << endl ;
}
int main ( ) {
int N = INPUT ( ) , M = INPUT ( ) , S = INPUT ( ) , m = INPUT ( ) ;
for ( int i= ; i<=M ; ++i ) {
int x = INPUT ( ) , y = INPUT ( ) ;
addEdge( x , y , ) ;
addEdge( y , x , ) ;
}
Spfa ( S ) ;
//Debug ( N ) ;
int ans = -inf ;
for ( int i= ; i<=N ; ++i ) {
ans = max ( ans , dis[ i ] ) ;
}
printf ( "%d\n" , ans + m ) ;
return ;
}
34
#include <bits/stdc++.h> using namespace std ;
const int maxN = ; struct Edge {
int to , next ;
};
Edge e[ maxN << ] ;
int head[ maxN ] , size[ maxN ] , hv[ maxN ] ; int INPUT ( ) {
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';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 ] = ;
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 = ;
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 / ) ) return false ;
if ( ( n - size[ x ] ) > ( int )( n / ) ) return false ;
return true ;
} int main ( ) {
int N = INPUT ( ) ;
for ( int i= ; i<N ; ++i ) {
int x = INPUT ( ) , y = INPUT ( ) ;
addEdge ( x , y ) ;
addEdge ( y , x ) ;
}
Dfs ( , ) ;
for ( int i= ; i<=N ; ++i ) {
if ( judge ( i , N ) ) {
printf ( "%d\n" , i ) ;
}
}
return ;
}
42
#include <bits/stdc++.h> using namespace std ;
typedef long long LL ;
const int maxN = ; char op[ maxN ] ; int main ( ) {
int t ;
while ( scanf ( "%s" , op + ) != EOF ) {
int len = strlen ( op + ) ;
cin >> t ;
LL xx = , yy = ;
if ( t > len ) {
for ( int i= ; 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= ; 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= ; 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 ;
}
50
#include "bits/stdc++.h" using namespace std ;
typedef long long QAQ ;
const int maxN = ;
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 << | ].sum + tr[ i << ].sum ) % MOD ;
} void Push_down ( int i , int m ) {
tr[ i << ].add = ( tr[ i << ].add * tr[ i ].mul + tr[ i ].add ) % MOD ;
tr[ i << | ].add = ( tr[ i << | ].add * tr[ i ].mul + tr[ i ].add ) % MOD ;
tr[ i << ].mul = tr[ i << ].mul * tr[ i ].mul % MOD ;
tr[ i << | ].mul = tr[ i << | ].mul * tr[ i ].mul % MOD ;
tr[ i << ].sum = ( tr[ i << ].sum * tr[ i ].mul + tr[ i ].add * ( m - ( m >> ) ) ) % MOD ;
tr[ i << | ].sum = ( tr[ i << | ].sum * tr[ i ].mul + tr[ i ].add * ( m >> ) ) % MOD ;
tr[ i ].add = ;
tr[ i ].mul = ;
} void Build_Tree ( const int x , const int y , const int i ) {
tr[ i ].l = x ; tr[ i ].r = y ;
tr[ i ].mul = ;
if ( x == y ) {
tr[ i ].sum = arr[ x ] ;
return ;
}
else {
int mid = ( x + y ) >> ;
Build_Tree ( x , mid , i << ) ;
Build_Tree ( mid + , y , i << | ) ;
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 + ) ;
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( q > mid ) return Query_Tree ( q , w , i << | ) % MOD;
else if ( w <= mid ) return Query_Tree ( q , w , i << ) % MOD ;
else return ( Query_Tree ( q , w , i << | ) + Query_Tree ( q , w , i << ) ) % MOD ;
Push_up ( i ) ;
}
} void Update_Tree ( int i , int q , int w , int _ ) {
if ( q <= tr[ i ].l && tr[ i ].r <= w ) {
if ( _ == ) {
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 ( _ == ) {
tr[ i ].add = ( tr[ i ].add + val ) % MOD ;
tr[ i ].sum = ( tr[ i ].sum + ( QAQ ) val * ( tr[ i ].r - tr[ i ].l + ) ) % MOD ;
}
}
else {
Push_down ( i , tr[ i ].r - tr[ i ].l + ) ;
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( q > mid ) Update_Tree ( i << | , q , w , _ ) ;
else if ( w <= mid ) Update_Tree ( i << , q , w , _ ) ;
else {
Update_Tree ( i << | , q , w , _ ) ;
Update_Tree ( i << , q , w , _ ) ;
}
Push_up ( i ) ;
}
} void DEBUG_( int n ) {
for ( int i= ; 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= ; i<=N ; ++i ) scanf ( "%lld" , arr + i ) ;
Build_Tree( , N , ) ;
scanf ( "%lld" , &Q ) ;
for ( int i= ; i<=Q ; ++i ){
QAQ op , l , r ;
scanf ( "%lld" , &op ) ;
//DEBUG_( 13 ) ;
if ( op == ) {
scanf ( "%lld %lld" , &l , &r ) ;
printf ( "%lld\n" , Query_Tree ( l , r , ) ) ;
}
else {
scanf ( "%lld %lld %lld" , &l , &r , &val ) ;
Update_Tree ( , l , r , op ) ;
}
}
return ;
}