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

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

🍭 大家好这里是Κιγιοτάκα-σενπάι , ένας προγραμματιστής που αγαπά τους αλγόριθμους

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

✨ Αυτή η σειρά σχεδιάζει να συνεχίσει να ενημερώνεται ερωτήσεις γραπτού τεστ Qiuzhao
👏 感谢大家的订阅➕ 和 喜欢💗

---

📧 清隆这边最近正在收集近一年半互联网笔试题汇总，有需要的小伙伴可以关注 Τέλος άρθρου Πάρτε την κρουαζιέρα της πριγκίπισσας~

🎀 01.A先生的环形花圃

Περιγραφή ερώτησης

Ο κ. Α έχει ένα κυκλικό παρτέρι, το οποίο χωρίζεται σε $n$ περιοχή μπλοκ. Αρχικά ο κ. Α επέλεξε τρεις περιοχές στο παρτέρι για να φυτέψει τριαντάφυλλα.

Τώρα, ο κ. Α θέλει να χρησιμοποιήσει λειτουργίες κινητής τηλεφωνίας για να φτάσει στον ανθόκηποΙσορροπημένη κατάσταση。

Ισορροπημένη κατάσταση: Η απόσταση μεταξύ οποιωνδήποτε δύο περιοχών που φυτεύονται με τριαντάφυλλα δεν είναι μικρότερη από $\kappa$(Η απόσταση μεταξύ των παρακείμενων περιοχών είναι $1$）。

Λειτουργία μετακίνησης: ανταλλαγή της κατάστασης των παρακείμενων περιοχών (η περιοχή τριαντάφυλλου γίνεται άδεια περιοχή, η κενή περιοχή γίνεται περιοχή τριαντάφυλλου).

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

Μορφή εισαγωγής

Εισαγάγετε έναν θετικό ακέραιο αριθμό στην πρώτη γραμμή $t$, αναφέροντας τον αριθμό των ερωτήσεων.

Επόμενο $t$ γραμμές, κάθε γραμμή περιέχει πέντε θετικούς ακέραιους αριθμούς$n$、$\kappa$、${έ\nu \alpha }_1$、${έ\nu \alpha }_2$、${έ\nu \alpha }_3$, αντιπροσωπεύοντας αντίστοιχα τον αριθμό των περιοχών παρτέρι, την απαιτούμενη ελάχιστη απόσταση και την αρχική θέση των τριών περιοχών τριανταφυλλιάς.

Μορφή εξόδου

παραγωγή $t$ γραμμές, καθεμία από τις οποίες δίνει έναν ακέραιο αριθμό που αντιπροσωπεύει τον ελάχιστο αριθμό ανταλλαγών που απαιτούνται για να φέρει το παρτέρι σε ισορροπία.Εάν δεν μπορεί να επιτευχθεί ισορροπία, έξοδος$-1$。

Δείγμα εισαγωγής

3
5 1 1 2 3
5 2 1 2 3
6 2 2 3 6
1
2
3
4

Δείγμα εξόδου

0
-1
1
1
2
3

φασμα ΔΕΔΟΜΕΝΩΝ

$1\le t\le 10^4$
$1\le n\le 10^9$
$1\le \kappa ,{έ\nu \alpha }_1,{έ\nu \alpha }_2,{έ\nu \alpha }_3\le n$

απάντηση

Αυτό το πρόβλημα μπορεί να λυθεί με την ανάλυση των συνθηκών ισορροπίας.

Πρώτον, εάν η απαιτούμενη ελάχιστη απόσταση $\kappa$ Υπέρβαση του αριθμού των περιοχών κήπου$n$ το ένα τρίτο του , τότε η συνθήκη δεν μπορεί να ικανοποιηθεί ανεξάρτητα από το τι, και αυτή τη στιγμή η έξοδος$-1$。

Διαφορετικά, μπορούμε πρώτα να ταξινομήσουμε τις θέσεις των τριών τριαντάφυλλων περιοχών και στη συνέχεια να υπολογίσουμε την απόσταση μεταξύ των παρακείμενων περιοχών τριανταφυλλιάς.Στη συνέχεια, για κάθε απόσταση, αν είναι μικρότερη από$\kappa$, τότε απαιτείται μια λειτουργία κίνησης και ο αριθμός των κινήσεων είναι $\kappa$ Η διαφορά από αυτή την απόσταση.

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

Η χρονική πολυπλοκότητα είναι ${\rm O}(t\mathrm{\iota \delta oύ\sigma o\lambda }t)$, η πολυπλοκότητα του χώρου είναι ${\rm O}(1)$。

Κώδικας αναφοράς

• Πύθων

t = int(input())

for _ in range(t):
    n, k, *a = map(int, input().split())
    a.sort()

    if k * 3 > n:
        print(-1)
        continue

    b = [a[1] - a[0], a[2] - a[1], n - a[2] + a[0]]
    ans = sum(max(0, k - d) for d in b)

    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• Ιάβα

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] a = new int[3];
            for (int i = 0; i < 3; i++) {
                a[i] = sc.nextInt();
            }

            Arrays.sort(a);

            if (k * 3 > n) {
                System.out.println(-1);
                continue;
            }

            int[] b = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
            int ans = 0;
            for (int d : b) {
                ans += Math.max(0, k - d);
            }

            System.out.println(ans);
        }
    }
}
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

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k, a[3];
        cin >> n >> k >> a[0] >> a[1] >> a[2];

        sort(a, a + 3);

        if (k * 3 > n) {
            cout << -1 << endl;
            continue;
        }

        int b[] = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
        int ans = 0;
        for (int d : b) {
            ans += max(0, k - d);
        }

        cout << ans << 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

🪐 02.卢小姐的音游金币

Περιγραφή Προβλήματος

Η κυρία Lu πρόσφατα εθίστηκε σε ένα μουσικό παιχνίδι που επικεντρώνεται στους ήχους του πιάνου.Στο παιχνίδι, κάθε πλακίδιο πιάνου έχει έναν αριθμό, με τον ελάχιστο αριθμό να είναι$1$ . Αν χτυπήσετε πέντε πλακίδια πιάνου με αυξανόμενους αριθμούς στη σειρά, θα πάρετε ένα χρυσό νόμισμα.

Για παράδειγμα, αν η Miss Lu χτυπήσει τον αριθμημένο 1, 2, 3, 4, 5, 6 κομμάτια πιάνου, μετά για1, 2, 3, 4, 5 Για αυτά τα πέντε μπλοκ με διαδοχικούς αυξανόμενους αριθμούς, θα πάρει ένα χρυσό νόμισμα.

Όταν ένα επίπεδο έχει προχωρήσει για μεγάλο χρονικό διάστημα, ο αριθμός θα μηδενιστεί Ο αριθμός επαναφοράς θα αλλάξει από $1$ αρχή. Έτσι, για ένα επίπεδο, είναι δυνατό να χτυπήσετε πολλά πλακίδια πιάνου με τον ίδιο αριθμό αλλά διαφορετικά.

Σημειώστε ότι μόνο πέντε πλακίδια πιάνου με συνεχώς αυξανόμενους αριθμούς στο ίδιο επίπεδο απαιτούνται για την απόκτηση χρυσών νομισμάτων.

Λόγω της ανώτερης δύναμης της Miss Lu, έχει περάσει τέσσερα επίπεδα.Η Miss Lu έχει πλέον τέσσερα επίπεδα δυσκολίας${\rm E}{\rm N}{\rm A}$、$\sigma \iota$、$\nu \tau o$ και$\rho \epsilon$ Αριθμός του χτυπήματος πλακιδίων για πιάνο Πόσα χρυσά νομίσματα μπορεί να πάρει η κυρία Lu συνολικά σε αυτά τα τέσσερα επίπεδα;

Μορφή εισαγωγής

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο $n$（$1\le n\le 10^5$), που αντιπροσωπεύει τον συνολικό αριθμό των πλακιδίων πιάνου που χτύπησε η Miss Lu στα τέσσερα επίπεδα.

Επόμενο $n$ γραμμές, εισαγάγετε τρεις παραμέτρους σε κάθε γραμμή:${έ\nu \alpha }_{{\rm E}\gamma ώ}$、${\sigma \iota }_{{\rm E}\gamma ώ}$（$1\le {έ\nu \alpha }_{{\rm E}\gamma ώ},{\sigma \iota }_{{\rm E}\gamma ώ}\le 10^9$)και ${\nu \tau o}_{{\rm E}\gamma ώ}$（ ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i σε {'A', 'B', 'C', 'D'}ντοΕγώ​∈{′ΕΝΑ′,′σι′,′ντο′,′ρε′}), αντιπροσωπεύοντας αντίστοιχα τον αριθμό, την ποσότητα και το επίπεδο κάθε πλακιδίου πιάνου.

Μορφή εξόδου

Δώστε έναν ακέραιο αριθμό που αντιπροσωπεύει τον συνολικό αριθμό των χρυσών νομισμάτων που μπορεί να αποκτήσει η Miss Lu.

Δείγμα εισαγωγής

11
1 1 A
2 2 A
3 2 A
4 2 A
5 2 A
6 1 A
7 1 B
8 2 B
9 2 B
10 2 B
11 1 B
1
2
3
4
5
6
7
8
9
10
11
12

Δείγμα εξόδου

3
1

Δείγμα περιγραφής

Για επίπεδα ${\rm E}{\rm N}{\rm A}$,πρώτα 1, 2, 3, 4, 5 Μπορείτε να πάρετε ένα χρυσό νόμισμα και μετά2, 3, 4, 5, 6 Μπορείτε να πάρετε ένα άλλο χρυσό νόμισμα.

Για επίπεδα $\sigma \iota$，7, 8, 9, 10, 11 Μπορείτε να πάρετε ένα χρυσό νόμισμα.

Επομένως, συνολικά $3$ χρυσά νομίσματα.

Δείγμα εισαγωγής 2

5
1 1 C
2 2 C
3 2 C 
4 2 C
6 1 C
1
2
3
4
5
6

Δείγμα εξόδου 2

0
1

Περιγραφή δείγματος 2

στο επίπεδο $\nu \tau o$ Σε , δεν μπορούν να ληφθούν πέντε διαδοχικοί αυξανόμενοι αριθμοί, επομένως ο αριθμός των χρυσών νομισμάτων είναι$0$。

φασμα ΔΕΔΟΜΕΝΩΝ

• $1\le n\le 10^5$
• $1\le {έ\nu \alpha }_{{\rm E}\gamma ώ},{\sigma \iota }_{{\rm E}\gamma ώ}\le 10^9$
• ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i σε {'A', 'B', 'C', 'D'}ντοΕγώ​∈{′ΕΝΑ′,′σι′,′ντο′,′ρε′}

απάντηση

Αυτό το πρόβλημα μπορεί να λυθεί χρησιμοποιώντας πίνακες κατακερματισμού και ταξινόμηση. Οι συγκεκριμένες ιδέες είναι οι εξής:

1. Χρησιμοποιήστε τον πίνακα κατακερματισμού cnt Καταγράψτε πόσες φορές εμφανίζεται κάθε αριθμός σε κάθε επίπεδο. Το κλειδί είναι ο συνδυασμός του χαρακτήρα επιπέδου και του αριθμού και η τιμή είναι ο αριθμός των φορών που εμφανίζεται ο αριθμός στο επίπεδο.

2. Ταξινομήστε τα δεδομένα εισόδου σύμφωνα με τους χαρακτήρες και τους αριθμούς επιπέδου για να βεβαιωθείτε ότι οι αριθμοί του ίδιου επιπέδου είναι διαδοχικοί.

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

4. Η τελική απάντηση είναι το άθροισμα όλων των χρυσών νομισμάτων που πληρούν τις προϋποθέσεις.

Η χρονική πολυπλοκότητα είναι ${\rm O}(n\mathrm{\iota \delta oύ\sigma o\lambda }n)$, η πολυπλοκότητα του χώρου είναι ${\rm O}(n)$。

Κώδικας αναφοράς

• Πύθων

from collections import defaultdict
import sys

def solve():
    n = int(input())
    cnt = defaultdict(int)
    vec = []

    for _ in range(n):
        a, b, c = input().split()
        a, b = int(a), int(b)
        cnt[c + str(a)] += b
        vec.append((c, a))

    vec.sort()

    ans = 0
    for v in vec:
        arr = [v[0] + str(v[1] + i) for i in range(5)]
        t = min(cnt[a] for a in arr)
        ans += t
        for a in arr:
            cnt[a] -= t

    print(ans)

if __name__ == '__main__':
    solve()
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

• Ιάβα

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Map<String, Integer> cnt = new HashMap<>();
        List<int[]> vec = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            String c = input[2];
            String key = c + a;
            cnt.put(key, cnt.getOrDefault(key, 0) + b);
            vec.add(new int[]{c.charAt(0), a});
        }

        vec.sort((x, y) -> {
            if (x[0] != y[0]) {
                return x[0] - y[0];
            }
            return x[1] - y[1];
        });

        long ans = 0;
        for (int[] v : vec) {
            String[] arr = new String[5];
            for (int i = 0; i < 5; i++) {
                arr[i] = (char) v[0] + String.valueOf(v[1] + i);
            }
            int t = Integer.MAX_VALUE;
            for (String a : arr) {
                t = Math.min(t, cnt.getOrDefault(a, 0));
            }
            ans += t;
            for (String a : arr) {
                cnt.put(a, cnt.get(a) - t);
            }
        }

        System.out.println(ans);
    }
}
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
37
38
39
40
41
42
43
44
45
46
47

• Cpp

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    map<string, ll> cnt;
    vector<pair<string, int>> vec;

    for (int i = 1; i <= n; i++) {
        int a, b;
        string c;
        cin >> a >> b >> c;
        cnt[c + to_string(a)] += b;
        vec.push_back({c, a});
    }

    sort(vec.begin(), vec.end());

    ll ans = 0;
    for (auto& v : vec) {
        vector<string> arr;
        for (int i = 0; i < 5; i++) {
            arr.push_back(v.first + to_string(v.second + i));
        }
        ll t = LLONG_MAX;
        for (auto& a : arr) {
            t = min(t, cnt[a]);
        }
        ans += t;
        for (auto& a : arr) {
            cnt[a] -= t;
        }
    }

    cout << ans << 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
34
35
36
37
38
39
40
41
42
43
44
45

✨ 03. Ο μοναδικός κήπος της Miss Lu

Περιγραφή Προβλήματος

Η δεσποινίς Λου έχει μήκος $n$ σε έναν κήπο φυτεμένο με$n$ Φυτέψτε διαφορετικά λουλούδια.Κάθε λουλούδι έχει μια αξία ομορφιάς${έ\nu \alpha }_{{\rm E}\gamma ώ}$。

Η κυρία Λου νιώθει ότι ένας όμορφος κήπος πρέπει να είναι μοναδικός, έχει δηλαδή $n-1$ Η αξία ομορφιάς των φυτεμένων λουλουδιών είναι η ίδια, μόνο$1$ Η αξία ομορφιάς των φυτεμένων λουλουδιών είναι διαφορετική από άλλα λουλούδια.

Για κάθε επέμβαση, η Miss Lu μπορεί να επιλέξει ένα λουλούδι και να αυξήσει την ομορφιά του. $1$ ή πλην$1$。

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

Μορφή εισαγωγής

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο $n$, υποδεικνύοντας το μήκος του κήπου.

Η δεύτερη γραμμή περιέχει $n$ θετικός ακέραιος${έ\nu \alpha }_1,{έ\nu \alpha }_2,\dots ,{έ\nu \alpha }_n$, υποδεικνύοντας την αξία ομορφιάς κάθε λουλουδιού.

Μορφή εξόδου

Εξάγει έναν ακέραιο που αντιπροσωπεύει τον ελάχιστο αριθμό πράξεων που απαιτούνται για να γίνει ο κήπος μοναδικός.

Δείγμα εισαγωγής

4
1 2 3 4
1
2

Δείγμα εξόδου

2
1

φασμα ΔΕΔΟΜΕΝΩΝ

• $1\le n\le 10^5$
• $1\le {έ\nu \alpha }_{{\rm E}\gamma ώ}\le 10^9$

απάντηση

Η βέλτιστη λύση είναι να γίνετε ο διάμεσος και να απαριθμήσετε όλα τα κόστη για να γίνετε διάμεσος.

Η χρονική πολυπλοκότητα είναι ${\rm O}(n\mathrm{\iota \delta oύ\sigma o\lambda }n)$, η πολυπλοκότητα του χώρου είναι ${\rm O}(n)$。

Κώδικας αναφοράς

• Πύθων

def main():
    n = int(input())
    w = list(map(int, input().split()))
    w.sort()
    if w[0] == w[n - 1]:
        print("1")
        return
    s1, s2 = 0, 0
    m1, m2 = w[(n - 1) // 2], w[(n + 1) // 2]
    for i in range(n - 1):
        s1 += abs(m1 - w[i])
    for i in range(1, n):
        s2 += abs(m2 - w[i])
    print(min(s1, s2))

if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• Ιάβα

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++)
            w[i] = scanner.nextInt();
        Arrays.sort(w);
        if (w[0] == w[n - 1]) {
            System.out.println("1");
            return;
        }
        long s1 = 0, s2 = 0;
        int m1 = w[(n - 1) / 2], m2 = w[(n + 1) / 2];
        for (int i = 0; i < n - 1; i++)
            s1 += Math.abs(m1 - w[i]);
        for (int i = 1; i < n; i++)
            s2 += Math.abs(m2 - w[i]);
        System.out.println(Math.min(s1, s2));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 100010;

int main() {
    int n, w[N];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];
    sort(w, w + n);
    if (w[0] == w[n - 1]) {
        cout << "1" << endl;
        return 0;
    }
    ll s1 = 0, s2 = 0;
    int m1 = w[(n - 1) / 2], m2 = w[(n + 1) / 2];
    for (int i = 0; i < n - 1; i++)
        s1 += abs(m1 - w[i]);
    for (int i = 1; i < n; i++)
        s2 += abs(m2 - w[i]);
    cout << min(s1, s2) << 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

🥝 04.LYA的字符画

Περιγραφή ερώτησης

Η LYA έχει αποκτήσει πρόσφατα εμμονή με τη ζωγραφική χαρακτήρων. Πιστεύει ότι η ομορφιά μιας ζωγραφικής χαρακτήρων είναι ίση με τον αριθμό των διαδοχικών πανομοιότυπων συμβόλων στη ζωγραφική των χαρακτήρων.Για παράδειγμα, η αισθητική της ζωγραφικής του χαρακτήρα «aabbccddef» είναι$6$。

Ο φίλος της LYA της έδωσε ένα $0$ και$1$ Η LYA, που έχει γίνει εμμονή με το σχέδιο χαρακτήρων, θέλει να μάθει όλες τις χορδές που αποτελούνται από αυτή τη χορδή.υποσυμβολοσειράΠοιο είναι το άθροισμα της αισθητικής;

Σημείωση: Υπάρχουν ${\nu \tau o}_{n+1}^2$ υποσυμβολοσειρά.

Μορφή εισαγωγής

Εισαγάγετε έναν θετικό ακέραιο αριθμό στην πρώτη γραμμή $n$, υποδεικνύοντας το μήκος της χορδής.

Το μήκος της δεύτερης γραμμής είναι $n$ του$01$ Σειρά.

Μορφή εξόδου

Εξαγωγή ακέραιου αριθμού που αντιπροσωπεύει το άθροισμα της αισθητικής όλων των υποσυμβολοσειρών.

Δείγμα εισαγωγής

4
0011
1
2

Δείγμα εξόδου

14
1

φασμα ΔΕΔΟΜΕΝΩΝ

$1\le n\le 2\times 10^5$

απάντηση

Αυτό το πρόβλημα μπορεί να λυθεί μέσω της ιδέας του αθροίσματος του προθέματος.

Αρχικά, μπορούμε να υπολογίσουμε τον συνολικό αριθμό των υποσυμβολοσειρών της συμβολοσειράς, δηλαδή $\frac{n(n+1)}{2}$。

Στη συνέχεια, επαναλαμβάνουμε τη συμβολοσειρά και χρησιμοποιούμε τις μεταβλητές $\mu \epsilon \gamma ά\lambda o$ Καταγράψτε την αρχική θέση των τρεχόντων διαδοχικών πανομοιότυπων συμβόλων, μεταβλητή$r$ Καταγράψτε την τρέχουσα τοποθεσία.πότε$\mu \iota \kappa \rho ό[r]\ne \mu \iota \kappa \rho ό[r-1]$ Όταν , σημαίνει ότι εμφανίζεται ένα νέο σύμβολο και μπορούμε να υπολογίσουμε$[\mu \epsilon \gamma ά\lambda o,r)$ Ο αριθμός των υποσυμβολοσειρών στο διάστημα, δηλαδή$\frac{(r-\mu \epsilon \gamma ά\lambda o)(r-\mu \epsilon \gamma ά\lambda o+1)}{2}$, αφαιρέστε το από τον συνολικό αριθμό των υποσυμβολοσειρών.

Τέλος, αυτό που απομένει είναι ο αριθμός όλων των όμορφων υποσυμβολοσειρών, που μπορούν να βγουν.

χρονική πολυπλοκότητα ${\rm O}(n)$, πολυπλοκότητα χώρου ${\rm O}(1)$。

Κώδικας αναφοράς

• Πύθων

def cal(length):
    return length * (length + 1) // 2

n = int(input())
s = input() + '#'

ans = 0
total = cal(n)
l = 0
for r in range(1, n + 1):
    if s[r] != s[r - 1]:
        ans += total - cal(l) - cal(n - r)
        l = r

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• Ιάβα

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next() + "#";
        
        long ans = 0;
        long total = cal(n);
        int l = 0;
        for (int r = 1; r <= n; r++) {
            if (s.charAt(r) != s.charAt(r - 1)) {
                ans += total - cal(l) - cal(n - r);
                l = r;
            }
        }
        System.out.println(ans);
    }
    
    private static long cal(int len) {
        return (long) len * (len + 1) / 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• Cpp

#include <iostream>
#include <string>

using namespace std;

using ll = long long;

ll cal(int len) {
    return (ll) len * (len + 1) / 2;
}

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s += "#";
    
    ll ans = 0;
    ll total = cal(n);
    int l = 0;
    for (int r = 1; r <= n; r++) {
        if (s[r] != s[r - 1]) {
            ans += total - cal(l) - cal(n - r);
            l = r;
        }
    }
    cout << ans << 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

🌸 05.卢小姐的数组删除计划

Όνομα ερώτησης

Περιγραφή Προβλήματος

Η Miss Lu έχει ένα πολύ μεγάλο σχέδιο, θέλει να διαγράψει όλες τις συστοιχίες στον κόσμο! Αλλά η ικανότητά της είναι περιορισμένη. Μπορεί να επιλέξει μόνο δύο πανομοιότυπα στοιχεία στον πίνακα κάθε φορά και να διαγράψει όλα τα στοιχεία μεταξύ τους (συμπεριλαμβανομένων των ίδιων των δύο στοιχείων).

Τώρα, μπροστά από τη δεσποινίς Λου, υπάρχει ένα μήκος του $n$ συστοιχία από$έ\nu \alpha$, θέλει να μάθει πόσα στοιχεία σε αυτόν τον πίνακα μπορεί να διαγράψει το πολύ.

Μορφή εισαγωγής

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο $n$, αντιπροσωπεύει έναν πίνακα $έ\nu \alpha$ μήκος.

Η δεύτερη γραμμή περιέχει $n$ θετικοί ακέραιοι χωρισμένοι με χώρο${έ\nu \alpha }_1,{έ\nu \alpha }_2,\dots ,{έ\nu \alpha }_n$, αντιπροσωπεύει έναν πίνακα $έ\nu \alpha$ Στοιχεία.

Μορφή εξόδου

Καταχωρίστε έναν ακέραιο αριθμό, υποδεικνύοντας τον μέγιστο αριθμό στοιχείων που μπορεί να διαγράψει η Miss Lu.

Δείγμα εισαγωγής

4
1 2 1 2
1
2

Δείγμα εξόδου

1
1

φασμα ΔΕΔΟΜΕΝΩΝ

• $1\le n\le 2\times 10^5$
• $1\le {έ\nu \alpha }_{{\rm E}\gamma ώ}\le 10^9$

απάντηση

Αυτό το πρόβλημα μπορεί να λυθεί χρησιμοποιώντας τις ιδέες της ταξινόμησης και των διπλών δεικτών.

Αρχικά, μπορούμε να μετατρέψουμε τον πίνακα $έ\nu \alpha$ Τα στοιχεία σε ταξινομούνται κατά τιμή και καταγράφεται η αρχική θέση κάθε στοιχείου στον πίνακα. Ο σκοπός αυτού είναι να μας διευκολύνει να βρούμε το εύρος θέσης του ίδιου στοιχείου.

Στη συνέχεια, μπορούμε να επαναλάβουμε τον ταξινομημένο πίνακα και, για κάθε στοιχείο, να βρούμε το εύρος θέσης όλων των στοιχείων που έχουν την ίδια τιμή με αυτό $[\mu \epsilon \gamma ά\lambda o,R]$ . Τα στοιχεία σε αυτό το εύρος μπορούν να διαγραφούν επειδή βρίσκονται ανάμεσα σε δύο πανομοιότυπα στοιχεία στον αρχικό πίνακα.Μπορούμε να υπολογίσουμε το εύρος$[\mu \epsilon \gamma ά\lambda o,R]$ Ο αριθμός των στοιχείων σε$R-\mu \epsilon \gamma ά\lambda o-1$, συγκρίνετε το με τον τρέχοντα μέγιστο αριθμό διαγραμμένων στοιχείων και ενημερώστε τη μέγιστη τιμή.

Τέλος, εξάγετε τον μέγιστο αριθμό διαγραμμένων στοιχείων.

Η χρονική πολυπλοκότητα είναι ${\rm O}(n\mathrm{\iota \delta oύ\sigma o\lambda }n)$ , κυρίως η χρονική πολυπλοκότητα της διαλογής.Η πολυπλοκότητα του χώρου είναι${\rm O}(n)$, χρησιμοποιείται για την αποθήκευση της αρχικής θέσης του στοιχείου.

Κώδικας αναφοράς

• Πύθων

n = int(input())
a = list(map(int, input().split()))

idx = sorted(range(n), key=lambda x: a[x])

ans = 0
i = 0
while i < n:
    j = i
    L, R = n, -1
    while j < n and a[idx[j]] == a[idx[i]]:
        L = min(L, idx[j])
        R = max(R, idx[j])
        j += 1
    ans = max(ans, R - L - 1)
    i = j

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• Ιάβα

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            idx[i] = i;
        }

        Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));

        int ans = 0;
        for (int i = 0; i < n;) {
            int j = i;
            int L = n, R = -1;
            while (j < n && a[idx[j]] == a[idx[i]]) {
                L = Math.min(L, idx[j]);
                R = Math.max(R, idx[j]);
                j++;
            }
            ans = Math.max(ans, R - L - 1);
            i = j;
        }

        System.out.println(ans);
    }
}
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

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> idx(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        idx[i] = i;
    }

    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return a[i] < a[j];
    });

    int ans = 0;
    for (int i = 0; i < n;) {
        int j = i;
        int L = n, R = -1;
        while (j < n && a[idx[j]] == a[idx[i]]) {
            L = min(L, idx[j]);
            R = max(R, idx[j]);
            j++;
        }
        ans = max(ans, R - L - 1);
        i = j;
    }

    cout << ans << 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
34
35
36
37
38

γράψε στο τέλος

Εδώ θα ήθελα να σας προτείνω τη φθινοπωρινή καμπίνα στρατολόγησης των ηλικιωμένων για το check-in.

🎧 秋招陪伴刷题打卡

• Δοκιμαστική ανάγνωση:

[Autumn Recruitment Check-in] Day01-Customized Sorting-CSDN Blog

[Autumn Recruitment Check-in] Day02-The Strongest Two-Section Series-Binary Search-CSDN Blog

[Autumn Recruitment Check-in] Day03-The Stronest Two-Point Series-Two-Point Answer-CSDN Blog

Παρέχουμε online κριτικές πραγματικών ερωτήσεων από προηγούμενους μεγάλους κατασκευαστές Οι ενδιαφερόμενοι φίλοι μπορούν να στείλουν ένα ιδιωτικό μήνυμα στην Qinglong για να μάθουν περισσότερα.

Και άλλα! εκτός!

✈️ Μια περιεκτική περίληψη των γραπτών ερωτήσεων του τεστ