Technology sharing

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

🍭 大家好这里是Kiyotaka-senpai , programmator qui algorithmos amat

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

Haec series consilia pergere ad update Qiuzhao scriptum test quaestionum
👏 感谢大家的订阅➕ 和 喜欢💗

---

📧 清隆这边最近正在收集近一年半互联网笔试题汇总，有需要的小伙伴可以关注 Articulus finis Get princeps lecythus ~

🎀 01.A先生的环形花圃

Quaeritur descriptio

Mr. A floris circularis habet, qui dividitur in $n$ angustos aream. Initio, D. A selectis tribus locis in lecto flore ad rosas plantandas.

Nunc, Mr. A rebus mobilibus uti vult ut hortum floris attingatlibratum statum。

Status libratus: Distantia inter binas areas rosis consita non minus est quam $k$(Quod spatium inter vicinis locis est $1$）。

Movere operationem: commutare statum regionum adiacentium (area rosa fit area vacua, area vacua fit area rosa).

Eodem tempore, Dominus A homo est qui magnam operam ad efficientiam attendit, ita sperat se uti posse minimum numerum motuum ad aequilibrium floris stratum pervenire.

Input format

Intrant integer positivus in prima acie $t$indicans numerum quaestionum.

deinde $t$ lineae, unaquaeque linea quinque integros positivos continet$n$、$k$、$a_1$、$a_2$、$a_3$respective repraesentans numerum arearum floris lecti, minimam distantiam requisitam, et situm initialem trium arearum rosarum.

Output format

output $t$ lineae, singulae extrahentes integrum repraesentantes minimum numerum commutationum quae ad aequilibrium floris stratum deducendi sunt.Si aequilibrium attingi non potest, output$-1$。

Sample input

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

Sample output

0
-1
1
1
2
3

data range

$1\le t\le 10^4$
$1\le n\le 10^9$
$1\le k,a_1,a_2,a_3\le n$

respondere

Haec quaestio solvi potest aequilibrii condiciones enucleando.

Primum, si minimum spatium requiratur $k$ Excessit numerus arearum hortus$n$ ex tertia parte, quacumque conditione satiari non potest, et hoc tempore output$-1$。

Alioquin possumus primum modum positiones trium arearum rosarum, et deinde distantiam inter rosae adjacentes computare.Deinde pro qualibet distantia, si minor est$k$ergo motus requiritur operatio, et numerus motuum $k$ Differentia ab hoc intervallo.

Denique, omnibus spatiis requisitis, florem stratum aequabiliter attingit, et numerus motus output esse potest.

Tempus complexionem O (t log ⁡ t) O (t log t)O**********(tlog****t), spatium complexionis est $O**********(1)$。

Reference Code

• Python

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

• Java

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

Problema Description

Ms Lu nuper deditus est venationi musicae quae in sonis piano versatur.In ludo, quilibet tile piano numerum habet, cum minimus numerus$1$ . Si quinque tegulas piano percusseris numero crescente in ordine, nummum aureum habebis.

Exempli gratia, si Miss Lu percusserit numeratum 1, 2, 3, 4, 5, 6 de piano pieces, deinde for1, 2, 3, 4, 5 Pro his quinque cuneos numero continuo crescente, nummum aureum habebit.

Cum in gradu diu profecerit, numerus reset erit $1$ initium. Ita pro gradu, possibile est plures pianos tegulas totidem, sed differentes ferire.

Nota quod quinque tantum tegulae piano cum continue crescentes numero in eodem gradu, ad obtinendum nummos aureos requiruntur.

Ob vim superiorem Miss Lu, quattuor gradus transiit.Nunc quattuor gradus difficultas Miss Lu$A$、$B$、$C$ et$D$ Numerus telearum piano ictus.

Input format

Prima linea integrum positivum continet $n$（$1\le n\le 10^5$) numerum tegularum piano repraesentatum Miss Lu in quattuor gradibus percussum esse.

deinde $n$ lineae, in quavis linea parametri tres intrant;$a_{ego}$、$b_{ego}$（$1\le a_{ego},b_{ego}\le 10^9$)et ${c***}_{ego}$（ ci { A , B , C , D } c_i in {'A', 'B', 'C', 'D'}c***ego​∈{′A′,′B′,′C′,′D′}) respective repraesentans numerum, quantitatem et gradum cujusvis laterculi piano.

Output format

Output integer repraesentans numerum nummorum aureorum qui Miss Lu obtinere potest.

Sample input

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

Sample output

3
1

Sample description

Nam gradus $A$,primis 1, 2, 3, 4, 5 Accipere potes nummum aureum, et inde2, 3, 4, 5, 6 Accipere potes alium nummum aureum.

Nam gradus $B$，7, 8, 9, 10, 11 Accipere potes nummum aureum.

Ergo summa $3$ nummos aureos.

Sample initus 2

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

Sample output 2

0
1

Sample Description 2

in plano $C$ In numero quinque continuos crescentes obtineri non possunt, numerus aureorum nummorum est$0$。

data range

• $1\le n\le 10^5$
• $1\le a_{ego},b_{ego}\le 10^9$
• ci { A , B , C , D } c_i in {'A', 'B', 'C', 'D'}c***ego​∈{′A′,′B′,′C′,′D′}

respondere

Hoc problema solvi potest utens Nullam tabularum et voluptua. Ideae speciales sunt hae:

1. Nullam mensam usus cnt Numerum in utroque gradu notare singulis vicibus apparet. Clavis est compositum ex aequo charactere et numero, et valor pluries numerus apparet in gradu.

2. Inputatio data secundum ordinem personarum et numerorum dispone ut numeri aequaliter consecuti sint.

3. Datas digesta percurre et pro quolibet numero, utrum quinque continuos numeri eius omnes in gradu currenti existant. Si existit, sume valorem minimum numeri eventuum in his quinque numeris, in responsione computa, et minue valorem minimum ex numero eventuum horum quinque numerorum.

4. Postrema responsio est summa omnium nummorum aureorum quae condiciones conveniant.

Tempus complexionem O (n log n) O (n log n)O**********(nlog****n), spatium complexionis est $O**********(n)$。

Reference Code

• Python

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

• Java

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's unicum hortum

Problema Description

Miss Lu habet longitudinem $n$ in horto plantatum$n$ Flores diversorum plantarum.Omnis flos habet pulchritudinem pretii$a_{ego}$。

Ms. Lu sentit hortum pulchrum esse unicum, id est, habet $n-1$ Valor florum plantatorum eadem est pulchritudo, solum$1$ Pulchritudo valoris florum plantatorum ab aliis floribus differt.

Pro qualibet operatione, Miss Lu eligere potest florem et auget valorem pulchritudinis. $1$ aut minus$1$。

Nunc, Ms. Lu scire vult quot operationes ad hortum unicum opus sunt.

Input format

Prima linea integrum positivum continet $n$horti longitudinem indicans.

Secunda linea continet $n$ integer positive$a_1,a_2,\dots ,a_n$indicans pulcritudinem valoris uniuscuiusque floris.

Output format

Outputs integer repraesentans numerum minimum operationum quae ad hortum singularem faciendam requiritur.

Sample input

4
1 2 3 4
1
2

Sample output

2
1

data range

• $1\le n\le 10^5$
• $1\le a_{ego}\le 10^9$

respondere

Optima solutio est media fieri et omnes sumptus mediani fieri.

Tempus complexionem O (n log n) O (n log n)O**********(nlog****n), spatium complexionis est $O**********(n)$。

Reference Code

• Python

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

• Java

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的字符画

Quaeritur descriptio

LYA nuper factus est in pictura characteris obsessus. Credet pulchritudinem picturae characteris aequalem esse numero continuorum identicorum symbolorum in pictura characteris.Pro exemplo, pictura aesthetica characteris "aabbccddef" is$6$。

LYA est amicus ei a $0$ et$1$ LYA, qui charactere tractus obsessus factus est, omnes chordas ex hoc chorda scire cupit.substringQuae summa est aestheticorum?

Nota: Sunt $C_{n+1}^2$ substring.

Input format

Intrant integer positivus in prima acie $n$chordae longitudinem indicans.

Longitudo secundae lineae est $n$ of*$01$ chorda.

Output format

Output integrum repraesentans summam aestheticorum omnium chordarum.

Sample input

4
0011
1
2

Sample output

14
1

data range

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

respondere

Hoc problema per notionem summae praepositionis solvi potest.

Primum computare numerum nervorum chordarum, id est $\frac{n(n+1)}{2}$。

Deinde per chordas iteramus et variabiles utimur $l$ Initium notare positionis hodiernae continuos symbola identica, variabilis$r******$ Locus monetae record.quando$s[r******]\ne s[r******-1]$ Quando, significat novum symbolum apparere et computare$[l,r******)$ Substringorum in intervallo numerus, id est$\frac{(r******-l)(r******-l+1)}{2}$detrahe de numero substringorum.

Postremo, quod reliquum est, omnium colorum chordarum numerus est, qui output esse possunt.

tempus complexionem $O**********(n)$, spatium complexionem $O**********(1)$。

Reference Code

• Python

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

• Java

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

Quaestio nomen

Problema Description

Miss Lu maximum consilium habet, omnes vestes in mundo delere vult! Sed facultas eius limitata est. Non potest tantum eligere duo elementa identica in ordine quovis tempore et omnia elementa inter ea delere (inclusa ipsa duo elementa).

Nunc in conspectu Miss Lu, longitudo est $n$ ordinata of *$a$, scire cupit quot elementa in hoc ordine ad summum delere possit.

Input format

Prima linea integrum positivum continet $n$Repraesentet aciem $a$ longitudo.

Secunda linea continet $n$ spatio-separata positiva integris$a_1,a_2,\dots ,a_n$Repraesentet aciem $a$ Elementa.

Output format

Output integrum, indicans numerum maximum elementorum quae Miss Lu delere potest.

Sample input

4
1 2 1 2
1
2

Sample output

1
1

data range

• $1\le n\le 2\times 10^5$
• $1\le a_{ego}\le 10^9$

respondere

Hoc problema solvi potest utentes notiones voluptua et duplices indicibus.

Primo potest converti aciem $a$ Elementa in pretio digessae sunt, et prima cuiusque elementi in ordine positio traditur. Hoc propositum est faciliorem nobis locum invenire eiusdem elementi amplitudinem.

Deinde iterari possumus per ordinatim ordinatum et, pro unoquoque elemento, invenire positionem omnium elementorum quae idem valent. $[L,R]$ . Elementa in hoc ambitu deleri possunt quia inter duo elementa identica in originali ordinata sita sunt.Ponere range$[L,R]$ Numerus elementorum in$R-L-1$compara cum maximo currenti numero elementorum deletorum et renovate valorem maximum.

Postremo numerus maximus elementorum delevit output.

Tempus complexionem O (n log n) O (n log n)O**********(nlog****n) maxime tempore intricata voluptua.De spatio multiplicitate$O**********(n)$adsuevit pristinum locum elementi reponere.

Reference Code

• Python

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

• Java

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

scribe in fine

Hic tibi commendare velim socium cooptationes autumnales senioris in casula reprehendo. Gradatim ad solvendas quaestiones communes interretiales scriptas in 31 diebus per singulos dies erit.

🎧 秋招陪伴刷题打卡

• Lectio iudicii:

[Autumn Recruiting Reprehendo-in] Day01-Customized Sorting-CSDN Blog

[Autumn Recruiting Check-in] Day02-Fortissima Duo Sectio Series binarii Quaerere-CSDN Blog

[Autumn Recruiting Reprehendo-in] Day03-Fortissimum Duo-Point Series Duo-Point Answer-CSDN Blog

Recognitiones realium quaestionum ex prioribus maioribus fabricatoribus praebemus. Amici interest, nuntium privatum mittere ad Qinglong ut plura discere possint.

Et plus! praeterea!

A comprehensive summary of written test questions