#include<iostream>
using namespace std ;
int n , q[1000010] , k ;
void quick( int q[] , int l , int r )
{
if( l >= r ) return ;
int x = q[ ( l + r ) / 2] , i = l - 1 , j = r + 1 ;
while( i < j )
{
do i ++ ; while( q[i] < x ) ;
do j -- ; while( q[j] > x ) ;
if( i < j ) swap(q[i] , q[j]) ;
}
quick(q , l, j) ;
quick(q , j + 1 , r) ;
return ;
}
int main()
{
cin >> n >> k ;
for( int i = 0 ; i < n ; i ++ ) cin >> q[i] ;
quick( q , 0 , n - 1 ) ;
cout << q[ k - 1 ] ;
return 0 ;
}
}
活动打卡代码
AcWing 786. 第k个数
活动打卡代码
AcWing 785. 快速排序
#include<iostream>
using namespace std ;
int q[100010] , n ;
void quick( int q[] , int l , int r )
{
if( l >= r) return ;
int x = q[(l+r) / 2] , i = l - 1 , j = r + 1 ;
while( i < j )
{
do i ++ ; while( q[i] < x ) ;
do j -- ; while( q[j] > x ) ;
if( i < j ) swap( q[i] , q[j]) ;
}
quick( q , l , j ) ;
quick( q , j + 1 , r) ;
return ;
}
int main()
{
cin >> n ;
for( int i = 0 ; i < n ; i ++ ) cin >> q[i] ;
quick(q,0,n-1) ;
for( int i = 0 ; i < n ; i ++ ) cout << q[i] << " " ;
return 0 ;
}
#include<iostream>
using namespace std ;
int main()
{
char a[20][20] , c , f ;
int x1 , y1 , x2 , y2 , ans = 0 , dx[4] = { -1 , 0 , 1 , 0 } , dy[4] = { 0 , 1 , 0 , -1 };
for( int i = 0 ; i < 10 ; i ++ )
for( int j = 0 ; j < 10 ; j ++ )
{
cin >> a[i][j] ;
if( a[i][j] == 'C')
{
x1 = i ;
y1 = j ;
}
else if( a[i][j] == 'F' )
{
x2 = i ;
y2 = j ;
}
}
for( int dc = 0 ,df = 0 ; ans < 160000 ; )
{
if(a[x1+dx[dc]][y1+dy[dc]]=='*'||x1+dx[dc]<0||x1+dx[dc]>9||y1+dy[dc]<0||y1+dy[dc]>9)
dc = ( dc + 1 ) % 4 ;
else
{
x1 = x1 + dx[dc] ;
y1 = y1 + dy[dc] ;
}
if(a[x2+dx[df]][y2+dy[df]]=='*'||x2+dx[df]<0||x2+dx[df]>9||y2+dy[df]< 0||y2+dy[df]>9)
df = ( df + 1 ) % 4 ;
else
{
x2 = x2 + dx[df] ;
y2 = y2 + dy[df] ;
}
if( x1 == x2 && y1 == y2)
{
cout << ++ans ;
return 0 ;
}
else ans ++ ;
}
cout << 0 ;
return 0 ;
}
折磨至极
#include<iostream>
using namespace std ;
int main()
{
int p1 , p2 , p3 ;
cin >> p1 >> p2 >> p3 ;
string a ;
cin >> a ;
for( int i = 0 ; a[i] != '\0' ; i ++ )
{
if( a[i] != '-' ) cout << a[i] ;
else
{
if( a[ i - 1 ] == a[ i + 1 ] )
{
cout << '-' ;
}
else if( a[ i - 1 ] >= 97 && a[ i - 1 ] <= 122 && a[ i + 1 ] >= 97 && a[ i + 1 ] <= 122 && a[ i - 1 ] < a[ i + 1 ] )
{
if( p1 == 1 && p3 == 1 )
for( int t = a[ i - 1 ] + 1 ; t < a[ i + 1 ] ; t ++ )
for( int j = 1 ; j <= p2 ; j ++)
cout <<(char) t ;
else if( p1 == 2 && p3 == 1)
{
for( int t = a[ i - 1 ] + 1 ; t < a[ i + 1 ] ; t ++ )
for( int j = 1 ; j <= p2 ; j ++)
printf("%c" , t - 32) ;
}
else if( p1 == 2 && p3 == 2 )
{
for( int t = a[ i + 1 ] - 1 ; t > a[ i - 1 ] ; t -- )
for( int j = 1 ; j <= p2 ; j ++)
printf("%c" , t - 32) ;
}
else if( p1 == 3 )
{
for( int t = a[ i + 1 ] - 1 ; t > a[ i - 1 ] ; t -- )
for( int j = 1 ; j <= p2 ; j ++)
cout << '*' ;
}
}
else if( a[ i - 1 ] >= 48 && a[ i - 1 ] <= 57 && a[ i + 1 ] >= 48 && a[ i + 1 ] <= 57 && a[ i - 1 ] < a[ i + 1 ])
{
if( ( p1 == 1 || p1 == 2) && p3 == 1 )
for( int t = a[ i - 1 ] + 1 ; t < a[ i + 1 ] ; t ++ )
for( int j = 1 ; j <= p2 ; j ++)
cout <<(char) t ;
else if( ( p1 == 1 || p1 == 2 ) && p3 == 2 )
{
for( int t = a[ i + 1 ] - 1 ; t > a[ i - 1 ] ; t -- )
for( int j = 1 ; j <= p2 ; j ++)
cout <<(char) t ;
}
else if( p1 == 3 )
{
for( int t = a[ i - 1 ] + 1 ; t < a[ i + 1 ] ; t ++ )
for( int j = 1 ; j <= p2 ; j ++)
cout << '*' ;
}
}
else cout << '-' ;
}
}
return 0 ;
}
活动打卡代码
AcWing 793. 高精度乘法
高位A * 低位b
#include<iostream>
#include<vector>
using namespace std ;
vector<int> mul(vector<int> &A , int b )
{
vector<int> c ;
int t = 0 ;
for( int i = 0 ; i < A.size() || t ; i ++ )
{ //检查for循环括号
if( i < A.size() )
{
t += A[i] * b ;
}
c.push_back( t % 10 ) ;
t = t / 10 ;
}//检查for循环括号
while( c.size() > 1 && c.back() == 0 )
c.pop_back() ;
return c ;
}
int main()
{
string a ;
int b ;
cin >> a >> b ;
vector<int> A ;
for( int i = a.size() - 1 ; i >= 0 ; i -- )
{
A.push_back( a[i] - '0' ) ;
}
vector<int> c = mul( A , b ) ;
for( int i = c.size() - 1 ; i >= 0 ; i -- )
{
cout << c[i] ;
}
return 0 ;
}
高位A * 高位B
#include<iostream>
#include<vector>
using namespace std ;
vector<int> mul( vector<int> &A , vector<int> &B )
{
vector<int> c ( A.size() + B.size() + 10 , 0 ) ;
int t = 0 ;
for( int i = 0 ; i < A.size() ; i ++ )
for( int j = 0 ; j < B.size() ; j ++ )
c[ i + j ] += A[i] * B[j] ;//检查A[i] * B[j]
for( int i = 0 ; i < c.size() ; i ++ )
{
t += c[i] ;
c[i] = t % 10 ;
t = t / 10 ;
}
while( c.size() > 1 && c.back() == 0 )
c.pop_back() ;
return c ;
}
int main()
{
string a , b ;
cin >> a >> b ;
vector<int> A , B ;
for( int i = a.size() - 1 ; i >= 0 ; i -- )
A.push_back( a[i] - '0' ) ;
for( int i = b.size() - 1 ; i >= 0 ; i -- )
B.push_back( b[i] - '0' ) ;
vector<int> c = mul( A , B ) ;
for( int i = c.size() - 1 ; i >= 0 ; i -- )
cout << c[i] ;
return 0 ;
}
高精度求阶乘和
#include<iostream>
#include<string.h>
using namespace std ;
int xc[100] , xj[100] ;
void jiecheng( int x )
{
int sum = 0 ;
for( int i = 100 ; i >= 0 ; i -- )
{
xc[i] = xc[i] * x + sum ;
sum = xc[i] / 10 ;
xc[i] = xc[i] % 10 ;
}
return;
}
void ac()
{
int sum = 0 ;
for( int i = 100 ; i >= 0 ; i -- )
{
xj[i] = xj[i] + xc[i] + sum ;
sum = xj[i] / 10 ;
xj[i] = xj[i] % 10 ;
}
return;
}
int main()
{
int n ;
cin >> n ;
xc[100] = 1 ;
for( int i = 1 ; i <= n ; i ++ )
{
jiecheng( i ) ;
ac() ;
}
int i = 0 ;
for( ; i <= 100 ; i ++ )
if( xj[i] != 0)
break ;
for( ; i <= 100 ; i ++ )
cout << xj[i] ;
}
活动打卡代码
AcWing 791. 高精度加法
#include<iostream>
#include<vector>
using namespace std ;
vector<int> add( vector<int> A , vector<int> B )
{
int t = 0 ;
vector<int> c ;
for( int i = 0 ; i < A.size() || i < B.size() ; i ++ )
{
if( i < A.size() )
{
t += A[i] ;
}
if( i < B.size() )
{
t += B[i] ;
}
c.push_back( t % 10);
t = t / 10 ;
}
if(t)
{
c.push_back(1) ;
}
return c ;
}
int main()
{
string a , b ;
cin >> a >> b ;
vector<int> A , B ;
for( int i = a.size() - 1 ; i >= 0 ; i -- )
{
A.push_back( a[i] - '0' );
}
for( int i = b.size() - 1 ; i >= 0 ; i -- )
{
B.push_back( b[i] - '0' ) ;
}
vector<int> c = add( A , B ) ;
for( int i = c.size() - 1 ; i >= 0 ; i -- )
{
cout << c[i] ;
}
return 0 ;
}
