Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Resumen de las preguntas de hoy-día010

1. La subcadena palíndromo más larga.

1.1.

1.2.Ideas

Después de leer la pregunta, sabes que en una cadena de longitud n, encuentra la longitud de la subcadena palíndromo más larga. Una subcadena palíndromo puede entenderse como una cadena simétrica. Debido a la simetría, la idea básica es el "método de expansión central", es decir, la cadena se recorre en secuencia y luego se expande a ambos lados del carácter. Si los caracteres en ambos lados son iguales, entonces es. registrado en la variable retlen Después de recorrer, finalmente obtenemos Simplemente devuelve la longitud máxima. Para facilitar la comprensión, haga un dibujo:

Además, al analizar el ejemplo, también se debe prestar atención a la diferencia entre números pares e impares, por lo que el siguiente paso es la implementación del programa.

1.3. Implementación del programa

Primero, de acuerdo con el "método de expansión central" del análisis de ideas, la cadena se atraviesa y se expande desde la estación central en i. El retlen obtenido a su vez se compara y actualiza continuamente con el retlen, porque es necesario distinguir entre impares. números y números pares, respectivamente. Encuentre el valor máximo y finalmente compárelo para obtener el máximo final y devuélvalo.

class Solution
{
public:
    int getLongestPalindrome(string A)
    {
        size_t len = A.size();
        int left = 0;
        int right = 0;
        int retlen = 0;
        //偶数
        for(int i = 0;i < len; i++)
        {
            left = i;
            right = i + 1;
            while(left >= 0 && right < len && A[left] == A[right])
            {
                left--;
                right++;
            }
            retlen = max(retlen ,right - left - 1);
        }
        //奇数
        for(int j = 0;j < len;j++)
        {
            left = j;
            right = j;
            while(left >= 0 && right < len && A[left] == A[right])
            {
                left--;
                right++;
            }
            retlen = max(retlen ,right - left - 1);
        }
        return retlen ;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. El mejor momento para comprar y vender acciones (1)

2.1.

2.2.Ideas

Después de leer la pregunta, sabes que para el mecanismo de compra y venta de un grupo de acciones, solo puedes comprar y vender una vez, encontremos el beneficio máximo obtenido si pierdes dinero sin importar cuándo compres o vendas. Cuanto pierde, es decir, no hay ganancias, entonces genera 0 Eso es todo. Luego, la idea básica es enumerar/método de fuerza bruta, encontrar la diferencia de ganancias de cada grupo y devolver el valor máximo. Después de probarlo, se descubre que las dos capas expirarán y este problema se limita a. 1 ms para resolver. Por lo tanto, es necesario optimizar en función del método de fuerza bruta, por lo que también se escribe el método de fuerza bruta. Luego, en función del método de fuerza bruta, retroceder se ha repetido demasiadas veces, optimización, pensamiento y descubrimiento, si pensamos en ello. a la inversa, primero considere vender. Luego, solo necesita encontrar el valor mínimo antes del punto de venta, y la diferencia obtenida es la diferencia máxima, lo que significa que solo necesita atravesarlo una vez. El siguiente paso es la implementación del programa.

2.3. Implementación del programa

Primero, de acuerdo con el análisis del método de fuerza bruta, todas las situaciones se enumeran para encontrar la diferencia máxima de salida. Esta pregunta caduca. Por eso hay que optimizarlo.

#include <iostream>
using namespace std;

const int N = 1e5 +10;

int arr[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
        cin >> arr[i];

    int maxval = 0;
    for(int i = 0;i < n; i++)
    {
        for(int j = i;j < n;j++)
        {
            maxval = max(maxval , arr[j]- arr[i]);
        }
    }

    cout << maxval << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.4. Implementación del programa – optimización

Basado en el método de fuerza bruta anterior, se lleva a cabo la optimización. Para comprenderlo completamente, se dibuja un diagrama de demostración basado en el análisis de ideas:

Luego, para implementar el programa, escriba la entrada según sea necesario, luego defina minval para inicializar arr[0] como el valor mínimo asumido para la comparación transversal y la actualización, y luego defina un maxSub para representar la diferencia máxima de minval al atravesar a la posición i , Vale la pena tener en cuenta que al atravesar, preste atención al orden de minval y maxSub. Primero encuentre el valor mínimo minval y luego busque maxSub.

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    int n = 0;
    cin >> n;
    vector<int> arr(n);
    int m = 0;
    while(n--)
    {
        cin >> arr[m];
        m++;
    }
    int minval = arr[0];
    int submax = 0;
    for(int i = 0;i<arr.size();i++)
    {
        minval = min(arr[i],minval);
        submax = max(submax, arr[i] - minval);
    }
    cout << submax << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3. [Grupo de Popularización NOIP2002] Cruzando el Peón del Río

3.1.

3.2.Ideas

Después de leer la pregunta, sabrás cuántos caminos hay como máximo para ir del punto A al punto B según ciertas reglas. Al analizar la pregunta, debe saber que de acuerdo con ciertas reglas, puede ir hacia la derecha o hacia abajo, lo que plantea la idea de programación dinámica dp. A lo que también debe prestar atención en la pregunta es al punto de control. del caballo no se puede mover (visitar), es decir, el caballo en el ajedrez. Los puntos diseñados por el "sol" diagonal en las coordenadas, incluido el punto de partida del caballo, se denominan puntos de control. Entre ellos, el caballo es un punto fijo (x, y) dado al principio, y la pregunta también da la relación entre el punto de salto del caballo y el punto de partida del caballo. Además, cabe señalar que según el ejemplo y el tablero de ajedrez, el tamaño del tablero de ajedrez es (n+1)(m+1)。
Por lo tanto, con base en el análisis anterior, podemos concluir que:
(1) Puede utilizar ideas dp de programación dinámica para resolver problemas;
(2) El punto de control del caballo, además del "sol" diagonal, también incluye su propia posición inicial;
(3). El tamaño del tablero de ajedrez es (n+1).(m+1).
Por lo tanto, después de analizar los puntos de atención, volvemos a la representación de estado dp y la ecuación de transición de estado de la programación dinámica;
Según las reglas para caminar del tema, el estado dp [i] [j] se define para representar: hay como máximo varios caminos hacia esta posición;
Derive la ecuación de transición de estado: dp[i][j] = d[i][j-1] + d[i-1][j];
Además, tenga en cuenta que si la posición inicial del punto B coincide con la posición inicial del caballo o el punto de control, y la parte superior e izquierda del punto B están todas bloqueadas, es decir, el punto de control, entonces en el caso extremo anterior , en este momento dp[i] [j] = 0; Luego, el siguiente paso es la implementación del programa.

3.3. Implementación del programa – dp

Primero, escriba la entrada de acuerdo con el análisis de la idea, defina y abra la matriz dp (dos trampas se discutirán más adelante) y de acuerdo con el tamaño del tablero de ajedrez, para poder describir las coordenadas de manera uniforme, se necesita un extra Aquí se abrirán las filas y columnas, luego se deben asignar xey. Simplemente establezca las coordenadas +=1, luego explore el problema de inicialización de dp y haga un dibujo para que quede más claro:

Luego, la matriz bidimensional real se recorre desde [1, n + 1] y [1, m + 1], juzgando constantemente el procesamiento de situaciones extremas y finalmente generando dp [n + 1] [m + 1]. En este punto, no hay ningún problema con la idea. Los pasos resumidos son los siguientes:
(1), mapeando las coordenadas de xey;
(2) Inicialice dp[0][1] = 1 o dp[1][0] = 1 según la definición de la matriz (abra una capa más);
(3) Recorra la matriz de dos dígitos, prestando atención al recorrido del control de límites desde [1, n+1] y [1, m+1];
a. Determinar situaciones extremas: 1. El punto de control del caballo bloquea el camino 2. Problema de coincidencia;
b. Ecuación de transición del estado de ejecución normal: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), finalmente genere dp [n + 1] [m + 1].
Además, los dos errores mencionados anteriormente son que después de terminar de escribir, el envío falló y descubrí que los datos estaban fuera de rango, por lo que es mejor usar long long para abrir la matriz. Otro error es que el rango de tamaño de. la abertura es demasiado grande. Se utiliza el primer piso, por lo que debe ser al menos mayor o igual a 22. Anteriormente, el uso de dp[21][21] no podía aprobar todos los casos de uso.

#include <iostream>
using namespace std;

long long dp[22][22];

int main()
{
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    //映射坐标
    x += 1;
    y += 1;
    //初始化
    dp[0][1] = 1;
    //遍历
    for(int i = 1;i <= n+1; i++)
    {
        for(int j = 1;j <= m+1; j++)
        {
            //极端情况的处理:  1.马控制点 2.自身重合
            if((i != x && j != y && abs(i - x) + abs(j - y) == 3) || (i == x && j == y))
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
    }
    cout << dp[n+1][m+1] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

4. Enlace de pregunta

subcadena palíndromo más larga
El mejor momento para comprar y vender acciones (1)
[Grupo de Popularización NOIP2002] Cruzando el Peón del Río