https://www.acmicpc.net/problem/13547 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 이 문제는 Update 쿼리가 주어져 있지 않으므로 모스 알고리즘(Mo's Algorithm)으로 풀 수 있다. 처리 방법 : 수가 나오는 빈도를 저장할 배열을 정하여 각 쿼리에 대응 #include #define MEM 100007 #define sanic ios_base::sync_with_stdio(0) #define pb push_back using namespace std; t..

https://www.acmicpc.net/problem/14504 14504번: 수열과 쿼리 18 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. 2 i k: Ai를 k로 www.acmicpc.net 우리는 이를 평방 분할(Sqrt Decomposition)로 풀 수 있다. 퀴리를 n^(1/2)만큼으로 분할 한 다음, 버킷에 정렬된 결과를 저장해놓으면 우리는 이를 lower_bound, upper_bound를 통해 k보다 크거나 같은 A_i의 인덱스를 찾을 수 있다. 그러므로 각 버킷에서 해는 n^(1/2)-(버킷에서 A_i> m..

이 문제는 n,m 범위가 엄청 작기에 백트래킹으러 풀 수 있다. 중복 수열 처리는 STL set의 중복 제거 특징을 이용하여 처리할 수 있다. #include #define sanic ios_base::sync_with_stdio(0); #define MEM 1002 #define f first #define s second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair pii; const ll MOD = 1e9+7; ll n,m; vector v,z; int vis[MEM]; set ans; void bt(int cur, int d){ if(d==m){..

이 문제는 DP로 해결할 수 있다. dp[i][j][k] = i초에 j번 움직이고 k번 나무에 있을 때 최적해 로 두고 풀면 된다. #include #define sanic ios_base::sync_with_stdio(0); #define MEM 1002 #define f first #define s second using namespace std; typedef long long ll; typedef pair pii; const ll MOD = 1e9+7; ll t,n,m,ans; ll dp[MEM][MEM][3]; ll ja[MEM]; main() { sanic; cin.tie(0); cin >> n >> m; for(int i=1; i> ja[i]; for(int i=1; i

우리는 세그먼트 트리를 이용하여 쉽게 구할 수 있다. 구간 합 세그트리를 구현 할 줄 안다면 쉽게 구현이 가능하다. #include #define sanic ios_base::sync_with_stdio(0); #define MEM 4000004 using namespace std; typedef long long ll; const ll MOD = 1e9+7; ll n,m,k; ll tree[MEM], a[MEM]; ll init(int idx, int l, int r){ if(l==r) return tree[idx] = a[l]; int mid=(l+r)/2; return tree[idx] = ((init(idx*2, l, mid)%MOD)*(init(idx*2+1, mid+1, r)%MOD))%MOD..

문제에서 2 또는 5로 나누어 떨어지지 않는 정수만 주어진다 했으니 비둘기집 원리에 의해 항상 답이 존재함을 알 수 있다. 우리는 1을 붙이지 않고 나머지의 성질을 이용하여 풀 수 있다. => (a+b)%MOD = a%MOD + b%MOD => (a*b)%MOD = ((a%MOD)*(b%MOD))%MOD 이를 이용해 배수를 하나의 식을 통해 확인할 수 있다. => a = (a*10+1)%n a가 0일 때까지 저 식을 계산해준다. 답은 저 식을 계산해준 횟수이다. #include #define MEM 500 #define sanic ios_base::sync_with_stdio(0) using namespace std; typedef long long ll; const ll MOD = 1e9+7; ll t..