Condivisione della tecnologia

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

Riepilogo delle domande di oggi-day010

1. La sottostringa palindroma più lunga

1.1

1.2. Idee

Dopo aver letto la domanda, sai che in una stringa di lunghezza n, trova la lunghezza della sottostringa palindroma più lunga. Una sottostringa palindroma può essere intesa come una stringa simmetrica. A causa della simmetria, l'idea di base è il "metodo di espansione centrale", ovvero la stringa viene attraversata in sequenza e quindi viene espansa su entrambi i lati del carattere. Se i caratteri su entrambi i lati sono uguali, allora lo è registrato nella variabile retlen Dopo l'attraversamento, otteniamo finalmente la lunghezza massima. Per facilitare la comprensione, disegna un'immagine:

Inoltre, analizzando l'esempio, è necessario prestare attenzione anche alla differenza tra numeri pari e dispari, quindi il passo successivo è l'implementazione del programma.

1.3. Attuazione del programma

Innanzitutto, secondo il "metodo dell'espansione centrale" dell'analisi delle idee, la stringa viene attraversata ed espansa dalla stazione centrale in i. Il retlen ottenuto a sua volta viene continuamente confrontato e aggiornato con retlen, poiché è necessario distinguere tra dispari numeri e numeri pari, rispettivamente Trova il valore massimo e infine confrontalo per ottenere il retlen massimo finale e restituirlo.

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. Il momento migliore per acquistare e vendere azioni (1)

2.1

2.2

Dopo aver letto la domanda, sai che per il meccanismo di acquisto e vendita di un gruppo di azioni, puoi acquistare e vendere solo una volta. Troviamo il profitto massimo ottenuto se perdi denaro, non importa quando acquisti o vendi, non importa come molto perdi, cioè non c’è profitto, quindi output 0 Questo è tutto. Quindi, l'idea di base è quella di enumerare il metodo della forza bruta, trovare la differenza di profitto di ciascun gruppo e restituire il valore massimo. Dopo averlo provato, si scopre che il timeout a due livelli è limitato a 1ms per risolvere. Pertanto, è necessario ottimizzare in base al metodo della forza bruta, quindi è scritto anche il metodo della forza bruta. Quindi, in base al metodo della forza bruta, il backtracking è stato ripetuto troppe volte, ottimizzazione, riflessione e scoperta, se pensiamo. inverso, considera prima la vendita. Quindi, devi solo trovare il valore minimo prima del punto di vendita e la differenza ottenuta è la differenza massima, il che significa che devi attraversarla solo una volta. Il passo successivo è l’attuazione del programma.

2.3. Attuazione del programma

Innanzitutto, secondo l'analisi del metodo della forza bruta, tutte le situazioni vengono enumerate per trovare l'output della differenza massima. Questa domanda scade. Quindi deve essere ottimizzato.

#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 Attuazione del programma – ottimizzazione

Sulla base del metodo della forza bruta sopra descritto, viene eseguita l'ottimizzazione. Per comprenderla appieno, viene disegnato un diagramma dimostrativo basato sull'analisi dell'idea:

Quindi, per implementare il programma, scrivere l'input come richiesto, quindi definire minval per inizializzare arr[0] come valore minimo presupposto per il confronto e l'aggiornamento trasversali, quindi definire un maxSub per rappresentare la differenza massima da minval durante l'attraversamento alla posizione i , che vale Nota che durante l'attraversamento, presta attenzione all'ordine di minval e maxSub Trova prima il valore minimo minval e poi trova 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. [Gruppo di divulgazione NOIP2002] Attraversando il fiume Pedone

3.1

3.2. Idee

Dopo aver letto la domanda saprai quanti percorsi ci sono al massimo per andare dal punto A al punto B secondo determinate regole. Quando analizzi la domanda, devi sapere che secondo determinate regole puoi andare a destra o in basso, il che fa emergere l'idea della programmazione dinamica dp. Ciò a cui devi prestare attenzione anche nella domanda è il punto di controllo del cavallo non può essere spostato (visitato), cioè il cavaliere negli scacchi. I punti disegnati dal "sole" diagonale sulle coordinate, compreso il punto di partenza del cavallo, sono chiamati punti di controllo. Tra questi, il cavallo è un punto fisso (x, y) dato all'inizio, e la domanda fornisce anche la relazione tra il punto di salto del cavallo e il punto di partenza del cavallo. Inoltre, va notato che, secondo l'esempio e la scacchiera, la dimensione della scacchiera è (n+1)(m+1).
Pertanto, sulla base dell’analisi di cui sopra, possiamo concludere che:
(1) È possibile utilizzare idee DP di programmazione dinamica per risolvere problemi;
(2) Il punto di controllo del cavallo, oltre al "sole" diagonale, comprende anche la propria posizione di partenza;
(3) La dimensione della scacchiera è (n+1)(m+1).
Pertanto, dopo aver analizzato i punti di attenzione, torniamo alla rappresentazione dello stato dp e all'equazione di transizione di stato della programmazione dinamica;
In base alle regole di camminata dell'argomento, lo stato dp[i][j] è definito per rappresentare: ci sono al massimo diversi percorsi verso questa posizione;
Derivare l'equazione di transizione di stato: dp[i][j] = d[i][j-1] + d[i-1][j];
Inoltre, si noti che se la posizione iniziale del punto B coincide con la posizione iniziale del cavallo o del punto di controllo, e la parte superiore e sinistra del punto B sono tutte bloccate, cioè il punto di controllo, allora nel caso estremo sopra , in questo momento dp[i] [j] = 0; il passo successivo è l'implementazione del programma.

3.3 Attuazione del programma – dp

Per prima cosa scrivere l'input in base all'analisi dell'idea, definire e aprire l'array dp (due trappole verranno discusse in seguito) e in base alle dimensioni della scacchiera, per poter descrivere le coordinate in modo uniforme, un extra riga e colonna verranno aperte qui, quindi xey devono essere mappate. Basta impostare le coordinate +=1, quindi esplorare il problema di inizializzazione di dp e disegnare un'immagine per renderlo più chiaro:

Quindi, l'effettivo array bidimensionale viene attraversato da [1, n+1] e [1, m+1], valutando costantemente l'elaborazione di situazioni estreme e infine producendo dp[n+1][m+1]. A questo punto, non ci sono problemi con l’idea. I passaggi riepilogativi sono i seguenti:
(1), mappando le coordinate di xey;
(2) Inizializzare dp[0][1] = 1 o dp[1][0] = 1 in base alla definizione dell'array (aprire un ulteriore livello);
(3) Attraversare l'array di due cifre, prestando attenzione all'attraversamento del controllo del confine da [1, n+1] e [1, m+1];
a. Determinare situazioni estreme: 1. Il punto di controllo del cavallo blocca il percorso 2. Problema di coincidenza;
b. Equazione di transizione dello stato di esecuzione normale: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), infine restituisce dp[n+1][m+1].
Inoltre, le due insidie ​​sopra menzionate sono che dopo aver finito di scrivere, l'invio non è riuscito e ho scoperto che i dati erano fuori intervallo, quindi è meglio utilizzare long long per aprire l'array. Un'altra trappola è l'intervallo di dimensioni l'apertura è troppo grande. Viene utilizzato il primo piano, quindi deve essere almeno maggiore o uguale a 22. In precedenza, l'utilizzo di dp[21][21] non poteva superare tutti i casi d'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. Collegamento alla domanda

sottostringa palindroma più lunga
Il momento migliore per acquistare e vendere azioni (1)
[Gruppo di divulgazione NOIP2002] Attraversando il fiume Pedone