부스터
문제 설명
체크포인트가 최대 25만개가 존재하고, 각 체크포인트는 2차원 상에 존재한다.
플레이어는 해당 체크포인트를 오가면서 원하는 곳에 도달해야 하는게 목표
플레이어는 2개의 방법으로 이동할 수 있다.
1. 걷기 : 단순한 걷기, d만큼 이동했을 경우, HP가 d만큼 줄어든다.
2. 부스터 : HP를 소모하지 않고, 원하는 방향(동, 서, 남, 북)으로 어디로든 갈 수 있다.
부스터는 "방전"과 "충전"의 두 가지 상태를 가지며, 충전 상태에만 사용될 수 있다. 한번
사용되면 부스터는 방전된다. 각 체크포인트에서는 부스터를 충전상태로 변경할 수 있다.
쿼리가 최대 25만개가 주어진다.
x, y, z : HP가 x인 경우 y 체크포인트에서 z체크포인트로 갈 수 있는지 여부해결
요구 스킬
1. 오프라인 쿼리
2. Union-Find
3. 관찰
작업 1.
먼저, (X,Y)에 위치한 체크포인트에서 (X1,Y1)에 위치한 체크포인트로 이동하는 방법은
min((X - X1), (Y, Y1)) <= HP인 경우에 직접적으로 갈 수 있다.
그러면 X를 기준으로 체크포인트를 정렬하고 A, B, C 라는 체크포인트가 있다고 가정해보자.
Y는 기준으로 제외하고 X를 기준으로만 생각해보면, A에서 C라는 체크포인트로 갈 수 있다고
가정한다면 A에서 B와 B에서 C로도 무조건 가능하다는 것을 알 수 있다. (Y도 마찬가지)
따라서 X, Y를 따로 기준으로 정렬한 다음 앞,뒤의 차이를 구한 값과 두 체크포인트를 저장하는
작업을 수행하고, 앞 뒤의 차이의 최소를 기준으로 정렬을 하고, V라는 배열에 저장
작업 2.
쿼리를 받은 다음, HP를 오름차순으로 정렬을 한다. 그리고 HP가 가장 적은순으로
답을 처리하는 방향으로 진행을 한다. 현재 V라는 배열의 앞,뒤 차이의 최소값이 해당 HP값 이하인
얘들을 Union-Find를 통해 같은 집합 만든다.
그리고 해당 쿼리를 처리하는데, 해당 쿼리에 있는 두 개의 체크포인트가 같은 집합이면 YES
그렇지 않으면 NO를 저장.
마지막으로 0번쿼리부터 시작해서 해당하는 값을 출력
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ans[250001];
int p[250001];
struct A {
int x, y, z;
};
struct Query {
int x, y, z, idx;
bool operator<(const Query obj) {
return x < obj.x;
}
};
bool comp(A x, A y) {
return x.x < y.x;
}
bool comp2(A x, A y) {
return x.y < y.y;
}
int f(int x) {
if (p[x] == x)
return x;
else
return p[x] = f(p[x]);
}
void merge(int x, int y) {
x = f(x);
y = f(y);
p[y] = x;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<A> v;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
v.push_back({x, y, i + 1});
}
priority_queue<pair<int, pair<int, int>>> q;
sort(v.begin(), v.end(), comp);
for (int i = 0; i < n - 1; i++) {
q.push({-(v[i + 1].x - v[i].x), {v[i].z, v[i + 1].z}});
}
sort(v.begin(), v.end(), comp2);
for (int i = 0; i < n - 1; i++) {
q.push({-(v[i + 1].y - v[i].y), {v[i].z, v[i + 1].z}});
}
vector<Query> query;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> z >> y >> x;
query.push_back({x, y, z, i});
}
sort(query.begin(), query.end());
for (int i = 0; i < m; i++) {
while (!q.empty() && -q.top().first <= query[i].x) {
merge(q.top().second.first, q.top().second.second);
q.pop();
}
if (f(query[i].y) == f(query[i].z)) {
ans[query[i].idx] = true;
}
}
for (int i = 0; i < m; i++) {
if (ans[i])
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
}준오는 심술쟁이!!
문제 설명
1. 준오는 문제 이름에서 아무 문자나 골라 k(1 ≤ k ≤ 25)만큼 바꿔버린다.
예를 들어, a를 3만큼 바꾸면 d로, z를 1만큼 바꾸면 a로 바뀐다.
2. 문자를 바꿀 때마다 k를 다시 고른다.
3. k의 합이 s가 될 때까지 문자를 계속 바꾼다. 단, 한 번 바꾼 문자를 다시 바꾸지는 않는다.
원래 이름이 주어졌을 때, 위 조건을 만족하는 새로운 이름의 경우의 수를 구하는 문제해결
dp[x][y] = 현재 x번째 문자열까지 사용한 k들의 합이 y인 경우
Example
dp[5][4] = 4번째 문자열에서 사용한 k가 (0 ~ 4)인 경우들의 합
dp[5][4] = dp[4][4] + dp[4][3] + dp[4][2] + ... + dp[4][0]
dp[5][3] = dp[4][3] + dp[4][2] + ... + dp[4][0]
3000 * 3000 * 25로 시간초과가 발생! 구간합을 사용해 미리 전처리를 해줘야 한다.
구간합으로 전처리를 해두면 O(1)만에 가능!코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
string s;
int n, m;
ll d[3001][3001];
ll sum[3001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> s;
m = (int)s.size();
for (int i = 0; i <= 25; i++) {
d[1][i] = 1;
}
for (int i = 2; i <= m; i++) {
for (int j = 0; j <= n; j++) {
sum[j] = sum[j - 1] + d[i - 1][j];
sum[j] %= mod;
}
for (int j = 0; j <= n; j++) {
d[i][j] += sum[j];
if (j >= 26) d[i][j] -= sum[j - 26];
while (d[i][j] < 0) d[i][j] += mod;
}
}
cout << d[m][n] << '\n';
}
Wow