Berbagi teknologi

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

Ringkasan soal hari ini-hari010

1. Substring palindrom terpanjang

1.1.Pertanyaan

1.2.Ide

Setelah membaca soal, Anda mengetahui bahwa dalam string dengan panjang n, carilah panjang substring palindrom terpanjang. Substring palindrom dapat dipahami sebagai string simetris. Karena simetri, ide dasarnya adalah "metode pemuaian pusat", yaitu string dilintasi secara berurutan, dan kemudian diperluas ke kedua sisi karakter. Jika karakter di kedua sisi sama, maka karakter tersebut adalah dicatat dalam variabel retlen. Setelah melintasi, akhirnya kita mendapatkan kembalikan panjang maksimumnya. Untuk memudahkan pemahaman, buatlah gambar:

Selain itu, dalam menganalisis contoh juga harus memperhatikan selisih bilangan ganjil dan genap, sehingga langkah selanjutnya adalah implementasi program.

1.3.Pelaksanaan program

Pertama, menurut "metode perluasan pusat" analisis ide, string dilintasi dan diperluas dari stasiun pusat di i. Retlen yang diperoleh pada gilirannya terus dibandingkan dan diperbarui dengan retlen. Kemudian, karena perlu untuk membedakan antara ganjil angka dan angka genap, masing-masing Temukan nilai maksimum, dan terakhir bandingkan untuk mendapatkan retlen maksimum akhir dan kembalikan.

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. Waktu terbaik untuk membeli dan menjual saham (1)

2.1.Pertanyaan

2.2.Ide

Setelah membaca pertanyaan tersebut, Anda tahu bahwa untuk mekanisme jual beli sekelompok saham, Anda hanya bisa membeli dan menjual satu kali. Mari kita cari keuntungan maksimal yang didapat Jika Anda kehilangan uang tidak peduli kapan Anda membeli atau menjual, tidak peduli bagaimana caranya banyak yang rugi yaitu tidak ada untung, maka outputnya 0 Itu saja. Kemudian ide dasarnya adalah metode enumerasi/brute force, mencari selisih keuntungan masing-masing kelompok, dan mengembalikan nilai maksimal. Setelah mencobanya, ternyata waktu dua lapis untuk akan habis, dan masalah ini terbatas pada 1 ms untuk diselesaikan. Oleh karena itu perlu dilakukan optimasi berdasarkan metode brute force, sehingga ditulis juga metode brute force, kemudian berdasarkan metode brute force, backtracking sudah terlalu sering diulang, optimasi, pemikiran dan penemuan, jika kita berpikir dalam. sebaliknya, pertimbangkan dulu untuk menjual. Kemudian, Anda hanya perlu mencari nilai minimum sebelum titik penjualan, dan selisih yang didapat adalah selisih maksimum yang artinya Anda hanya perlu melintasinya satu kali saja. Langkah selanjutnya adalah implementasi program.

2.3.Pelaksanaan program

Pertama, menurut analisis metode brute force, semua situasi dihitung untuk menemukan keluaran perbedaan maksimum. Jadi harus dioptimalkan.

#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. Implementasi program – optimalisasi

Berdasarkan metode brute force di atas, dilakukan optimasi Untuk memahaminya secara utuh, dibuat diagram demonstrasi berdasarkan analisis ide:

Kemudian untuk mengimplementasikan program, tulis input sesuai kebutuhan, lalu tentukan minval untuk menginisialisasi arr[0] sebagai asumsi nilai minimum untuk perbandingan dan pembaruan traversal, lalu tentukan maxSub untuk mewakili perbedaan maksimum dari minval saat melakukan traversal ke posisi i , yang perlu diperhatikan bahwa saat melakukan traversing, perhatikan urutan minval dan maxSub. Pertama cari nilai minimum minval lalu cari 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. [Kelompok Popularisasi NOIP2002] Menyeberangi Sungai Pion

3.1.Pertanyaan

3.2.Ide

Setelah membaca soal tersebut, Anda akan mengetahui paling banyak berapa banyak jalur yang harus ditempuh dari titik A ke titik B menurut aturan tertentu. Saat menganalisa soal perlu anda ketahui bahwa menurut aturan tertentu anda bisa ke kanan atau ke bawah yang memunculkan ide dp pemrograman dinamis. Yang juga perlu diperhatikan dalam soal adalah titik kendali kuda tidak dapat dipindahkan (dikunjungi), yaitu ksatria dalam catur. Titik-titik yang dirancang oleh diagonal "matahari" pada koordinat, termasuk titik awal kudanya, disebut titik kendali. Diantaranya, kuda adalah titik tetap (x, y) yang diberikan di awal, dan soal tersebut juga memberikan hubungan antara titik lompat kuda dan titik awal kuda. Selain itu perlu diperhatikan bahwa sesuai contoh dan papan catur, ukuran papan catur tersebut adalah (n+1)(m+1)
Oleh karena itu, berdasarkan analisis di atas, kita dapat menyimpulkan bahwa:
(1) Anda dapat menggunakan ide dp pemrograman dinamis untuk memecahkan masalah;
(2) Titik kendali kuda, selain "matahari" diagonal, juga mencakup posisi awalnya sendiri;
(3). Ukuran papan catur adalah (n+1)(m+1) adalah bilangan bulat positif.
Oleh karena itu, setelah menganalisis poin perhatian, kita kembali ke representasi keadaan dp dan persamaan transisi keadaan dari pemrograman dinamis;
Berdasarkan aturan berjalan dari topik tersebut, status dp[i][j] didefinisikan untuk mewakili: paling banyak ada beberapa jalur menuju posisi ini;
Turunkan persamaan transisi keadaan: dp[i][j] = d[i][j-1] + d[i-1][j];
Selain itu, perhatikan bahwa jika posisi awal titik B bertepatan dengan posisi awal kuda atau titik kendali, dan bagian atas dan kiri titik B semuanya terhalang, yaitu titik kendali, maka dalam kasus ekstrim di atas , saat ini dp[i] [j] = 0; Kemudian langkah selanjutnya adalah implementasi program.

3.3. Implementasi program – dp

Pertama, tulis input sesuai dengan analisis ide, tentukan dan buka array dp (dua jebakan akan dibahas nanti), dan sesuai dengan ukuran papan catur, agar dapat menggambarkan koordinat secara seragam, tambahan baris dan kolom akan dibuka di sini, lalu x dan y perlu dipetakan. Tetapkan saja koordinat +=1, lalu pelajari masalah inisialisasi dp, dan buatlah gambar agar lebih jelas:

Kemudian, array dua dimensi sebenarnya dilintasi dari [1, n+1] dan [1, m+1], terus-menerus menilai pemrosesan situasi ekstrem, dan akhirnya menghasilkan dp[n+1][m+1]. Pada titik ini, tidak ada masalah dengan ide tersebut. Langkah-langkah ringkasannya adalah sebagai berikut:
(1), memetakan koordinat x dan y;
(2) Inisialisasi dp[0][1] = 1 atau dp[1][0] = 1 sesuai dengan definisi array (buka satu lapisan lagi);
(3) Lintasi larik dua digit, perhatikan traversal kontrol batas dari [1, n+1] dan [1, m+1];
a. Menentukan situasi ekstrim: 1. Titik kendali kuda menghalangi jalan 2. Masalah kebetulan;
b.Persamaan transisi keadaan eksekusi normal: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), akhirnya menghasilkan dp[n+1][m+1].
Selain itu, dua kendala yang disebutkan di atas adalah setelah saya selesai menulis, pengiriman gagal dan saya menemukan bahwa data berada di luar jangkauan, jadi yang terbaik adalah menggunakan long long untuk membuka array bukaannya terlalu besar. Lantai pertama yang digunakan, jadi minimal harus lebih besar atau sama dengan 22. Sebelumnya, penggunaan dp[21][21] tidak dapat melewati semua kasus penggunaan.

#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. Tautan pertanyaan

substring palindrom terpanjang
Waktu terbaik untuk membeli dan menjual saham (1)
[Grup Popularisasi NOIP2002] Menyeberangi Sungai Pion