Κοινή χρήση τεχνολογίας

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

Σύνοψη των σημερινών ερωτήσεων-day010

1. Η μεγαλύτερη υποχορδή παλίνδρομου

1.1 Ερώτηση

1.2 Ιδέες

Αφού διαβάσετε την ερώτηση, γνωρίζετε ότι σε μια συμβολοσειρά μήκους n, βρείτε το μήκος της μεγαλύτερης υποσυμβολοσειράς παλίνδρομου. Μια υποχορδή παλίνδρομου μπορεί να γίνει κατανοητή ως συμμετρική συμβολοσειρά. Λόγω της συμμετρίας, η βασική ιδέα είναι η "μέθοδος επέκτασης του κέντρου", δηλαδή, η συμβολοσειρά διασχίζεται με τη σειρά και στη συνέχεια επεκτείνεται και στις δύο πλευρές του χαρακτήρα Αν οι χαρακτήρες και στις δύο πλευρές είναι ίσοι, τότε είναι καταγράφεται στη μεταβλητή retlen Μετά τη διέλευση, τελικά παίρνουμε Απλά επιστρέψτε το μέγιστο μήκος. Για να διευκολυνθεί η κατανόηση, σχεδιάστε μια εικόνα:

Επιπλέον, κατά την ανάλυση του παραδείγματος, πρέπει να προσέχουμε και τη διαφορά μεταξύ περιττών και ζυγών αριθμών, οπότε το επόμενο βήμα είναι η υλοποίηση του προγράμματος.

1.3 Εφαρμογή προγράμματος

Πρώτον, σύμφωνα με τη "μέθοδο επέκτασης του κέντρου" της ανάλυσης ιδεών, η συμβολοσειρά διασχίζεται και επεκτείνεται από τον κεντρικό σταθμό στο i αριθμοί και ζυγοί αριθμοί, αντίστοιχα Βρείτε τη μέγιστη τιμή και, τέλος, συγκρίνετε τη για να λάβετε το τελικό μέγιστο retlen και επιστρέψτε την.

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. Η καλύτερη στιγμή για αγορά και πώληση μετοχών (1)

2.1 Ερώτηση

2.2 Ιδέες

Αφού διαβάσετε την ερώτηση, γνωρίζετε ότι για τον μηχανισμό αγοράς και πώλησης μιας ομάδας μετοχών, μπορείτε να αγοράσετε και να πουλήσετε μόνο μία φορά πολλά χάνεις, δηλαδή δεν υπάρχει κέρδος, τότε βγάζεις 0 Αυτό είναι. Στη συνέχεια, η βασική ιδέα είναι να απαριθμήσουμε τη μέθοδο ωμής δύναμης, να βρούμε τη διαφορά κέρδους κάθε ομάδας και να επιστρέψουμε τη μέγιστη τιμή Αφού το δοκιμάσουμε, διαπιστώνεται ότι το χρονικό όριο για το δύο στρώματα θα λήξει και αυτό το πρόβλημα περιορίζεται σε 1 ms για επίλυση. Επομένως, είναι απαραίτητο να γίνει βελτιστοποίηση με βάση τη μέθοδο της ωμής δύναμης, επομένως γράφεται και η μέθοδος ωμής δύναμης Στη συνέχεια, με βάση τη μέθοδο ωμής δύναμης, η οπισθοδρόμηση έχει επαναληφθεί πάρα πολλές φορές, βελτιστοποίηση, σκέψη και ανακάλυψη, αν σκεφτούμε σε. αντίστροφα, εξετάστε πρώτα την πώληση Στη συνέχεια, χρειάζεται μόνο να βρείτε την ελάχιστη αξία πριν από το σημείο πώλησης και η διαφορά που προκύπτει είναι η μέγιστη διαφορά, πράγμα που σημαίνει ότι χρειάζεται να το διασχίσετε μόνο μία φορά. Το επόμενο βήμα είναι η υλοποίηση του προγράμματος.

2.3 Εφαρμογή προγράμματος

Πρώτον, σύμφωνα με την ανάλυση της μεθόδου ωμής δύναμης, απαριθμούνται όλες οι καταστάσεις προκειμένου να βρεθεί η μέγιστη έξοδος διαφοράς Αυτή η ερώτηση θα λήξει. Πρέπει λοιπόν να βελτιστοποιηθεί.

#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 Υλοποίηση προγράμματος – βελτιστοποίηση

Με βάση την παραπάνω μέθοδο ωμής δύναμης, πραγματοποιείται βελτιστοποίηση για την πλήρη κατανόηση της, σχεδιάζεται ένα διάγραμμα επίδειξης με βάση την ανάλυση ιδεών:

Στη συνέχεια, για να υλοποιήσετε το πρόγραμμα, γράψτε την είσοδο όπως απαιτείται, μετά ορίστε το minval για να αρχικοποιήσετε το arr[0] ως την υποτιθέμενη ελάχιστη τιμή για σύγκριση και ενημέρωση διέλευσης και, στη συνέχεια, ορίστε ένα maxSub για να αντιπροσωπεύει τη μέγιστη διαφορά από το minval κατά τη διέλευση στη θέση i , το οποίο αξίζει Σημειώστε ότι κατά τη διέλευση, προσέξτε τη σειρά των minval και maxSub Αρχικά βρείτε την ελάχιστη τιμή minval και μετά βρείτε το 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 Popularization Group] Διασχίζοντας το πιόνι του ποταμού

3.1 Ερώτηση

3.2 Ιδέες

Αφού διαβάσετε την ερώτηση, θα μάθετε πόσα μονοπάτια υπάρχουν το πολύ για να πάτε από το σημείο Α στο σημείο Β σύμφωνα με ορισμένους κανόνες. Όταν αναλύετε την ερώτηση, πρέπει να γνωρίζετε ότι σύμφωνα με ορισμένους κανόνες, μπορείτε να πάτε δεξιά ή προς τα κάτω, κάτι που αναδεικνύει την ιδέα του δυναμικού προγραμματισμού dp Αυτό που πρέπει επίσης να προσέξετε στην ερώτηση είναι ότι το σημείο ελέγχου του αλόγου δεν μπορεί να μετακινηθεί (επισκεπτόταν), δηλαδή ο ιππότης στο σκάκι Τα σημεία που σχεδιάζει ο διαγώνιος «ήλιος» στις συντεταγμένες, συμπεριλαμβανομένου του σημείου εκκίνησης του αλόγου, ονομάζονται σημεία ελέγχου. Μεταξύ αυτών, το άλογο είναι ένα σταθερό σημείο (x, y) που δίνεται στην αρχή, και η ερώτηση δίνει επίσης τη σχέση μεταξύ του σημείου άλματος του αλόγου και του σημείου εκκίνησης του αλόγου. Επιπλέον, πρέπει να σημειωθεί ότι σύμφωνα με το παράδειγμα και τη σκακιέρα το μέγεθος της σκακιέρας είναι (n+1)(m+1).
Επομένως, με βάση την παραπάνω ανάλυση, μπορούμε να συμπεράνουμε ότι:
(1) Μπορείτε να χρησιμοποιήσετε ιδέες dp δυναμικού προγραμματισμού για να λύσετε προβλήματα.
(2) Το σημείο ελέγχου του αλόγου, εκτός από τον διαγώνιο "ήλιο", περιλαμβάνει και τη δική του θέση εκκίνησης.
(3) Το μέγεθος της σκακιέρας είναι (n+1).(m+1).
Επομένως, αφού αναλύσουμε τα σημεία προσοχής, επιστρέφουμε στην αναπαράσταση κατάστασης dp και στην εξίσωση μετάβασης κατάστασης του δυναμικού προγραμματισμού.
Με βάση τους κανόνες βάδισης του θέματος, η κατάσταση dp[i][j] ορίζεται να αντιπροσωπεύει: υπάρχουν το πολύ πολλά μονοπάτια σε αυτή τη θέση.
Εξάγετε την εξίσωση μετάβασης κατάστασης: dp[i][j] = d[i][j-1] + d[i-1][j];
Επιπλέον, σημειώστε ότι εάν η αρχική θέση του σημείου Β συμπίπτει με την αρχική θέση του αλόγου ή του σημείου ελέγχου, και το πάνω και το αριστερό του σημείου Β είναι όλα μπλοκαρισμένα, δηλαδή το σημείο ελέγχου, τότε στην παραπάνω ακραία περίπτωση , αυτή τη στιγμή dp[i] [j] = 0 Τότε το επόμενο βήμα είναι η υλοποίηση του προγράμματος.

3.3 Υλοποίηση προγράμματος – dp

Πρώτα, γράψτε την είσοδο σύμφωνα με την ανάλυση της ιδέας, ορίστε και ανοίξτε τον πίνακα dp (δύο παγίδες θα συζητηθούν αργότερα) και σύμφωνα με το μέγεθος της σκακιέρας, για να μπορέσετε να περιγράψετε τις συντεταγμένες ομοιόμορφα, ένα επιπλέον Η γραμμή και η στήλη θα ανοίξουν εδώ και, στη συνέχεια, τα x και y πρέπει να αντιστοιχιστούν Απλώς ορίστε τις συντεταγμένες +=1, στη συνέχεια εξερευνήστε το πρόβλημα αρχικοποίησης του dp και σχεδιάστε μια εικόνα για να το κάνετε πιο σαφές:

Στη συνέχεια, ο πραγματικός δισδιάστατος πίνακας διασχίζεται από το [1, n+1] και το [1, m+1], κρίνοντας συνεχώς την επεξεργασία ακραίων καταστάσεων και τελικά βγάζοντας dp[n+1][m+1]. Σε αυτό το σημείο, δεν υπάρχει πρόβλημα με την ιδέα Τα συνοπτικά βήματα είναι τα εξής:
(1), χαρτογράφηση των συντεταγμένων των x και y.
(2) Αρχικοποίηση dp[0][1] = 1 ή dp[1][0] = 1 σύμφωνα με τον ορισμό του πίνακα (άνοιξε ένα ακόμη επίπεδο).
(3) Διασχίστε τον διψήφιο πίνακα, δίνοντας προσοχή στη διέλευση του οριακού ελέγχου από [1, n+1] και [1, m+1].
α. Προσδιορίστε ακραίες καταστάσεις: 1. Το σημείο ελέγχου του αλόγου μπλοκάρει τη διαδρομή 2. Πρόβλημα σύμπτωσης.
β) Εξίσωση μετάβασης σε κανονική κατάσταση εκτέλεσης: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), τελικά εξάγετε dp[n+1][m+1].
Επιπλέον, οι δύο παγίδες που αναφέρθηκαν παραπάνω είναι ότι αφού τελείωσα τη γραφή, η υποβολή απέτυχε και διαπίστωσα ότι τα δεδομένα ήταν εκτός εμβέλειας, επομένως είναι καλύτερο να χρησιμοποιήσετε μεγάλο χρονικό διάστημα για να ανοίξετε τη συστοιχία Το άνοιγμα είναι πολύ μεγάλο Ο πρώτος όροφος χρησιμοποιείται, επομένως πρέπει να είναι τουλάχιστον μεγαλύτερος ή ίσος με 22. Προηγουμένως, η χρήση dp[21][21] δεν μπορούσε να περάσει όλες τις περιπτώσεις χρήσης.

#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. Σύνδεσμος ερώτησης

μακρύτερη υποχορδή παλίνδρομου
Η καλύτερη στιγμή για αγορά και πώληση μετοχών (1)
[NOIP2002 Popularization Group] Διασχίζοντας το πιόνι του ποταμού