Compartilhamento de tecnologia

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

Resumo das perguntas de hoje-day010

1. A substring do palíndromo mais longa

1.1.

1.2.

Depois de ler a pergunta, você sabe que em uma string de comprimento n, encontre o comprimento da substring do palíndromo mais longa. Uma substring palíndromo pode ser entendida como uma string simétrica. Por causa da simetria, a ideia básica é o "método de expansão central", ou seja, a string é percorrida em sequência e depois expandida para ambos os lados do caractere. Se os caracteres de ambos os lados forem iguais, então é. registrado na variável retlen. Após percorrer, finalmente obtemos apenas o comprimento máximo. Para facilitar a compreensão, faça um desenho:

Além disso, ao analisar o exemplo, você também deve prestar atenção à diferença entre números ímpares e pares, portanto o próximo passo é a implementação do programa.

1.3. Implementação do programa

Primeiro, de acordo com o "método de expansão central" de análise de ideias, a corda é atravessada e expandida a partir da estação central em i. O retlen obtido por sua vez é continuamente comparado e atualizado com o retlen. números e números pares, respectivamente Encontre o valor máximo e, finalmente, compare-o para obter o valor máximo final e retorne-o.

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. O melhor momento para comprar e vender ações (1)

2.1.

2.2.

Depois de ler a pergunta, você sabe que para o mecanismo de compra e venda de um grupo de ações, você só pode comprar e vender uma vez. Vamos descobrir o lucro máximo obtido se você perder dinheiro, não importa quando você compra ou vende, não importa como. você perde muito, ou seja, não tem lucro, então produz 0 É isso. Então, a ideia básica é enumerar/método de força bruta, encontrar a diferença de lucro de cada grupo e retornar o valor máximo. Depois de tentar, descobre-se que o tempo limite do for de duas camadas expirará e esse problema será limitado a. 1ms para resolver. Portanto, é necessário otimizar com base no método da força bruta, então o método da força bruta também é escrito. Então, com base no método da força bruta, o retrocesso foi repetido muitas vezes, otimização, pensamento e descoberta, se pensarmos em. reverso, primeiro considere a venda Então, você só precisa encontrar o valor mínimo antes do ponto de venda, e a diferença obtida é a diferença máxima, o que significa que você só precisa percorrê-lo uma vez. O próximo passo é a implementação do programa.

2.3. Implementação do programa

Primeiro, de acordo com a análise do método de força bruta, todas as situações são enumeradas para encontrar a saída de diferença máxima. Esta questão irá expirar. Portanto, tem que ser otimizado.

#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. Implementação do programa – otimização

Com base no método de força bruta acima, a otimização é realizada para entendê-lo totalmente, um diagrama de demonstração é desenhado com base na análise da ideia:

Em seguida, para implementar o programa, escreva a entrada conforme necessário, defina minval para inicializar arr[0] como o valor mínimo assumido para comparação e atualização de travessia e, em seguida, defina um maxSub para representar a diferença máxima de minval ao percorrer para a posição i , o que vale a pena observar que ao percorrer, preste atenção à ordem de minval e maxSub. Primeiro encontre o valor mínimo minval e depois encontre 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 Popularização NOIP2002] Cruzando o Rio Peão

3.1.

3.2.

Depois de ler a pergunta, você saberá quantos caminhos existem no máximo para ir do ponto A ao ponto B de acordo com certas regras. Ao analisar a questão, você precisa saber que de acordo com certas regras, você pode ir para a direita ou para baixo, o que traz a ideia de programação dinâmica dp. O que você também precisa prestar atenção na questão é que o ponto de controle. do cavalo não pode ser movido (visitado), ou seja, o cavalo no xadrez Os pontos desenhados pela diagonal “sol” nas coordenadas, incluindo o ponto de partida do cavalo, são chamados de pontos de controle. Dentre elas, o cavalo é um ponto fixo (x, y) dado no início, e a questão também dá a relação entre o ponto de salto do cavalo e o ponto de partida do cavalo. Além disso, deve-se notar que de acordo com o exemplo e o tabuleiro de xadrez, o tamanho do tabuleiro de xadrez é (n+1)(m+1)。
Portanto, com base na análise acima, podemos concluir que:
(1) Você pode usar ideias de programação dinâmica dp para resolver problemas;
(2) O ponto de controle do cavalo, além do “sol” diagonal, inclui também sua própria posição inicial;
(3). O tamanho do tabuleiro de xadrez é (n+1)(m+1).
Portanto, após analisar os pontos de atenção, voltamos à representação do estado dp e à equação de transição de estado da programação dinâmica;
Com base nas regras de caminhada do tópico, o estado dp[i][j] é definido para representar: existem no máximo vários caminhos para esta posição;
Derive a equação de transição de estado: dp[i][j] = d[i][j-1] + d[i-1][j];
Além disso, observe que se a posição inicial do ponto B coincidir com a posição inicial do cavalo ou do ponto de controle, e a parte superior e esquerda do ponto B estiverem todas bloqueadas, ou seja, o ponto de controle, então no caso extremo acima , neste momento dp[i] [j] = 0; Então a próxima etapa é a implementação do programa.

3.3. Implementação do programa – dp.

Primeiro, escreva a entrada de acordo com a análise da ideia, defina e abra o array dp (duas armadilhas serão discutidas mais tarde) e de acordo com o tamanho do tabuleiro de xadrez, para poder descrever as coordenadas uniformemente, um extra linha e coluna serão abertas aqui, então x e y precisam ser mapeados. Basta definir as coordenadas + = 1, explorar o problema de inicialização do dp e fazer um desenho para torná-lo mais claro:

Em seguida, a matriz bidimensional real é percorrida de [1, n+1] e [1, m+1], julgando constantemente o processamento de situações extremas e, finalmente, gerando dp[n+1][m+1]. Neste ponto, não há problema com a ideia. As etapas resumidas são as seguintes:
(1), mapeando as coordenadas de x e y;
(2) Inicialize dp[0][1] = 1 ou dp[1][0] = 1 de acordo com a definição do array (abra mais uma camada);
(3) Percorra a matriz de dois dígitos, prestando atenção à travessia de controle de limite de [1, n+1] e [1, m+1];
a. Determine situações extremas: 1. O ponto de controle do cavalo bloqueia o caminho 2. Problema de coincidência;
b. Equação de transição de estado de execução normal: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), finalmente produza dp[n+1][m+1].
Além disso, as duas armadilhas mencionadas acima são que, depois de terminar de escrever, o envio falhou e descobri que os dados estavam fora do intervalo, por isso é melhor usar long long para abrir o array. Outra armadilha é o intervalo de tamanho de. a abertura é muito grande O primeiro andar é utilizado, portanto deve ser pelo menos maior ou igual a 22. Anteriormente, usar dp[21][21] não conseguia passar em todos os 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. Link da pergunta

substring do palíndromo mais longo
O melhor momento para comprar e vender ações (1)
[Grupo de Popularização NOIP2002] Cruzando o Rio Peão