acwing game 74 of the week

competition link

1. There is nothing to say about the idea of ​​the first question. One thing to note is that we should not forget to compare the difference between the first and the last one when comparing.

AC code

#include <iostream>
using namespace std ;
int main()
{
    int mi = 1010 ;
    int n ;
    int a[1010] ; 
    cin >> n ; 
    for(int i = 0 ; i < n ; i ++ )
    {
        cin >> a[i] ; 
        if(i) mi = min(mi , abs(a[i] - a[i - 1])) ; 
    }
    mi = min(mi , abs(a[0] - a[n - 1])) ; 
    cout << mi << endl ; 
    return 0 ;
}

2. This question is a template question for searching. We can use wide search or deep search. The only difference between this question and template question is that this question is three-dimensional, which is not much different from the two-dimensional template question. Just modify the offset array.
AC code (deep search version)

#include <iostream>
using namespace std ;
const int N = 15 ; 
int n , m , tt ;
char g[N][N][N] ;
int x , y ; 
int dx[6] = {0 , -1 , 0 , 1 , 0 , 0 } , dy[6] = {0,  0 , 1 ,  0 , -1 , 0 } , dz[6] = {1 , 0 , 0 , 0 , 0 , -1 } ; 
int dfs(int k , int x , int y )
{
    g[k][x][y] = '#' ;
    int res = 1 ; 
    for(int i = 0 ; i < 6 ; i ++ ) 
    {
        int k1 = k + dz[i] , b = x + dx[i] , c = y +dy[i] ; 
        if(k1 < 1 || k1 > tt || b < 1 || b > n || c < 1 || c > m || g[k1][b][c] == '#') continue ;
        res += dfs(k1 , b , c ) ; 
    }
    return res ;  
}

int main()
{
    cin >> tt >> n >> m ;
    for(int i = 1;  i <= tt ; i ++ )
    {
        for(int j = 1 ; j <= n ; j ++ )
        {
            for(int t = 1 ; t <= m ; t ++ )
            {
                cin >> g[i][j][t] ; 
            }
        }
    }
    cin >> x >> y ; 
    cout << dfs(1 , x , y ) << endl ;
    return 0 ;
}

Wide search version

#include <iostream>
#define x first 
#define y second 
#include <cstring> 
using namespace std ;
const int N = 20 ; 
typedef pair<int,pair<int,int> > PIP  ; 
int n , m , tt ;
char g[N][N][N] ;  
bool st[N][N][N] ;
PIP qq[ N*N*N ] ;
int hh = 0 , tt1 = -1 ; 
int x , y ;
int cnt ; // cnt is used to store the number of points we can reach,
int dx[6] = {0 , -1 , 0 , 1 , 0 , 0 } ; 
int dy[6] = {0,  0 , 1 ,  0 , -1 , 0 } ;
int dz[6] = {1 , 0 , 0 , 0 , 0 , -1 } ; 
void bfs()
{
    qq[++tt1] = { 1 , {x , y } } ;
    st[1][x][y] = true ; 
    cnt ++ ; 
    while(hh <= tt1 ) 
    {
        auto t = qq[hh++] ;
        for(int i = 0 ; i < 6 ;  i ++ )
        {
            int a = t.x + dz[i], b = t.y.x + dx[i], c = t.y.y + dy[i] ;
            if(a >= 1 && a <= tt && b >= 1 && b <= n && c >= 1 && c <= m &&g[a][b][c] == '.' ) 
            {
                if(st[a][b][c]) continue ; 
                else 
                {
                    cnt ++ ; 
                    st[a][b][c] = true ; 
                }
                qq[++tt1] = {a , {b , c } } ; 
            }
        }
    }
}

int main()
{
    cin >> tt >> n >> m ;
    for(int i = 1;  i <= tt ; i ++ )
    {
        for(int j = 1 ; j <= n ; j ++ )
        {
            for(int t = 1 ; t <= m ; t ++ )
            {
                cin >> g[i][j][t] ; 
            }
        }
    }
    cin >> x >> y ; 
    bfs() ;
    
    cout << cnt << endl ; 
    
    return 0 ;
}

3. Ideas, we use tree array + discretization to do this question;
We enumerate linearly a j a_j aj​ This number, how do we find it in the process of enumeration a [ 1....... j − 1 ] a[1 ....... j - 1] ratio between a[1.......j−1] a [ j ] a[j] What about a[j] big numbers? Also how to find a [ j + 1 , n ] a[j+1, n] a[j+1,n] the ratio in this interval a [ j ] a[j] What about small numbers of a[j]?
Don't be afraid, tree array + discretization can solve these two problems:
Let's first introduce discretization, how do we find a [ j ] a[j] What about the discretized value corresponding to a[j]? For the original array w, we open up another array q, and after assigning the original array to the q array, sort the q group in ascending order, if we traverse the original array to a [ j ] a[j] The number a[j] must be uniquely mapped to a subscript v in the q array. This v is what we call the discretized value. (because any two numbers in the original array are different), so we can find that the ratio of a [ j ] a[j] There are v - 1 numbers where a[j] is small.
Note that this tree-like array maintains the number of current occurrences of each discretized value. That is, when we traverse to a [ j ] a[j] a[j] and the v corresponding to a[j] has not been updated to the tree array, then t r [ v ] tr[v] tr[v] means that a [ 1....... j − 1 ] a[1 ....... j - 1] Among a[1.......j−1], than a [ j ] a[j] a[j] is the number of small numbers (set to tt), but in a [ 1....... j − 1 ] a[1 ....... j - 1] The interval a[1.......j−1] we want is the ratio a [ j ] a[j] a[j] is the number of large numbers, so it is ( j − 1 − t t ) (j - 1 - tt ) (j−1−tt) (the code shows (i - tt) because i starts at 0, but the principle is the same) Good! We have solved the first problem. Similarly, the answer to the second question is: (v - 1 - tt ) because (v - 1 ) represents all the ratios in the original array a [ j ] a[j] a[j] is the number of small numbers, and tt represents the number of a [ 1....... j − 1 ] a[1 ....... j - 1] Among a[1.......j−1], than a [ j ] a[j] a[j] is the number of small numbers, so in a [ j + 1 , n ] a[j + 1 , n] a[j+1,n] where the ratio a [ j ] a[j] The number of small numbers of a[j] is (v - 1 - tt ), according to the multiplication principle to a [ j ] a[j] a[j] is the number of intermediate values
( i − t t ) ∗ ( v − 1 − t t ) (i - tt ) * (v - 1 - tt ) (i−tt)∗(v−1−tt) , now all the problems are solved, go directly to the code:
AC code:

#include <algorithm>
#include <iostream>
using namespace std ;
typedef long long LL ; 
const int N = 1e6 + 10 ;
int tr[N] , w[N] , q[N] ; // tree array, input value, discretized array
int n ; 
int lowbit(int x )
{
    return  x & -x ; 
}

void update(int x , int v ) 
{
    for(int i = x ; i <= n ; i += lowbit(i) ) 
    {
        tr[i] += v ; 
    }
}

int query(int x ) 
{
    int res = 0 ; 
    for(int i = x  ; i >= 1 ; i -= lowbit(i) ) 
    {
        res += tr[i] ; 
    }
    return res ; 
}

int main()
{
    cin >> n ; 
    for(int i = 0 ; i < n ; i ++ ) 
    {
        cin >> w[i] ;
        q[i] = w[i] ; 
    }
    LL res = 0 ; 
    sort(q , q + n ) ; 
    for(int i = 0 ; i < n ; i ++ )
    {
        int v = lower_bound(q , q  + n , w[i] ) - q + 1 ; // Find the discretized coordinate values
        int tt = query(v) ; //  Find the number of preceding numbers less than v.
        res += (LL)(i - tt) * (v - 1 - tt) ; // (i - tt ) is the number of larger numbers.
        update(v , 1) ;
    }
    cout << res << endl ; 
    return 0 ; 
}

Tags: Algorithm Graph Theory dfs

Posted by peytonrm on Sun, 23 Oct 2022 03:43:56 +1030