2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
🍭 大家好这里是Kiyotaka-senpai , un programmeur qui aime les algorithmes
💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导
✨ Cette série prévoit de continuer à se mettre à jour Questions du test écrit Qiuzhao
👏 感谢大家的订阅➕ 和 喜欢💗
📧 清隆这边最近正在收集近一年半互联网笔试题汇总，有需要的小伙伴可以关注 Fin de l'article Obtenez la croisière princesse ~
M. A possède un parterre de fleurs circulaire, divisé en nnn zone de bloc. Initialement, M. A a sélectionné trois zones du parterre de fleurs pour planter des roses.
Désormais, M. A souhaite utiliser les opérations mobiles pour rendre le jardin fleuri accessibleÉtat équilibré。
État d'équilibre : La distance entre deux zones plantées de roses n'est pas inférieure à kk(La distance entre les zones adjacentes est 1 1 1）。
Opération de déplacement : échangez le statut des zones adjacentes (la zone rose devient une zone vide, la zone vide devient une zone rose).
Dans le même temps, M. A est une personne qui accorde une grande attention à l'efficacité, il espère donc que vous pourrez utiliser le nombre minimum de mouvements pour que le parterre de fleurs atteigne un état d'équilibre.
Entrez un entier positif dans la première ligne ttt, indiquant le nombre de demandes.
Suivant ttt lignes, chaque ligne contient cinq entiers positifs nnn、 kk、 un 1 a_1un1、 un 2 a_2un2、 un 3 a_3un3, représentant respectivement le nombre de zones de parterres de fleurs, la distance minimale requise et la position initiale des trois zones de rosiers.
sortir ttt lignes, chacune produisant un entier représentant le nombre minimum d'échanges nécessaires pour amener le parterre de fleurs à l'équilibre.Si l’équilibre ne peut être atteint, la production − 1 -1 −1。
3
5 1 1 2 3
5 2 1 2 3
6 2 2 3 6
0
-1
1
1 ≤ t ≤ 1 0 4 1 leq t leq 10^41≤t≤104
1 ≤ n ≤ 1 0 9 1 leq n leq 10^91≤n≤109
1 ≤ k , a 1 , a 2 , a 3 ≤ n 1 leq k, a_1, a_2, a_3 leq n1≤k,un1,un2,un3≤n
Ce problème peut être résolu en analysant les conditions d’équilibre.
Premièrement, si la distance minimale requise kk Dépassé le nombre de zones de jardin nnn un tiers de , alors la condition ne peut pas être satisfaite quoi qu'il arrive, et à ce moment la sortie − 1 -1 −1。
Sinon, nous pouvons d’abord trier les positions des trois zones de roses, puis calculer la distance entre les zones de roses adjacentes.Ensuite, pour chaque distance, si elle est inférieure à kk, alors une opération de mouvement est requise, et le nombre de mouvements est kk La différence de cette distance.
Enfin, lorsque toutes les distances répondent aux exigences, le parterre de fleurs atteint un état équilibré et le nombre total de mouvements peut être émis.
La complexité temporelle est O ( t log t ) O(t log t)O(tlogt), la complexité spatiale est O ( 1 ) O(1)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)
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);
}
}
}
#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;
}
Mme Lu est récemment devenue accro à un jeu musical axé sur les sons du piano.Dans le jeu, chaque tuile piano possède un numéro, le nombre minimum étant 1 1 1 . Si vous frappez cinq tuiles de piano avec des nombres croissants d'affilée, vous obtiendrez une pièce d'or.
Par exemple, si Miss Lu atteint le numéro 1, 2, 3, 4, 5, 6 de pièces pour piano, puis pour1, 2, 3, 4, 5 Pour ces cinq blocs aux nombres croissants consécutifs, elle recevra une pièce d’or.
Lorsqu'un niveau a progressé pendant une longue période, le numéro sera réinitialisé. Le numéro de réinitialisation changera de. 1 1 1 commencer. Ainsi pour un niveau, il est possible de toucher plusieurs tuiles piano portant le même numéro mais différentes.
Notez que seules cinq tuiles piano avec des nombres en constante augmentation dans le même niveau sont nécessaires pour obtenir des pièces d'or.
En raison de la force supérieure de Miss Lu, elle a passé quatre niveaux.Miss Lu dispose désormais de quatre niveaux de difficulté AAUN、 BBB、 CCC et DDD Nombre de tuiles de piano touchées. Combien de pièces d'or Mme Lu peut-elle obtenir au total dans ces quatre niveaux ?
La première ligne contient un entier positif nnn（ 1 ≤ n ≤ 1 0 5 1 leq n leq 10^51≤n≤105), représentant le nombre total de tuiles de piano touchées par Miss Lu dans les quatre niveaux.
Suivant nnn lignes, saisissez trois paramètres dans chaque ligne : ai a_iunje、 bi b_ibje（ 1 ≤ ai , bi ≤ 1 0 9 1 leq a_i, b_i leq 10^91≤unje,bje≤109)et ci c_icje（ ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i dans {'A', 'B', 'C', 'D'}cje∈{′UN′,′B′,′C′,′D′}), représentant respectivement le nombre, la quantité et le niveau de chaque tuile piano.
Affichez un nombre entier représentant le nombre total de pièces d'or que Miss Lu peut obtenir.
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
3
Pour les niveaux AAUN,d'abord 1, 2, 3, 4, 5 Vous pouvez obtenir une pièce d'or, et ensuite2, 3, 4, 5, 6 Vous pouvez obtenir une autre pièce d'or.
Pour les niveaux BBB，7, 8, 9, 10, 11 Vous pouvez obtenir une pièce d'or.
Par conséquent, un total de 3 3 3 pièces d'or.
5
1 1 C
2 2 C
3 2 C
4 2 C
6 1 C
0
au niveau CCC En , cinq nombres croissants consécutifs ne peuvent pas être obtenus, le nombre de pièces d'or est donc 0 0 0。
Ce problème peut être résolu en utilisant des tables de hachage et du tri. Les idées spécifiques sont les suivantes :
Utiliser une table de hachage cnt Enregistrez le nombre de fois où chaque numéro apparaît dans chaque niveau. La clé est la combinaison du caractère du niveau et du nombre, et la valeur est le nombre de fois que le nombre apparaît dans le niveau.
Triez les données d'entrée en fonction des caractères et des nombres de niveau pour vous assurer que les nombres du même niveau sont consécutifs.
Parcourez les données triées et, pour chaque nombre, déterminez si ses cinq nombres consécutifs existent tous dans le niveau actuel. S'il existe, prenez la valeur minimale du nombre d'occurrences parmi ces cinq nombres, comptez-la dans la réponse, et soustrayez la valeur minimale du nombre d'occurrences de ces cinq nombres.
La réponse finale est la somme de toutes les pièces d’or qui remplissent les conditions.
La complexité temporelle est O ( n log n ) O(n log n)O(nlogn), la complexité spatiale est O ( n ) O(n)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()
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);
}
}
#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;
}
Miss Lu a une longueur de nnn dans un jardin planté de nnn Plantez différentes fleurs.Chaque fleur a une valeur de beauté ai a_iunje。
Mme Lu estime qu'un beau jardin doit être unique, c'est-à-dire qu'il a n − 1 n-1n−1 La valeur beauté des fleurs plantées est la même, seulement 1 1 1 La valeur beauté des fleurs plantées est différente de celle des autres fleurs.
Pour chaque opération, Miss Lu peut choisir une fleur et augmenter sa valeur beauté. 1 1 1 ou moins 1 1 1。
Maintenant, Mme Lu veut savoir combien d’opérations sont nécessaires pour rendre le jardin unique.
La première ligne contient un entier positif nnn, indiquant la longueur du jardin.
La deuxième ligne contient nnn entier positif un 1 , un 2 , … , un a_1, a_2, ldots, a_nun1,un2,…,unn, indiquant la valeur beauté de chaque fleur.
Génère un entier représentant le nombre minimum d’opérations requises pour rendre le jardin unique.
4
1 2 3 4
2
La solution optimale consiste à devenir la médiane et à énumérer tous les coûts liés à ce statut.
La complexité temporelle est O ( n log n ) O(n log n)O(nlogn), la complexité spatiale est O ( n ) O(n)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()
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));
}
}
#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;
}
LYA est récemment devenue obsédée par la peinture de personnages. Elle croit que la beauté d'une peinture de personnages est égale au nombre de symboles identiques consécutifs dans la peinture de personnages.Par exemple, l'esthétique de la peinture du personnage « aabbccddef » est 6 6 6。
L'amie de LYA lui a donné un 0 0 0 et 1 1 1 LYA, devenue obsédée par le dessin de personnages, souhaite connaître toutes les cordes composées de cette corde.sous-chaîneQuelle est la somme de l’esthétique ?
Remarque : il existe C n + 1 2 C^{2}_{n+1}Cn+12 sous-chaîne.
Entrez un entier positif dans la première ligne nnn, indiquant la longueur de la chaîne.
La longueur de la deuxième ligne est nnn de 01 01 01 Chaîne.
Génère un entier représentant la somme de l’esthétique de toutes les sous-chaînes.
4
0011
14
1 ≤ n ≤ 2 × 1 0 5 1 leq n leq 2 fois 10^51≤n≤2×105
Ce problème peut être résolu grâce à l'idée de somme de préfixes.
Tout d’abord, nous pouvons calculer le nombre total de sous-chaînes de la chaîne, c’est-à-dire n ( n + 1 ) 2 frac{n(n+1)}{2}2n(n+1)。
Ensuite, nous parcourons la chaîne et utilisons les variables lll Enregistrez la position de départ des symboles identiques consécutifs actuels, variable rrl Enregistrez l'emplacement actuel.quand s [ r ] ≠ s [ r − 1 ] s[r] neq s[r-1]m[l]=m[l−1] Quand , cela signifie qu'un nouveau symbole apparaît, et on peut calculer [ g , d ) [ g , d )[l,l) Le nombre de sous-chaînes dans l'intervalle, c'est-à-dire ( r − l ) ( r − l + 1 ) 2 frac{(rl)(r-l+1)}{2}2(l−l)(l−l+1), soustrayez-le du nombre total de sous-chaînes.
Enfin, ce qui reste est le nombre de toutes les belles sous-chaînes qui peuvent être sorties.
complexité temporelle O ( n ) O(n)O(n), complexité spatiale O ( 1 ) O(1)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)
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;
}
}
#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;
}
Miss Lu a un très grand projet, elle veut supprimer toutes les baies du monde ! Mais sa capacité est limitée. Elle ne peut sélectionner à chaque fois que deux éléments identiques dans le tableau et supprimer tous les éléments entre eux (y compris les deux éléments eux-mêmes).
Maintenant, devant Miss Lu, il y a une longueur de nnn tableau de aaun, elle veut savoir combien d'éléments de ce tableau elle peut supprimer au maximum.
La première ligne contient un entier positif nnn, représente un tableau aaun longueur.
La deuxième ligne contient nnn entiers positifs séparés par des espaces un 1 , un 2 , … , un a_1, a_2, ldots, a_nun1,un2,…,unn, représente un tableau aaun Éléments.
Affiche un entier, indiquant le nombre maximum d'éléments que Miss Lu peut supprimer.
4
1 2 1 2
1
Ce problème peut être résolu en utilisant les idées de tri et de doubles pointeurs.
Tout d'abord, nous pouvons convertir le tableau aaun Les éléments sont triés par valeur et la position d'origine de chaque élément dans le tableau est enregistrée. Le but de ceci est de nous faciliter la recherche de la plage de positions du même élément.
Ensuite, nous pouvons parcourir le tableau trié et, pour chaque élément, trouver la plage de positions de tous les éléments qui ont la même valeur que lui. [ G , D ] [ G , D ][L,R] . Les éléments de cette plage peuvent être supprimés car ils sont situés entre deux éléments identiques dans le tableau d'origine.Nous pouvons calculer la portée [ G , D ] [ G , D ][L,R] Le nombre d'éléments dans R − G − 1 R - G - 1R−L−1, comparez-le avec le nombre maximum actuel d'éléments supprimés et mettez à jour la valeur maximale.
Enfin, affichez le nombre maximum d’éléments supprimés.
La complexité temporelle est O ( n log n ) O(n log n)O(nlogn) , principalement la complexité temporelle du tri.La complexité spatiale est O ( n ) O(n)O(n), utilisé pour stocker la position d'origine de l'élément.
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)
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);
}
}
#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;
}
Ici, je voudrais vous recommander la cabine d'enregistrement des compagnons de recrutement d'automne pour les seniors. Elle vous guidera étape par étape pour résoudre les questions courantes des tests écrits sur Internet en 31 jours. Chaque jour regorge d'informations utiles.
[Enregistrement du recrutement d'automne] Jour 01 - Tri personnalisé - Blog CSDN
Nous fournissons des critiques en ligne de vraies questions des principaux fabricants précédents. Les amis intéressés peuvent envoyer un message privé à Qinglong pour en savoir plus.
Et plus encore ! Et plus encore ! en plus!
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
