Berbagi teknologi

[Terobosan Perekrutan Musim Gugur] Tes Tertulis Rekrutmen Musim Gugur 2024-Soal Tes Tertulis ByteDance-01-Solusi Pertanyaan Tiga Bahasa (Java/Cpp/Python)

2024-07-12

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

🍭 大家好这里是Kiyotaka-senpai , seorang programmer yang menyukai algoritma

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

✨ Seri ini rencananya akan terus diupdate Soal tes tertulis Qiuzhao
👏 感谢大家的订阅➕ 和 喜欢💗


📧 清隆这边最近正在收集近一年半互联网笔试题汇总,有需要的小伙伴可以关注 Akhir artikel Dapatkan pelayaran putri~

Masukkan deskripsi gambar di sini

🎀 01.A先生的环形花圃

Deskripsi pertanyaan

Pak A mempunyai petak bunga berbentuk lingkaran yang terbagi menjadi tidak adaN daerah blok. Awalnya Pak A memilih tiga area di petak bunga untuk ditanami bunga mawar.

Sekarang Pak A ingin menggunakan operasi keliling untuk menjangkau taman bungaKeadaan seimbang

Keadaan seimbang: Jarak antara dua areal yang ditanami bunga mawar tidak kurang dari kkaaaaaakuuuuuu(Jarak antara daerah yang berdekatan adalah 1 1 1)。

Operasi pemindahan: menukar status area yang berdekatan (area mawar menjadi area kosong, area kosong menjadi area mawar).

Di saat yang sama, Pak A adalah orang yang sangat memperhatikan efisiensi, sehingga ia berharap dapat menggunakan jumlah gerakan yang minimal agar hamparan bunga mencapai keadaan seimbang.

Masukkan format

Masukkan bilangan bulat positif pada baris pertama tidak adaT, menunjukkan jumlah pertanyaan.

Berikutnya tidak adaT baris, setiap baris berisi lima bilangan bulat positif tidak adaN kkaaaaaakuuuuuu sebuah 1 a_1A1 sebuah 2 a_2A2 sebuah 3 a_3A3, masing-masing mewakili jumlah area hamparan bunga, jarak minimum yang diperlukan, dan posisi awal ketiga area mawar.

Format output

keluaran tidak adaT garis, masing-masing menghasilkan bilangan bulat yang mewakili jumlah minimum pertukaran yang diperlukan untuk membawa petak bunga ke keseimbangan.Jika keseimbangan tidak dapat dicapai, keluarkan − 1 -1 1

Contoh masukan

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

Contoh keluaran

0
-1
1
  • 1
  • 2
  • 3

rentang data

1 ≤ t ≤ 1 0 4 1 kiri t kiri 10^41T104
1 ≤ n ≤ 1 0 9 1 pangkat n pangkat 10^91N109
1 ≤ k, a1, a2, a3 ≤ n 1 koefisien k, a_1, a_2, a_3 koefisien n1aaaaaakuuuuuu,A1,A2,A3N

menjawab

Masalah ini dapat diselesaikan dengan menganalisis kondisi keseimbangan.

Pertama, jika diperlukan jarak minimum kkaaaaaakuuuuuu Melebihi jumlah area taman tidak adaN sepertiga dari , maka kondisinya tidak dapat dipenuhi dalam hal apa pun, dan hasilnya adalah − 1 -1 1

Jika tidak, kita bisa mengurutkan terlebih dahulu posisi ketiga area mawar tersebut lalu menghitung jarak antar area mawar yang berdekatan.Selanjutnya, untuk setiap jarak, jika kurang dari kkaaaaaakuuuuuu, maka diperlukan operasi pergerakan, dan jumlah pergerakannya adalah kkaaaaaakuuuuuu Perbedaan dari jarak ini.

Akhirnya, ketika semua jarak memenuhi persyaratan, hamparan bunga mencapai keadaan seimbang, dan jumlah total gerakan dapat dihasilkan.

Kompleksitas waktunya adalah Bahasa Indonesia: O(log t ⁡ t ) O(log t)HAI(TlihatGT), kompleksitas ruangnya adalah O ( 1 ) O(1)HAI(1)

Kode referensi

  • Ular piton
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
  • Jawa
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.卢小姐的音游金币

Deskripsi Masalah

Lu baru-baru ini menjadi kecanduan permainan musik yang berfokus pada suara piano.Dalam permainan, setiap ubin piano memiliki nomor, dengan jumlah minimumnya adalah 1 1 1 . Jika Anda menekan lima ubin piano dengan angka yang semakin meningkat secara berturut-turut, Anda akan mendapatkan koin emas.

Misalnya, jika Nona Lu berhasil menekan nomor tersebut 1, 2, 3, 4, 5, 6 potongan piano, lalu untuk1, 2, 3, 4, 5 Untuk lima blok dengan angka yang meningkat berturut-turut, dia akan mendapatkan koin emas.

Ketika suatu level telah dimainkan dalam waktu yang lama, nomor tersebut akan direset. Nomor reset akan berubah 1 1 1 awal. Jadi untuk suatu level, dimungkinkan untuk memukul beberapa ubin piano dengan nomor yang sama tetapi berbeda.

Perhatikan bahwa hanya diperlukan lima ubin piano dengan angka yang terus meningkat di level yang sama untuk mendapatkan koin emas.

Karena kekuatan Nona Lu yang unggul, dia telah melewati empat level.Nona Lu sekarang diberikan empat tingkat kesulitan A AA BBB Bahasa InggrisC Dan DDD Jumlah ubin piano yang dipukul. Berapa total koin emas yang dapat diperoleh Nona Lu dalam empat level ini?

Masukkan format

Baris pertama berisi bilangan bulat positif tidak adaN 1 ≤ n ≤ 1 0 5 1 pangkat n pangkat 10^51N105), mewakili jumlah total ubin piano yang dipukul oleh Nona Lu dalam empat level.

Berikutnya tidak adaN baris, masukkan tiga parameter di setiap baris: ai a_iASaya bi b_iBSaya 1 ≤ ai, bi ≤ 1 0 9 1 sifat a_i, b_i sifat 10^91ASaya,BSaya109)Dan ci c_iCSaya ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i dalam {'A', 'B', 'C', 'D'}CSaya{A,B,C,D}), masing-masing mewakili jumlah, kuantitas, dan level setiap ubin piano.

Format output

Keluarkan bilangan bulat yang mewakili jumlah total koin emas yang dapat diperoleh Nona Lu.

Contoh masukan

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

Contoh keluaran

3
  • 1

Deskripsi sampel

Untuk level A AA,Pertama 1, 2, 3, 4, 5 Anda bisa mendapatkan koin emas, dan kemudian2, 3, 4, 5, 6 Anda bisa mendapatkan koin emas lainnya.

Untuk level BBB7, 8, 9, 10, 11 Anda bisa mendapatkan koin emas.

Oleh karena itu, totalnya adalah 3 3 3 koin emas.

Contoh masukan 2

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

Contoh keluaran 2

0
  • 1

Contoh Deskripsi 2

di tingkat Bahasa InggrisC Dalam , lima angka yang bertambah berturut-turut tidak dapat diperoleh, jadi jumlah koin emasnya adalah 0 0 0

rentang data

  • 1 ≤ n ≤ 1 0 5 1 pangkat n pangkat 10^51N105
  • 1 ≤ ai, bi ≤ 1 0 9 1 sifat a_i, b_i sifat 10^91ASaya,BSaya109
  • ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i dalam {'A', 'B', 'C', 'D'}CSaya{A,B,C,D}

menjawab

Masalah ini dapat diselesaikan dengan menggunakan tabel hash dan pengurutan. Ide spesifiknya adalah sebagai berikut:

  1. Gunakan tabel hash cnt Catat berapa kali setiap angka muncul di setiap level. Kuncinya adalah kombinasi karakter level dan angka, dan nilainya adalah berapa kali angka tersebut muncul di level tersebut.

  2. Urutkan data masukan menurut karakter level dan angka untuk memastikan bahwa angka pada level yang sama berurutan.

  3. Telusuri data yang diurutkan, dan untuk setiap angka, tentukan apakah lima angka berurutannya semuanya ada di level saat ini. Jika ada, ambillah nilai minimum banyaknya kemunculan di antara kelima angka tersebut, hitunglah dalam jawaban, dan kurangi nilai minimum dari banyaknya kemunculan kelima angka tersebut.

  4. Jawaban akhirnya adalah jumlah seluruh koin emas yang memenuhi syarat.

Kompleksitas waktunya adalah Bahasa Indonesia: O(n log ⁡ n) O(n log n)HAI(NlihatGN), kompleksitas ruangnya adalah Tidak adaHAI(N)

Kode referensi

  • Ular piton
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
  • Jawa
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. Taman unik Nona Lu

Deskripsi Masalah

Nona Lu panjangnya tidak adaN di taman yang ditanami tidak adaN Tanam bunga yang berbeda.Setiap bunga mempunyai nilai keindahan ai a_iASaya

Lu merasa bahwa taman yang indah haruslah unik n-1 n-1N1 Nilai keindahan bunga yang ditanam sama saja, hanya saja 1 1 1 Nilai keindahan bunga yang ditanam berbeda dengan bunga lainnya.

Untuk setiap operasi, Nona Lu dapat memilih bunga dan meningkatkan nilai keindahannya. 1 1 1 atau dikurangi 1 1 1

Sekarang, Nona Lu ingin mengetahui berapa banyak operasi yang diperlukan untuk membuat taman tersebut menjadi unik.

Masukkan format

Baris pertama berisi bilangan bulat positif tidak adaN, menunjukkan panjang taman.

Baris kedua berisi tidak adaN bilangan bulat positif sebuah 1 , sebuah 2 , … , sebuah a_1, a_2, ldots, sebuah_nA1,A2,,AN, menunjukkan nilai keindahan setiap bunga.

Format output

Menghasilkan bilangan bulat yang mewakili jumlah minimum operasi yang diperlukan untuk membuat taman menjadi unik.

Contoh masukan

4
1 2 3 4
  • 1
  • 2

Contoh keluaran

2
  • 1

rentang data

  • 1 ≤ n ≤ 1 0 5 1 pangkat n pangkat 10^51N105
  • 1 ≤ ai ≤ 1 0 9 1 sifat a_i sifat 10^91ASaya109

menjawab

Solusi optimalnya adalah dengan menjadi median dan menghitung semua biaya untuk menjadi median.

Kompleksitas waktunya adalah Bahasa Indonesia: O(n log ⁡ n) O(n log n)HAI(NlihatGN), kompleksitas ruangnya adalah Tidak adaHAI(N)

Kode referensi

  • Ular piton
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
  • Jawa
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的字符画

Deskripsi pertanyaan

LYA akhir-akhir ini terobsesi dengan lukisan karakter. Ia percaya bahwa keindahan lukisan karakter setara dengan banyaknya simbol identik yang berurutan dalam lukisan karakter.Misalnya saja estetika lukisan karakter “aabbccddef” tersebut 6 6 6

Teman LYA memberinya a 0 0 0 Dan 1 1 1 LYA yang terobsesi dengan gambar karakter ingin mengetahui semua string yang terbuat dari string ini.substringBerapa jumlah estetikanya?

Catatan: Ada Persamaan kuadrat dari n+1 dan n+2 adalah 2,5.CN+12 substring.

Masukkan format

Masukkan bilangan bulat positif pada baris pertama tidak adaN, menunjukkan panjang string.

Panjang baris kedua adalah tidak adaN dari 01 01 01 rangkaian.

Format output

Keluarkan bilangan bulat yang mewakili jumlah estetika semua substring.

Contoh masukan

4
0011
  • 1
  • 2

Contoh keluaran

14
  • 1

rentang data

1 ≤ n ≤ 2 × 1 0 5 1 kelipatan n kelipatan 2 kali 10^51N2×105

menjawab

Masalah ini dapat diselesaikan melalui gagasan jumlah awalan.

Pertama, kita dapat menghitung jumlah total substring dari string tersebut n ( n + 1 ) 2 pecahan{n(n+1)}{2}2N(N+1)

Kemudian, kami mengulangi string dan menggunakan variabel IIaku Catat posisi awal dari simbol-simbol identik yang berurutan saat ini, variabel rrR Rekam lokasi saat ini.Kapan s [ r ] ≠ s [ r − 1 ] s[r] neq s[r-1]S[R]=S[R1] Bila , berarti muncul simbol baru dan bisa kita hitung [ kiri, kanan ) [ kiri, kanan )[aku,R) Jumlah substring dalam interval, yaitu ( r − l ) ( r − l + 1 ) 2 pecahan{(rl)(r-l+1)}{2}2(Raku)(Raku+1), kurangi dari jumlah total substring.

Terakhir, yang tersisa adalah jumlah semua substring indah yang dapat dihasilkan.

kompleksitas waktu Tidak adaHAI(N), kompleksitas ruang O ( 1 ) O(1)HAI(1)

Kode referensi

  • Ular piton
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
  • Jawa
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.卢小姐的数组删除计划

Nama pertanyaan

Deskripsi Masalah

Nona Lu mempunyai rencana yang sangat besar, dia ingin menghapus semua susunan di dunia! Namun kemampuannya terbatas. Dia hanya dapat memilih dua elemen identik dalam array setiap kali dan menghapus semua elemen di antara keduanya (termasuk dua elemen itu sendiri).

Sekarang, di depan Nona Lu, ada panjang tidak adaN susunan dari A AA, dia ingin tahu berapa banyak elemen dalam array ini yang dapat dia hapus paling banyak.

Masukkan format

Baris pertama berisi bilangan bulat positif tidak adaN, mewakili sebuah array A AA panjang.

Baris kedua berisi tidak adaN bilangan bulat positif yang dipisahkan spasi sebuah 1 , sebuah 2 , … , sebuah a_1, a_2, ldots, sebuah_nA1,A2,,AN, mewakili sebuah array A AA Elemen.

Format output

Keluarkan bilangan bulat, yang menunjukkan jumlah maksimum elemen yang dapat dihapus oleh Nona Lu.

Contoh masukan

4
1 2 1 2
  • 1
  • 2

Contoh keluaran

1
  • 1

rentang data

  • 1 ≤ n ≤ 2 × 1 0 5 1 kelipatan n kelipatan 2 kali 10^51N2×105
  • 1 ≤ ai ≤ 1 0 9 1 sifat a_i sifat 10^91ASaya109

menjawab

Masalah ini dapat diselesaikan dengan menggunakan ide pengurutan dan penunjuk ganda.

Pertama, kita dapat mengonversi array A AA Elemen-elemen di dalamnya diurutkan berdasarkan nilai, dan posisi asli setiap elemen dalam array dicatat. Tujuannya adalah untuk memudahkan kita mencari kisaran posisi elemen yang sama.

Selanjutnya, kita dapat mengulangi array yang diurutkan dan, untuk setiap elemen, menemukan rentang posisi semua elemen yang memiliki nilai yang sama. [ Kiri, Kanan ] [Kiri, Kanan][Saya,R] . Elemen dalam rentang ini dapat dihapus karena terletak di antara dua elemen identik dalam larik asli.Kita bisa menghitung jangkauannya [ Kiri, Kanan ] [Kiri, Kanan][Saya,R] Jumlah elemen di R - L - 1 R - L - 1RSaya1, bandingkan dengan jumlah maksimum elemen yang dihapus saat ini, dan perbarui nilai maksimum.

Terakhir, tampilkan jumlah maksimum elemen yang dihapus.

Kompleksitas waktunya adalah Bahasa Indonesia: O(n log ⁡ n) O(n log n)HAI(NlihatGN) , terutama kompleksitas waktu penyortiran.Kompleksitas ruangnya adalah Tidak adaHAI(N), digunakan untuk menyimpan posisi asli elemen.

Kode referensi

  • Ular piton
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
  • Jawa
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

tulis di akhir

Di sini saya ingin merekomendasikan kepada Anda kabin check-in pendampingan rekrutmen musim gugur untuk siswa senior. Ini akan memandu Anda langkah demi langkah dalam menyelesaikan soal tes tertulis Internet umum dalam 31 hari.

🎧 秋招陪伴刷题打卡

  • Pembacaan percobaan:

[Check-in Perekrutan Musim Gugur] Blog CSDN Penyortiran Khusus Hari01

[Check-in Rekrutmen Musim Gugur] Day02-Seri Dua Bagian Terkuat-Pencarian Biner-Blog CSDN

[Check-in Rekrutmen Musim Gugur] Hari03-Seri Dua Poin Terkuat-Jawaban Dua Poin-Blog CSDN

Kami memberikan ulasan online atas pertanyaan nyata dari produsen besar sebelumnya. Teman yang tertarik dapat mengirim pesan pribadi ke Qinglong untuk mempelajari lebih lanjut.

Masukkan deskripsi gambar di sini

Masukkan deskripsi gambar di sini

Dan banyak lagi! di samping itu!

✈️ Ringkasan lengkap soal tes tertulis

Masukkan deskripsi gambar di sini
Masukkan deskripsi gambar di sini
Masukkan deskripsi gambar di sini