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 ;
}