oVeron

13548번: 수열과 쿼리 6 - Mo'shttps://oberon.tistory.com/278 13547번: 수열과 쿼리 5, 13548번: 수열과 쿼리 6 - Mo's13547번: Mo's 알고리즘 기본 문제.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 100001;const int BK = 1001;int N, M;int A[MAXN];vector query;int cnt[1000001];int getBK(int n)oberon.tistory.com 4008번: 특공대 - DP(컨벡스 헐 트릭), 누적 합https://oberon...

알고리즘/solved.ac - CLASS 2024. 8. 10. 09:18

1420번: 학교 가지마! - 최대 유량(MFMC)https://oberon.tistory.com/267 1420번: 학교 가지마! - 최대 유량(MFMC)집에서 학교까지 가는 최소 컷을 구하는 문제이다. 여기서는 디닉 알고리즘을 사용했지만 에드몬드-카프로도 해결할 수 있다. 기준이 간선이 아닌 정점이기 때문에, '2316번: 도시 왕복하기 2'와oberon.tistory.com 2261번: 가장 가까운 두 점 - 분할 정복, 비둘기 집 원리//완전 탐색으로는 O(N^2)이므로 다른 방법이 필요하다. 이 문제는 분할 정복으로 해결할 수 있다.//점들을 x좌표 기준으로 정렬해 절반으로 나눈다. 나눈 두 구간에서 각각 최단 거리를 구했다 가정하자.//두 점이 모두 하나의 구간에 있는 경우는 구했으므로, 이제..

알고리즘/solved.ac - CLASS 2024. 8. 10. 09:17

1017번: 소수 쌍 - 이분 매칭, 수학(소수 판정)https://oberon.tistory.com/262 1017번: 소수 쌍 - 이분 매칭, 수학(소수 판정)두 수를 짝짓는 문제이므로 이분 매칭으로 풀어야 한다. 단, 첫 번째 수와 매칭되는 수의 개수를 구하는 문제이므로, 먼저 첫 번째 수와 임의의 수를 매칭해 고정시킨 다음 이분 매칭 알고리즘을oberon.tistory.com 1126번: 같은 탑 - DP#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 51;const int MAXH = 500001;int N;int block[MAX..

알고리즘/solved.ac - CLASS 2024. 8. 10. 09:16

2673번: 교차하지 않는 원의 현들의 최대집합 - DP//원의 현들의 교차만 중요하므로, 1부터 100까지의 좌표를 수평선상에 놓고 생각할 수 있다.//ex) 현 (1, 45) -> 구간 [1, 45], 현 (11, 65) -> 구간 [11, 65]//현이 교차한다는 뜻은 각 구간이 교차한다는 뜻과 동일하다.//따라서 이 문제를 교차하지 않는 구간의 최대 집합을 구하는 문제로 바꿔 풀 수 있다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int SIZE = 101;int N;bool chord[SIZE][SIZE];int dp[SIZE][SIZE]; //..

알고리즘/solved.ac - CLASS 2024. 8. 10. 09:15

1214번: 쿨한 물건 구매 - 수학(정수론)#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const ll MAXD = 1e9;ll D, P, Q;set per; //P * x + Q * y - D의 주기int main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> D >> P >> Q; if(P Q로 고정한다. //P * x + Q * y >= D일 때, 좌변의 최솟값을 구하는 문제이다. ll x = 0; while(P * x sqrt(le9)일 경우,..

알고리즘/solved.ac - CLASS 2024. 8. 10. 09:14