괴물 클럽

문제 T1: XOR과 K의 인수 시험 중에는 정해를 생각하지 못하고 브루트포스로 풀었습니다. 브루트포스는 접두사 XOR을 미리 계산한 후, 모든 구간을 순회하며 구간 XOR이 K의 약수인지 확인하는 방식입니다. 복잡도는 높지만 80점을 받을 수 있었습니다. #include <bits/stdc++.h> #define int long long #define N 1000100 using namespace std; int n, k, arr[N], p ...

해결 방법 1 보조정리: 이분 그래프의 두 부분집합을 각각 X, Y(|X| ≤ |Y|)라고 할 때, 완벽한 매칭이 존재할 필요충분조건은 ∀S ⊆ X, f(S) ≥ |S| (여기서 f(S)는 S와 연결된 점들의 집합)이다. (즉, 홀의 정리) 문제에서 요구하는 것은 기본적으로 완벽한 매칭을 구성하기 위해 최소 몇 개의 의자를 추가해야 하는지를 묻고 있습니다. 따라서 모든 사람이 의자를 선택할 ...

이 문제는 주로 자료구조를 다루며, O(n log²n) 시간 복잡도를 가지는 이진 인덱스 트리와 이분 탐색 조합이 O(n log n)의 세그먼트 트리 이분 탐색보다 빠르다는 점을 보여줍니다. 세그먼트 트리는 상수 최적화가 필요할 정도로 20ms 차이로 시간 초과가 발생합니다. 공식을 통해 k 라운드(모두 사용) 후 체력이 0이 되는 지점을 이분 탐색으로 찾을 수 있습니다. 그 다음 ...

문제 목록 개인이 작성한 것이 아닌 요약입니다 P3812 [템플] 선형 기저 #include <bits/stdc++.h> using namespace std; #define ll long long const int D = 64; ll base[D]; bool flag; bool insert(ll x) { for (int i = D - 1; i >= 0; i--) { if ((x >> i) & 1) { if (base[i]) x ^= base[i]; ...

[HEOI2016/TJOI2016] 트리 이 문제는 트리에서 노드를 표시하거나, 특정 노드로부터 가장 가까운 조상 중 표시된 노드를 찾는 쿼리를 처리해야 한다. 이를 효율적으로 해결하기 위해 경로 분할(Heavy-Light Decomposition) 기법을 사용한다. 각 경로 체인의 맨 위에 있는 표시된 노드를 관리하고, 세트(set)를 이용해 체인 내 위치를 추적한다. 쿼리는 부모 방향으로 이동 ...

P2048 [NOI2010] 슈퍼 피아노 연속 부분 수열의 합을 전처리하고 RMQ를 사용하여 최대값을 찾습니다. 우선순위 큐를 사용하여 최적의 답을 저장합니다. 힙의 맨 위 요소를 꺼내서 계산한 후, 해당 지점을 제외하고 두 개의 새로운 구간을 다시 큐에 추가합니다. 이 과정을 k번 반복합니다. #include <iostream> #include <vector> #include <queue> #inc ...

문제 개요 배열의 각 원소에 대해 오일러 함수를 반복적으로 적용하면서, 특정 범위 내의 모든 원소가 동일한 값으로 수렴하는 최소 연산 횟수를 구하는 문제입니다. 이 과정에서 선형 시간 전처리와 세그먼트 트리, 그리고 LCA(Lowest Common Ancestor) 기법을 결합하여 효율적인 쿼리를 처리합니다. 핵심 아이디어 오일러 함수 φ(n)는 정수 n에 대해 1부터 n까지의 자 ...

A - 손 소독하기 N명의 외계인이 순차적으로 손을 소독하려고 합니다. 각 외계인은 H_i개의 손을 가지고 있으며, 전체를 소독해야 합니다. 소독제는 총 M회 사용할 수 있습니다. 한 외계인이 소독을 할 때 필요한 양만큼만 사용하며, 부족하면 남은 양만 소모합니다. 모든 손을 소독한 외계인의 수를 구하세요. 단순히 앞에서부터 순회하면서 소독제 잔량을 갱신하고, 소진 ...

총점: \(100+100+30+45=275\) 시작 10분 동안 문제 A에 접근했으나, 한 시간 후 포기하고 다른 문제로 이동. 문제 B를 빠르게 해결한 후 C에 도전하였으나 실패. D의 폭력적인 해법을 작성하고 남은 30분 동안 다시 A를 시도. A: H 군의 블록 상단과 하단의 숫자를 모두 세그먼트 트리에 추가합니다. 만약 숫자가 두 번 이상 등장하면 이를 후보로 설정하며, 각 단계에서 ...

A. 기호 기반 계산 시스템 구현 주어진 명령어 집합(정의, 곱셈, 나눗셈, 덧셈, 뺄셈, 모듈러 연산)을 기반으로 간단한 식 계산 시스템을 구현한다. 각 명령어는 변수에 대한 연산을 수행하며, 결과는 항상 모듈러 연산을 통해 유지된다. #include <set> #include <map> #include <iostream> using namespace std; typedef long long LL; const LL MOD ...