CodeForces Gym 101623 간략한 문제 해결
Ascending Photo
먼저 이산화하고 인접한 동일한 수를 하나로 만든다.값 영역을 작은 DP에서 큰 DP로 고려하면 i와 i+1i+1 사이가 절개되지 않으면 i+1i+1과 i+2i+2 사이가 절개되어야 하기 때문에 DP 값과 지난번 결정 지점만 유지하면 됩니다.최대치와 차대치만 유지하면 이동할 수 있다는 것을 발견하기 어렵지 않다.
#include
", n - 1 - u.first);
return 0;
}Boss Battle
특판 n≤3 n≤3의 경우, 그렇지 않으면 매번 boss의 가능한 위치를 1 1로 줄일 수 있으며, 답은 n-3 n-3이다.
#include
", max(n - 2, 1));
return 0;
}Connect the Dots
욕심은 현재의 합법적인 각도를 지키면 된다.
#include
", answer);
return 0;
}Dunglish
모방하다.
#include
' : ' ');
}
cout << (ok ? "correct" : "incorrect") << endl;
} else {
cout << ok << " correct" << endl;
cout << ways - ok << " incorrect" << endl;
}
return 0;
}English Restaurant
탁자를 용량에 따라 정렬하고 마지막에 tt의 용량이 ∞∞인 탁자를 추가합니다.마지막 사람은 몇 개의 구간을 꽉 채웠을 것이다. 먼저 f[l][r]f[l][r][r]는 구간[l,r][l,r]만 앉은 테이블의 방안 수와 답안을 총화하고 마지막에 앉은 테이블의mid m i d를 매거한다. 양쪽은 하위 문제이고 마지막에 온 사람이 구간(al-1,amid](al-3-1,am i d)에 매거하면 옮길 수 있다.
뒤에서 앞으로 DP를 외우고 g[i][j]g[i][j]는 ii를 고려한 후의 시간을 나타낸다. 현재 구간의 가장 왼쪽 단점은 jj의 방안수와 답안을 합친 것이다. 옮길 때 지난번에 옮긴 시간과 지난번 구간의 시작 위치를 일일이 열거하고 접두사와 최적화를 사용하면 된다.
#include operator + (pair a, pair b) {
return make_pair(a.first + b.first, a.second + b.second);
}
pair operator * (pair a, pair b) {
return make_pair(a.first * b.second + a.second * b.first, a.second * b.second);
}
int sum(int x) {
return x * (x + 1) >> 1;
}
int main() {
#ifdef wxh010910
freopen("input.txt", "r", stdin);
#endif
int n, group, hours;
scanf("%d %d %d", &n, &group, &hours);
vector<int> a(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
a[i] = min(a[i], group);
}
sort(a.begin(), a.end());
for (int i = 0; i < hours; ++i) {
a.push_back(group + 1);
++n;
}
vector<vector value = make_pair(0, binom[j - i][k - i]);
value = value * make_pair(a[k] == group + 1 ? 0 : sum(a[k]) - sum(i ? a[i - 1] : 0), min(a[k], group) - (i ? min(a[i - 1], group) : 0));
if (k != i) {
value = value * dp[i][k - 1];
}
if (k != j) {
value = value * dp[k + 1][j];
}
dp[i][j] = dp[i][j] + value;
}
}
}
vector<vector value = make_pair(0, binom[hours - i][hours - k]);
value = value * dp[j][j + k - i - 1] * sum[k][j + k - i + 1];
f[i][j] = f[i][j] + value;
}
}
sum[i][j] = f[i][j];
if (j + 1 < n) {
sum[i][j] = sum[i][j] + sum[i][j + 1];
}
}
}
pair answer;
for (int i = 0; i < n; ++i) {
answer = answer + f[0][i];
}
printf("%.8lf
", (double)(answer.first / answer.second));
return 0;
} Factor-Free Tree
분해질 인수는 왼쪽에서 오른쪽으로 가장 먼 곳까지 모든 것과 호환성을 구하고 중간 순서에 따라 전체 서열을 두루 고려한다. 한 창고는 이전의 가장 오른쪽 체인을 표시하고 새로운 점이 생길 때마다 먼저 아래로 걸어서 아버지의 rr가 자신의 rr보다 크거나 그의 ll가 왼쪽의 자수를 덮을 수 없을 때까지 위로 올라가려고 한다.
#include int , int>, int>> stack(n + 1);
stack[0].first.second = -1;
int top = 0;
for (int i = 0; i < n; ++i) {
stack[top + 1].first.second = -1;
int temp = i;
while (top && l[i] <= stack[top].first.first && r[i] >= stack[top].second) {
temp = min(temp, stack[top].first.first);
--top;
}
if (~stack[top + 1].first.second) {
answer[stack[top + 1].first.second] = i;
}
answer[i] = stack[top].first.second;
int right = top ? stack[top].second : n;
if (right < i) {
puts("impossible");
return 0;
}
stack[++top] = make_pair(make_pair(temp, i), min(r[i], right));
}
for (int i = 0; i < n; ++i) {
printf("%d%c", answer[i] + 1, i == n - 1 ? '
' : ' ');
}
return 0;
}Glyph Recognition
매거 변수는 공식적으로 두 개의 bound를 계산해 낼 수 있고 직접 계산하면 된다.
#include
", best, (double)answer);
return 0;
}High Score
제곱의 성장이 비교적 빠르기 때문에 작은 두 개가 얼마나 증가했는지 매거할 수 있다. 이 값은 크지 않고 폭력이면 된다.
#include
", answer);
}
return 0;
}Installing Apps
만약에 모든 것을 선택한다면 가장 좋은 순서는 반드시 max(d,s) - d max(d,s) - - d에 따라 큰 것부터 작은 것까지 순서를 정하고 f(i,j) f(i,j)를 외우는 것이 전 ii의 물품을 고려하고 j개를 선택했는데 최소한 얼마의 공간을 차지했는지 나타낸다.
#include
", i);
if (i) {
vector<int> answer;
for (int j = n, current = i; j; --j) {
if (g[j][current]) {
--current;
answer.push_back(apps[j - 1].id);
}
}
reverse(answer.begin(), answer.end());
for (int j = 0; j < answer.size(); ++j) {
printf("%d%c", answer[j] + 1, j == answer.size() - 1 ? '
' : ' ');
}
}
return 0;
}
}
return 0;
}Juggling Troupe
22마다 단독으로 고려하여 ii라고 가정하고 그 좌우의 000의 위치 l,rl,r를 구하면 l,rl,r를 1로 부여하고 l+r-3-i l+r-3을 0으로 부여한다.set로 유지보수하면 됩니다.
#include Knockout Tournament
a1a1을 0 0으로 보고 aa에 따라 작은 순서에서 큰 순서로 인접한 매칭이 가장 좋다.그리고 트리 DP를 만들면 됩니다.
#include int , ld>>> &f) {
if ((x << 1 | 1) >= m) {
f[x].push_back(make_pair(--index, 1));
} else {
dfs(x << 1 | 1, m, index, f);
dfs(x + 1 << 1, m, index, f);
}
}
int main() {
#ifdef wxh010910
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int first = a[0];
a[0] = 0;
sort(a.begin(), a.end());
a[0] = first;
int m = (n << 1) - 1, binary = 1;
while ((binary << 1 | 1) <= m) {
binary = binary << 1 | 1;
}
vector<vectorint , ld>>> f(m);
int index = n;
dfs(0, m, index, f);
for (int i = m - n - 1, j = 0; ~i; --i) {
int l = i << 1 | 1, r = i + 1 << 1;
for (int rotate = 0; rotate < 2; ++rotate) {
for (auto p : f[l]) {
int index = p.first;
ld prob = 0;
for (auto q : f[r]) {
prob += q.second * a[index] / (a[index] + a[q.first]);
}
f[i].push_back(make_pair(index, prob * p.second));
}
swap(l, r);
}
}
for (auto p : f[0]) {
if (!p.first) {
printf("%.8lf
", (double)p.second);
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
