내 연락처 정보
우편메소피아@프로톤메일.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
🍭 大家好这里是키요타카 선배 , 알고리즘을 사랑하는 프로그래머
💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导
✨ 이 시리즈는 계속 업데이트 예정입니다 Qiuzhao 필기 시험 문제
👏 感谢大家的订阅➕ 和 喜欢💗
📧 清隆这边最近正在收集近一年半互联网笔试题汇总，有需要的小伙伴可以关注 기사 끝 프린세스 크루즈 타세요~
A씨는 원형 화단을 갖고 있는데, 화단은 다음과 같이 나누어져 있다. 엔N 블록 영역. A씨는 당초 화단 내 3곳을 선정해 장미를 심었다.
이제 A씨는 모바일 조작을 이용해 꽃밭을 손에 넣으려고 합니다.균형 잡힌 상태。
균형 상태: 장미를 심은 두 영역 사이의 거리는 다음보다 작지 않습니다. kk케이(인접한 지역 사이의 거리는 1 1 1）。
이동 동작: 인접 영역의 상태를 교환합니다. (장미 영역은 빈 영역으로, 빈 영역은 장미 영역으로)
동시에 A씨는 효율성을 크게 중시하는 사람이기 때문에 최소한의 이동 횟수를 활용해 화단이 균형 잡힌 상태에 도달할 수 있기를 바란다.
첫 번째 줄에 양의 정수를 입력하세요. 티티티, 문의 건수를 나타냅니다.
다음 티티티 줄, 각 줄에는 5개의 양의 정수가 포함됩니다. 엔N、 kk케이、 아 1 아_1ㅏ1、 아 2 아_2ㅏ2、 아 3 아_3ㅏ3는 각각 화단 면적 수, 필요한 최소 거리 및 3개 장미 면적의 초기 위치를 나타냅니다.
산출 티티티 각 라인은 화단을 평형 상태로 만드는 데 필요한 최소 교환 횟수를 나타내는 정수를 출력합니다.평형에 도달하지 못하면 출력 − 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 렉티 렉티 10^41≤티≤104
1 ≤ n ≤ 1 0 9 1 렉 n 렉 10^91≤N≤109
1 ≤ k, a 1, a 2, a 3 ≤ n 1 1/k, a_1, a_2, a_3 1/n1≤케이,ㅏ1,ㅏ2,ㅏ3≤N
이 문제는 평형상태를 분석함으로써 해결될 수 있다.
첫째, 필요한 최소 거리가 있는 경우 kk케이 정원 면적을 초과했습니다. 엔N 의 1/3이면 무슨 일이 있어도 조건을 만족할 수 없으며 이때 출력은 − 1 -1 −1。
그렇지 않으면 먼저 세 개의 장미 영역의 위치를 정렬한 다음 인접한 장미 영역 사이의 거리를 계산할 수 있습니다.다음으로, 각 거리에 대해 다음보다 작은 경우 kk케이, 이동 작업이 필요하며 이동 횟수는 kk케이 이 거리의 차이.
마지막으로 모든 거리가 요구 사항을 충족하면 화단이 균형 잡힌 상태에 도달하고 총 이동 횟수가 출력될 수 있습니다.
시간복잡도는 O ( t 로그 t ) O( t 로그 t )영형(티봐라g티), 공간 복잡도는 오(1)오(1)영형(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;
}
루 씨는 최근 피아노 소리에 초점을 맞춘 음악 게임에 중독되었습니다.게임에서 각 피아노 타일에는 숫자가 있으며, 최소 숫자는 다음과 같습니다. 1 1 1 . 연속해서 숫자가 증가하는 5개의 피아노 타일을 치면 금화를 얻게 됩니다.
예를 들어, Miss Lu가 숫자를 쳤다면 1, 2, 3, 4, 5, 6 피아노 곡, 그 다음에는1, 2, 3, 4, 5 숫자가 연속적으로 증가하는 이 5개의 블록에 대해 그녀는 금화를 받게 됩니다.
장기간 레벨을 진행하면 숫자가 재설정됩니다. 1 1 1 시작. 따라서 한 레벨에서는 숫자는 같지만 숫자가 다른 여러 피아노 타일을 칠 수 있습니다.
같은 레벨에서 숫자가 계속 증가하는 피아노 타일 5개만 있으면 금화를 얻을 수 있습니다.
루 선생님의 뛰어난 힘으로 인해 그녀는 4단계를 통과했습니다.Miss Lu에게는 이제 4가지 난이도가 주어집니다. 금주 모임ㅏ、 비비비、 참조씨 그리고 디.디.디 피아노 타일에 닿은 횟수 루 씨는 이 4개 레벨에서 총 몇 개의 금화를 얻을 수 있나요?
첫 번째 줄에는 양의 정수가 포함되어 있습니다. 엔N（ 1 ≤ n ≤ 1 0 5 1 렉 n 렉 10^51≤N≤105)는 Miss Lu가 4개 레벨에서 친 피아노 타일의 총 개수를 나타냅니다.
다음 엔N 행의 경우 각 행에 세 개의 매개변수를 입력합니다. 아이 아이_아이ㅏ나、 비 비_이비나（ 1 ≤ ai, bi ≤ 1 0 9 1 1/2 a_i, b_i 1/2 10^91≤ㅏ나,비나≤109)그리고 씨 씨_이씨나（ {'A', 'B', 'C', 'D'}에 있는 c_i씨나∈{′ㅏ′,′비′,′씨′,′디′})는 각각 각 피아노 타일의 수, 수량 및 레벨을 나타냅니다.
미스 루가 얻을 수 있는 금화의 총 개수를 나타내는 정수를 출력하세요.
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
레벨의 경우 금주 모임ㅏ,첫 번째 1, 2, 3, 4, 5 금화를 얻을 수 있고,2, 3, 4, 5, 6 또 다른 금화를 얻을 수 있습니다.
레벨의 경우 비비비，7, 8, 9, 10, 11 금화를 얻을 수 있습니다.
따라서 총 3 3 3 금화.
5
1 1 C
2 2 C
3 2 C
4 2 C
6 1 C
0
수준에서 참조씨 에서는 5개의 연속 증가하는 숫자를 얻을 수 없으므로 금화의 개수는 0 0 0。
이 문제는 해시 테이블과 정렬을 사용하여 해결할 수 있습니다. 구체적인 아이디어는 다음과 같습니다.
해시 테이블 사용 cnt 각 레벨에서 각 숫자가 나타나는 횟수를 기록하십시오. 키는 레벨 캐릭터와 숫자의 조합이고, 값은 레벨에 숫자가 나타나는 횟수입니다.
동일한 레벨의 숫자가 연속되도록 레벨 문자 및 숫자에 따라 입력 데이터를 정렬합니다.
정렬된 데이터를 탐색하고 각 숫자에 대해 5개의 연속 숫자가 모두 현재 수준에 존재하는지 확인합니다. 존재하는 경우, 이 5개 숫자 중 발생 횟수의 최소값을 취하여 답에 세고, 이 5개 숫자의 발생 횟수에서 최소값을 뺍니다.
최종 답은 조건을 만족하는 모든 금화의 합입니다.
시간복잡도는 O(n log n) O(n log n)영형(N봐라gN), 공간 복잡도는 O(n) O(n)영형(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의 길이는 다음과 같습니다. 엔N 식물이 심어진 정원에서 엔N 다양한 꽃을 심으세요.모든 꽃에는 아름다움의 가치가 있습니다 아이 아이_아이ㅏ나。
Lu 씨는 아름다운 정원은 독특해야 한다고 생각합니다. n − 1 n-1N−1 심은 꽃의 아름다움의 가치는 동일하지만 1 1 1 심은 꽃의 아름다움의 가치는 다른 꽃과 다릅니다.
각 작업마다 루 선생님은 꽃을 선택하고 그 아름다움의 가치를 높일 수 있습니다. 1 1 1 또는 마이너스 1 1 1。
이제 Lu 씨는 정원을 독특하게 만들기 위해 얼마나 많은 작업이 필요한지 알고 싶어합니다.
첫 번째 줄에는 양의 정수가 포함되어 있습니다. 엔N, 정원의 길이를 나타냅니다.
두 번째 줄에는 다음이 포함됩니다. 엔N 양의 정수 a 1 , a 2 , … , a_1, a_2, ldots, a_nㅏ1,ㅏ2,…,ㅏN, 각 꽃의 아름다움 가치를 나타냅니다.
정원을 고유하게 만드는 데 필요한 최소 작업 수를 나타내는 정수를 출력합니다.
4
1 2 3 4
2
최적의 해법은 중앙값이 되어 중앙값이 되기 위한 모든 비용을 열거하는 것입니다.
시간복잡도는 O(n log n) O(n log n)영형(N봐라gN), 공간 복잡도는 O(n) O(n)영형(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는 최근 캐릭터 페인팅에 푹 빠졌습니다. 그녀는 캐릭터 그림의 아름다움은 캐릭터 그림에 연속된 동일한 기호의 수와 같다고 믿습니다.예를 들어, 캐릭터 그림 "aabbccddef"의 미학은 다음과 같습니다. 6 6 6。
LYA의 친구가 그녀에게 0 0 0 그리고 1 1 1 캐릭터 그리기에 푹 빠진 LYA는 이 끈으로 이루어진 모든 끈을 알고 싶어 합니다.하위 문자열미학의 총합은 무엇입니까?
참고: 있습니다. Cn + 1 2 C^{2}_{n+1}씨N+12 하위 문자열.
첫 번째 줄에 양의 정수를 입력하세요. 엔N, 문자열의 길이를 나타냅니다.
두 번째 줄의 길이는 엔N ~의 01 01 01 끈.
모든 하위 문자열의 미학의 합을 나타내는 정수를 출력합니다.
4
0011
14
1 ≤ n ≤ 2 × 1 0 5 1 leq n leq 2 곱하기 10^51≤N≤2×105
이 문제는 접두사 합이라는 아이디어를 통해 해결될 수 있습니다.
먼저, 문자열의 전체 하위 문자열 수를 계산할 수 있습니다. n ( n + 1 ) 2 분수 {n ( n + 1 )}{2}2N(N+1)。
그런 다음 문자열을 반복하고 변수를 사용합니다. 나는엘 현재 연속된 동일 기호의 시작 위치를 기록, 변수 르르르아르 자형 현재 위치를 기록합니다.언제 s [ r ] ≠ s [ r − 1 ] s[r] neq s[r-1]에스[아르 자형]=에스[아르 자형−1] 이면 새로운 기호가 나타나는 것을 의미하며 다음을 계산할 수 있습니다. [ l , r ) [ l , r )[엘,아르 자형) 간격의 하위 문자열 수, 즉 ( r − l ) ( r − l + 1 ) 2 프랙{(rl)(r-l+1)}{2}2(아르 자형−엘)(아르 자형−엘+1), 전체 하위 문자열 수에서 이를 뺍니다.
마지막으로 남은 것은 출력할 수 있는 모든 아름다운 하위 문자열의 수입니다.
시간 복잡도 O(n) O(n)영형(N), 공간 복잡도 오(1)오(1)영형(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는 매우 원대한 계획을 가지고 있습니다. 그녀는 세상의 모든 어레이를 삭제하고 싶어합니다! 그러나 그녀의 능력은 제한되어 있습니다. 매번 배열에서 동일한 요소 두 개만 선택하고 그 사이의 모든 요소(두 요소 자체 포함)를 삭제할 수 있습니다.
이제 Miss Lu 앞에는 엔N 의 배열 아아ㅏ, 그녀는 이 배열에서 최대 몇 개의 요소를 삭제할 수 있는지 알고 싶어합니다.
첫 번째 줄에는 양의 정수가 포함되어 있습니다. 엔N, 배열을 나타냅니다 아아ㅏ 길이.
두 번째 줄에는 다음이 포함됩니다. 엔N 공백으로 구분된 양의 정수 a 1 , a 2 , … , a_1, a_2, ldots, a_nㅏ1,ㅏ2,…,ㅏN, 배열을 나타냅니다 아아ㅏ 강요.
Miss Lu가 삭제할 수 있는 최대 요소 수를 나타내는 정수를 출력합니다.
4
1 2 1 2
1
이 문제는 정렬과 이중 포인터 아이디어를 사용하여 해결할 수 있습니다.
먼저 배열을 변환할 수 있습니다. 아아ㅏ 의 요소는 값을 기준으로 정렬되고 배열에 있는 각 요소의 원래 위치가 기록됩니다. 이것의 목적은 동일한 요소의 위치 범위를 쉽게 찾는 것입니다.
다음으로, 정렬된 배열을 반복하고 각 요소에 대해 동일한 값을 갖는 모든 요소의 위치 범위를 찾을 수 있습니다. [좌,우] [좌,우][엘,아르 자형] . 이 범위의 요소는 원래 배열의 동일한 두 요소 사이에 있으므로 삭제할 수 있습니다.범위를 계산할 수 있습니다. [좌,우] [좌,우][엘,아르 자형] 의 요소 수 R − L − 1 R - L - 1아르 자형−엘−1, 현재 삭제된 요소의 최대 개수와 비교하여 최대값을 업데이트합니다.
마지막으로 삭제된 요소의 최대 개수를 출력합니다.
시간복잡도는 O(n log n) O(n log n)영형(N봐라gN) , 주로 정렬의 시간 복잡도입니다.공간 복잡도는 O(n) O(n)영형(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)
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;
}
여기에서는 선배의 가을 모집 동반자 체크인 캐빈을 추천하고 싶습니다. 매일 31 일 동안 일반적인 인터넷 필기 시험 문제를 풀 수 있도록 단계별로 안내해 드리겠습니다.
[가을 모집 체크인] Day01-맞춤정렬-CSDN 블로그
[가을 모집 체크인] Day02 - 최강 2부 시리즈 - 바이너리 검색 - CSDN 블로그
[가을 모집 체크인] Day03 - 최강의 2점 시리즈 - 2점 정답 - CSDN 블로그
우리는 이전 주요 제조업체의 실제 질문에 대한 온라인 리뷰를 제공합니다. 관심 있는 친구는 Qinglong에 비공개 메시지를 보내 자세히 알아볼 수 있습니다.
그리고 더! 게다가!
그는 30년 넘게 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈소스 분야에 많은 공헌을 해왔습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.
우편메소피아@프로톤메일.com