Teknologian jakaminen

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

Yhteenveto tämän päivän kysymyspäivästä010

1. Pisin palindromi-alijono

1.1

1.2 Ideoita

Luettuasi kysymyksen tiedät, että merkkijonosta, jonka pituus on n, etsi pisimmän palindromi-alijonon pituus. Palindromi-alijono voidaan ymmärtää symmetriseksi merkkijonoksi. Symmetrian vuoksi perusideana on "keskilaajennusmenetelmä", eli merkkijono kuljetetaan peräkkäin ja laajennetaan sitten merkin molemmille puolille retlen-muuttujaan tallennetun poikkikierron jälkeen saamme lopulta vain maksimipituuden. Ymmärtämisen helpottamiseksi piirrä kuva:

Lisäksi esimerkkiä analysoitaessa on kiinnitettävä huomiota myös parittomien ja parillisten lukujen eroon, joten seuraava askel on ohjelman toteutus.

1.3 Ohjelman toteuttaminen

Ensin idea-analyysin "keskuksen laajennusmenetelmän" mukaan merkkijonoa kuljetetaan ja laajennetaan keskusasemalta i:stä saatua retleniä puolestaan ​​verrataan ja päivitetään jatkuvasti retlenillä numerot ja vastaavasti parilliset luvut Etsi maksimiarvo ja lopuksi vertaa sitä saadaksesi lopullisen maksimiretlenin ja palauttaaksesi sen.

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. Paras aika ostaa ja myydä osakkeita (1)

2.1

2.2 Ideoita

Kun olet lukenut kysymyksen, tiedät, että osakeryhmän osto- ja myyntimekanismilla voit ostaa ja myydä vain kerran paljon menetät, eli voittoa ei ole, sitten tuotos 0 Siinä kaikki. Sitten perusideana on luetella/raaka voima -menetelmä, löytää kunkin ryhmän voittoero ja palauttaa maksimiarvo Kokeilun jälkeen todetaan, että kaksikerroksinen for time out, ja tämä ongelma rajoittuu 1ms ratkaistavaksi. Siksi on välttämätöntä optimoida raa'an voiman menetelmällä, joten raa'an voiman menetelmällä on myös kirjoitettu. Sitten raa'an voiman menetelmään perustuen on toistettu liian monta kertaa taaksepäin, optimointia, ajattelua ja löytämistä, jos ajatellaan. päinvastoin, harkitse ensin myyntiä Sitten sinun tarvitsee vain löytää vähimmäisarvo ennen myyntikohtaa, ja saatu ero on suurin ero, mikä tarkoittaa, että sinun tarvitsee kulkea se vain kerran. Seuraava askel on ohjelman toteuttaminen.

2.3 Ohjelman toteuttaminen

Ensin raa'an voiman menetelmän analyysin mukaan kaikki tilanteet luetellaan, jotta löydettäisiin suurin ero. Tämä kysymys aikakatkaisee. Joten se on optimoitava.

#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 Ohjelman toteutus – optimointi

Yllä olevaan raakavoimamenetelmään perustuen suoritetaan optimointi. Jotta se ymmärrettäisiin täysin, piirretään idea-analyysin perusteella esittelykaavio:

Tämän jälkeen ohjelman toteuttamiseksi kirjoita syöte tarpeen mukaan, määritä sitten minval alustamaan arr[0] oletukseksi läpikulkuvertailun ja -päivityksen vähimmäisarvoksi, ja määritä sitten maxSub, joka edustaa maksimieroa minval:iin siirrettäessä i-kohtaan. , joka kannattaa Huomaa, että kuljetettaessa tulee huomioida minvalin ja maxSub:n järjestys. Etsi ensin minimiarvo minval ja sitten 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. [NOIP2002 Popularisation Group] Crossing the River Pawn

3.1

3.2. Ideoita

Luettuasi kysymyksen tiedät kuinka monta polkua on korkeintaan pisteestä A pisteeseen B tiettyjen sääntöjen mukaan. Kysymystä analysoidessasi sinun on tiedettävä, että tiettyjen sääntöjen mukaan voit mennä oikealle tai alas, mikä tuo esiin ajatuksen dynaamisesta ohjelmoinnista dp. Mihin sinun on myös kiinnitettävä huomiota kysymyksessä hevosta ei voi siirtää (vierailla), eli ritari shakissa Pisteitä, jotka on suunnitellut diagonaalinen "auringon" koordinaatteihin, mukaan lukien hevosen aloituspiste, kutsutaan ohjauspisteiksi. Niistä hevonen on alussa annettu kiinteä piste (x, y), ja kysymys antaa myös hevosen hyppypisteen ja hevosen lähtökohdan välisen suhteen. Lisäksi on huomioitava, että esimerkin ja shakkilaudan mukaan shakkilaudan koko on (n+1)(m+1).
Siksi voimme päätellä yllä olevan analyysin perusteella, että:
(1) Voit käyttää dynaamisen ohjelmoinnin dp-ideoita ongelmien ratkaisemiseen;
(2) Hevosen ohjauspisteeseen kuuluu diagonaalisen "auringon" lisäksi myös oma lähtöasema;
(3) Shakkilaudan koko on (n+1).(m+1).
Siksi huomiopisteiden analysoinnin jälkeen palaamme dynaamisen ohjelmoinnin dp-tilan esitykseen ja tilasiirtymäyhtälöön;
Aiheen kävelysääntöjen perusteella dp[i][j]-tila on määritelty edustamaan: tähän paikkaan on korkeintaan useita polkuja;
Johda tilasiirtymäyhtälö: dp[i][j] = d[i][j-1] + d[i-1][j];
Lisäksi on huomioitava, että jos pisteen B aloitusasema on sama kuin hevosen tai tarkastuspisteen aloitusasema ja pisteen B ylä- ja vasen puoli ovat kaikki tukossa, eli tarkastuspiste, niin yllä olevassa ääritapauksessa , tällä hetkellä dp[i] [j] = 0 Sitten seuraava vaihe on ohjelman toteutus.

3.3 Ohjelman toteuttaminen – dp

Ensin kirjoitetaan syöte idean analyysin mukaan, määritellään ja avataan dp-taulukko (kaksi sudenkuoppaa käsitellään myöhemmin) ja shakkilaudan koon mukaan, jotta koordinaatit pystytään kuvaamaan tasaisesti, ylimääräinen rivi ja sarake avataan tähän, sitten x ja y on kartoitettava. Aseta vain koordinaatit +=1, tutki sitten dp:n alustusongelmaa ja piirrä kuva selventääksesi sitä:

Sitten varsinaisen kaksiulotteisen matriisin läpi kuljetaan [1, n+1] ja [1, m+1], jatkuvasti arvioiden ääritilanteiden käsittelyä ja lopuksi tulostetaan dp[n+1][m+1]. Tässä vaiheessa idean kanssa ei ole ongelmia. Yhteenvetovaiheet ovat seuraavat:
(1), kartoitetaan x:n ja y:n koordinaatit;
(2) Alusta dp[0][1] = 1 tai dp[1][0] = 1 taulukon määritelmän mukaan (avaa vielä yksi kerros);
(3) Kulje kaksinumeroinen matriisi kiinnittäen huomiota rajojen ohjauksen läpikulkuun kohdista [1, n+1] ja [1, m+1];
a. Määritä ääritilanteet: 1. Hevosen ohjauspiste estää polun 2. Sattumaongelma;
b. Normaalin suoritustilan siirtymäyhtälö: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), lopulta ulostulo dp[n+1][m+1].
Lisäksi kaksi yllä mainittua sudenkuoppaa ovat se, että kirjoittamisen jälkeen lähetys epäonnistui ja huomasin, että tiedot olivat alueen ulkopuolella, joten on parasta käyttää pitkää pituutta taulukon avaamiseen Toinen sudenkuoppa on, että kokoalue aukko on liian suuri Ensimmäinen kerros on käytössä, joten sen on oltava vähintään 22. Aikaisemmin dp[21][21] ei voinut läpäistä kaikkia käyttötapauksia.

#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. Kysymyslinkki

pisin palindromimerkkijono
Paras aika ostaa ja myydä osakkeita (1)
[NOIP2002 Popularisation Group] Crossing the River Pawn