摘要：
P1226 【模板】快速幂||取余运算=0）｛16printf；19｝else｛20dfs；21｝22｝23｝24｝25｝26intmain（）27｛28intn；29scanf；30dfs；31put（“”）；32return0；33｝ViewCodeP1908反向对使用两种方法来尝试。第一个是树数组，这一点不用说。基本的例行操作是在离散化后保持前一位置的桶数，并使用与前一个桶相对应的当前下标来计算位置中的反向数，其余相同。使用合并和排序更合适。在治理方面，对于两个排序的数组，两个头部指针指向的位置设置为p1和p2。p1˃p2：此时，需要计算上一个数组中剩余的数组数。
快速幂板子题：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ll; 4 ll Mul ( ll a ,ll b , ll p ){ 5 a %= p; 6 b %= p; 7 ll c = (long double ) a*b / p; 8 ll ans = a*b - c*p; 9 if( ans < 0 ) ans += p ; 10 else if( ans >= p ) ans -= p ; 11 return ans ; 12 } 13 ll qmul( ll a , ll b , ll p ){ 14 ll ans = 0; 15 a %= p ; 16 while ( b ){ 17 if( b & 1 ){ 18 ans = (ans + a)%p; 19 } 20 a =( a + a )%p; 21 b>>=1; 22 } 23 return ans ; 24 } 25 ll qpow ( ll a , ll b , ll mod ){ 26 a %= mod ; 27 ll ans = 1 ; 28 while ( b ){ 29 if( b & 1 ){ 30 ans = qmul( ans , a , mod ); 31 } 32 a = qmul(a,a,mod); 33 b >>= 1 ; 34 } 35 return ans % mod ; 36 } 37 int main() 38 { 39 ll a,b,p,ans; 40 cin >> a >> b >> p ; 41 ans = qpow(a,b,p); 42 cout<<a<<"^"<<b<<" mod "<<p<<"="<<ans<<endl; 43 return 0 ; 44 }
P1010 幂次方
【题解】
用到的就是基础的dfs来做法来做，除非是 当前位置数位上的数是 1 或者 2 ，否则直接下一层，下一层进入之前应该外面套一个 “2 (” , 出来的时候，套回去 " ) "。
1 #include<bits/stdc++.h> 2 using namespace std; 3 void dfs( int x ){ 4 if( x == 0 ){ 5 printf("2(0)"); 6 }else if( x == 1 ){ 7 printf("2"); 8 }else{ 9 bool f = false ; 10 for( int i=14 ; i>=0 ; i-- ){ 11 if( ( x & (1 << i) ) == (1 << i) ){ 12 if( f ) printf("+"); 13 else f = true; 14 15 if( i != 1 && i != 0 ){ 16 printf("2("); 17 dfs( i ) ; 18 printf(")"); 19 }else{ 20 dfs(i); 21 } 22 } 23 } 24 } 25 } 26 int main() 27 { 28 int n; 29 scanf("%d",&n); 30 dfs(n); 31 puts(""); 32 return 0; 33 }
P1908 逆序对
【题解】
【树状数组】
用了两种方法来尝试，第一种就是树状数组，这个就不多说了，基本套路操作，就是离散化之后，维护每一个位置 上前一个有多少个桶，用目前现在的下标 - 对应前面的多少个桶的形式来计算该位置上的逆序数，其余也是这样。
【归并排序】
利用归并排序来做，这个题目显得更加恰当。
先分后治。
主要在治的方面，两个已排序的数组，两个头指针指着的位置 设为 p1 , p2 。
p1 < p2 ：直接放即可
p1 > p2 : 这时候就需要统计前面数组中，前一个数组剩余个数。
树状数组做法：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 5e5+100; 5 6 ll c[N]; 7 8 typedef struct Node { 9 int id , val ; 10 }Node ; 11 12 bool cmp1 ( Node u , Node v ){ 13 if( u.val == v.val ) return u.id < v.id ; 14 return u.val < v.val ; 15 } 16 bool cmp2 ( Node u , Node v ){ 17 return u.id < v.id ; 18 } 19 20 int lowbit( int x ){ 21 return x & -x ; 22 } 23 24 void update( int No , int val ){ 25 while( No < N ){ 26 c[No] += val ; 27 No += lowbit(No); 28 } 29 } 30 31 ll getsum( int No ){ 32 ll res = 0; 33 while( No > 0 ){ 34 res += c[No]; 35 No -= lowbit(No); 36 } 37 return res ; 38 } 39 Node a[N]; 40 int main() 41 { 42 int n; 43 scanf("%d",&n); 44 for( int i = 1 ; i <= n; i++){ 45 scanf("%d",&a[i].val); 46 a[i].id = i ; 47 } 48 sort( a+1 , a+1+n , cmp1 ); 49 for( int i=1;i<=n;i++){ 50 a[i].val = i ; 51 } 52 sort( a+1 , a+1+n , cmp2 ); 53 ll ans = 0 ; 54 for( int i=1 ; i <= n ;i++ ){ 55 ans += i - getsum(a[i].val)-1 ; 56 update( a[i].val , 1 ); 57 } 58 printf("%lld ",ans); 59 return 0 ; 60 }
归并排序做法：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 5e5+100; 5 ll a[N],b[N]; 6 ll ans = 0 ; 7 void Merge_sort( int L , int R ){ 8 if( L == R ) return ; 9 int Mid = L + R >> 1 ; 10 11 Merge_sort( L , Mid ) ; 12 Merge_sort( Mid+1 , R ); 13 14 int i = L , j = Mid + 1 , k = L ; 15 while( i <= Mid && j <= R ){ 16 if( a[i] <= a[j] ){ 17 b[k++] = a[i++]; 18 }else{ 19 b[k++] = a[j++]; 20 ans += Mid - i + 1 ; 21 } 22 } 23 while( i <= Mid ) b[k++] = a[i++]; 24 while( j <= R ) b[k++] = a[j++]; 25 for( int i = L ; i <= R ; i++ ){ 26 a[i] = b[i] ; 27 } 28 } 29 int main() 30 { 31 int n; 32 scanf("%d",&n); 33 for( int i=1 ;i<=n;i++){ 34 scanf("%lld",&a[i]); 35 } 36 Merge_sort( 1 , n ); 37 printf("%lld ",ans); 38 return 0; 39 }
P1498 南蛮图腾
【题解】
当你找到规律，这个题目就是迎刃而解
首先是创造出第一个处理，然后向右平移 ， 向右下平移，然后就完成了。主要要倒着来。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 2e3+500; 5 int a[N>>1][N]; 6 int main() 7 { 8 int n; 9 scanf("%d",&n); 10 11 for( int i = 0 ; i < N>>1 ; i++ ){ 12 for( int j = 0 ; j < N ; j++ ){ 13 a[i][j] = ' '; 14 } 15 } 16 17 int len = 4 ; 18 a[0][0] = a[1][1] = '/'; 19 a[0][1] = a[0][2] = '_'; 20 a[0][3] = a[1][2] = '\'; 21 22 while( --n ){ 23 for( int i = len/2 ; ~i ; i-- ){ 24 for( int j = 0 ; j < len ; j ++ ){ 25 a[i][j+len] = a[i+len/2][j+len/2] = a[i][j]; 26 } 27 } 28 len <<= 1 ; 29 } 30 31 for( int i = len/2 -1 ; ~i ; i-- ){ 32 for( int j = 0 ; j < len + (len-i) ; j ++ ){ 33 printf("%c",a[i][j]); 34 } 35 puts(""); 36 } 37 return 0 ; 38 }