Codeforces Good Bye 2014 부분 문제 풀이
12014 단어 codeforces2014Goodbye
Solution A
이 문제는 바로 제목이 준 조건에 따라 풀면 된다.
아흥고로 디프엑스 만들 수 있어요.
위치가 단조롭기 때문에,
그러니까 우리가 직접 한 번 훑어보면 돼.
시간의 복잡도는 O(n)이다.
Code A
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 300000 + 5
int n, k, Next[N];
int main()
{
scanf("%d%d", &n, &k);
int u = 1;
bool ok = 0;
for (int i = 1; !ok && i < n; i ++)
{
scanf("%d", Next + i);
Next[i] += i;
u = u == i ? Next[i] : u;
if (u == k) ok = 1;
}
puts(ok ? "YES" : "NO");
return 0;
}
Solution B라는 문제는 A[i][j]==1의 문제만 바꿀 수 있는 것으로 보입니다.
만약 우리가 A[][]를 인접 행렬로 간주한다면,
실제로 u와 v가 같은 연결 블록 안에 있으면
u는 v와 직접 교환할 수 있습니다.
【증명】
u에서 v까지의 경로가 있다고 가정하면 u-a-...b - v
그러면 우리는 u로 v로 바꿔서 이렇게 된다.
a - ... - b - v - u
그리고 v로 a로 바꿔서 이렇게 돼요.
v - a - ... - b - u.
이것은 u와 v의 직접 교환과 같다.
좋습니다. 사전의 순서가 가장 작은 배열을 요구하기 때문에,
그러면 우리는 모든 연결 블록 안의 원소에 순서를 배열할 수 있다.
사전의 순서가 가장 작은 배열을 얻을 수 있다.
시간의 복잡도는 O(n^2)이다.
Code B
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 300 + 5
int n, A[N], Fa[N], Ord[N];
bool Map[N][N], Flag[N];
inline int Find(int x)
{
return x == Fa[x] ? x : Fa[x] = Find(Fa[x]);
}
inline bool cmp(int u, int v)
{
return A[u] < A[v];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d", A + i);
Ord[i] = Fa[i] = i;
}
sort(Ord + 1, Ord + n + 1, cmp);
char ch = '
';
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
while (ch != '0' && ch != '1')
ch = getchar();
if (ch == '1') Fa[Find(i)] = Find(j);
ch = getchar();
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
Map[i][j] = Find(i) == Find(j);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (Map[i][Ord[j]] && !Flag[j])
{
printf("%d%c", j, i == n ? '
' : ' ');
Flag[j] = 1;
break ;
}
return 0;
}
Solution C
이 문제는 보기에 그리 쉽지 않은 것 같다.
우선 이 문제는 책의 배치 순서를 찾아야 한다.
제목에 따라 책을 읽을 때 총 무게를 최소화할 수 있다.
우리는 먼저 이렇게 해서 순서를 확정할 수 있다.
순서 매거 독서 순서표,
만약 현재의 책을 아직 보지 못했다면,
그럼 지금 다 본 책 밑에 놓고
안 그러면 몰라.
처음부터 끝까지 보지 못한 책에 대해
임의의 순서대로 맨 아래에 놓아라.
이런 순서가 가장 좋다.
【위증】
우선 책을 본 적이 있다면,
그러면 이 책 뒤의 위치가 확정된다.
그래서 우리는 어느 순간에 한 번도 보지 못한 책을 생각하고 있다.
만약 우리가 이 책을 아래에 놓는 것이 위에 놓는 것보다 낫다는 것을 증명할 수 있다면,
그러면 우리는 모든 책이 조건을 충족시키는 방안을 세울 수 있고,
그래서 이 문제는 해결되었다.
만약 이 책이 이전에 읽을 책 위에 놓여 있다면,
그럼 책을 가져올 때,
우리가 고려한 이 책은 답안에 기여해야 한다.
밑에 놓으면,
공헌이 되지 않는다.
그래서 앞서 말한 순서 구조 방법이 가장 좋다.
(증명이 위선적인 것 같아...)
이제 우리는 이런 책의 배치 순서를 얻었고,
다음은 바로 시뮬레이션입니다.
책 한 권을 보는데 필요한 책의 수량은 O(n)이다.
m권의 책을 가져가려면,
그러니까 우리가 직접 폭력 시뮬레이션을 하면 돼.
어쨌든 데이터 범위는 좁다.
시간 복잡도 O(nm).
Code C
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1500 + 5
int n, m, ans, A[N], B[N], Ord[N];
bool Flag[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d", A + i);
for (int i = 1; i <= m; i ++)
{
scanf("%d", B + i);
if (!Flag[B[i]]) Ord[++ Ord[0]] = B[i];
Flag[B[i]] = 1;
}
for (int i = 1; i <= m; i ++)
{
int j = 1;
for (; Ord[j] != B[i]; j ++) ans += A[Ord[j]];
for (; j > 1; j --) swap(Ord[j], Ord[j - 1]);
}
printf("%d
", ans);
return 0;
}
Solution D
이 문제는 그래도 비교적 예쁘다.
체인의 가치에 대한 기대를 우리는 유지하기 어렵다.
O(n^2) 체인이 있기 때문에 수정도 해야 합니다...
어차피 난 못해.
그래서 우리는 모든 측면에서 답안에 대한 공헌을 고려할 수 있다.
우선 우리는 기대는 추가할 수 있다는 것을 안다.
그래서 우리가 이렇게 하는 것은 괜찮다.
우리는 얼마나 많은 상황에서 이 변이 나타날지 고려할 수 있다.
x를 이 변의 한쪽 끝의 점의 개수로 설정하고 다른 한쪽 끝에는 (n-x)의 점이 있다.
따라서 x*(x-1)/2*(n-x)+(n-x)*(n-x-1)/2*x의 경우
이 쪽은 답안에 기여할 것이다.
그리고 나서 우리는 한 변이 계산되지 않거나 두 번 계산되는 것을 알아차렸다.
그래서 한 변의 기대에 대한 공헌은 W * [x * (x - 1) * (n - x) + (n - x) * (n - x - 1) * x]/[n * (n - 1) * (n - 2)]
여기서 W는 모서리의 모서리입니다.
그래서 문제 전체가 가볍고 유쾌해졌다.
질문을 O(1)처리할 수 있습니다.
시간 복잡도 O(n+q).
Code D
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef long double LD;
#define N 100000 + 5
int n, tot = 1, Head[N], Size[N], E[N], W[N];
LD ans;
LL A_n_3;
struct Edge
{
int next, node, w;
}h[N << 1];
inline void addedge(int u, int v, int w)
{
h[++ tot].next = Head[u], Head[u] = tot;
h[tot].node = v, h[tot].w = w;
h[++ tot].next = Head[v], Head[v] = tot;
h[tot].node = u, h[tot].w = w;
}
inline void dfs(int z, int fa)
{
Size[z] = 1;
for (int i = Head[z]; i; i = h[i].next)
{
int d = h[i].node;
if (d == fa) continue ;
dfs(d, z);
Size[z] += Size[d];
W[i >> 1] = Size[d];
}
}
inline LD Calc(int pos, int delta)
{
LL t_1 = (LL) W[pos] * (W[pos] - 1) * (n - W[pos]) * 6;
LL t_2 = (LL) W[pos] * (n - W[pos]) * (n - W[pos] - 1) * 6;
LD t = (LD) (t_1 + t_2) / A_n_3;
return t * delta;
}
int main()
{
scanf("%d", &n);
A_n_3 = (LL) n * (n - 1) * (n - 2);
for (int i = 1; i < n; i ++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
E[i] = w;
}
dfs(1, 0);
for (int i = 1; i < n; i ++)
ans += Calc(i, E[i]);
int q;
scanf("%d", &q);
while (q --)
{
int pos, num;
scanf("%d%d", &pos, &num);
ans -= Calc(pos, E[pos]);
ans += Calc(pos, num);
E[pos] = num;
printf("%.7lf
", (double) ans);
}
return 0;
}
Solution E
만약 우리가 i를 일일이 열거하고 왼쪽 단점을 1로 유지할 수 있다면...i, 오른쪽 단점 i의 답안.
그래서 이 문제는 오프라인으로 풀 수 있다.
사실도 마찬가지다.
우리는 그 하나를 하나의 선으로 바꿀 수 있다 [L, L + H].
그래서 문제는 구(l,r)의 선의 공백 부분 크기로 바뀌었다.
공백은 앞의 것이 무엇인지 뒤의 것이 닿지 않는다는 것을 의미한다.
그래서 우리는 라인의 오른쪽 단점 위치에 따라 단조로운 체감 창고를 유지할 수 있다.
이것은 창고에 있는 두 인접 원소 사이의 모든 것을 통일적으로 고려할 수 있다는 것을 의미한다.
그리고 두 인접 원소 사이의 모든 것을 통일적으로 처리할 수 있다.
우리는 다음과 같은 점을 알아차렸다.
만약 어떤 결정 구간의 그 무엇이 현재의 매거에 미치지 못한다면,
그러면 우리는 이 구간의 답안에 대해 구간 증량을 진행할 것이다.
그리고 이 구간은 삭제될 것이다.
그래서:
그 무엇이 대표하는 구간마다 O(1)회 조작만 할 수 있다.
그래서 이 문제는 구간 증량, 단일 문의,
시간의 복잡도는 O(n log n)이다.
아...내가 분명히 말하지 못한 것 같아...
그럼 제 코드를 보세요...TAT
Code E
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 200000 + 5
#define M 600000 + 5
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int n, T, size, L[N], R[N], q[N];
LL Ans[N];
struct Querys
{
int l, r, id;
Querys (int _l = 0, int _r = 0, int _id = 0) {l = _l, r = _r, id = _id;}
bool operator < (const Querys a) const
{
return r < a.r;
}
}Ask[N];
struct Segment_Tree
{
LL num, delta;
}h[M];
inline void apply(int x, int d)
{
h[x].num += d;
h[x].delta += d;
}
inline void push(int x)
{
if (h[x].delta)
{
apply(ls(x), h[x].delta);
apply(rs(x), h[x].delta);
h[x].delta = 0;
}
}
inline void Modify(int x, int l, int r, int s, int t, int d)
{
if (l == s && r == t)
{
apply(x, d);
return ;
}
push(x);
int mid = l + r >> 1;
if (t <= mid)
Modify(ls(x), l, mid, s, t, d);
else if (s > mid)
Modify(rs(x), mid + 1, r, s, t, d);
else Modify(ls(x), l, mid, s, mid, d), Modify(rs(x), mid + 1, r, mid + 1, t, d);
}
inline LL Query(int x, int l, int r, int t)
{
if (l == r)
return h[x].num;
push(x);
int mid = l + r >> 1;
if (t <= mid)
return Query(ls(x), l, mid, t);
else return Query(rs(x), mid + 1, r, t);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d%d", L + i, R + i);
R[i] += L[i];
}
scanf("%d", &T);
for (int i = 1; i <= T; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
Ask[i] = Querys(l, r, i);
}
sort(Ask + 1, Ask + T + 1);
int t = 1;
for (int i = 1; i <= n; i ++)
{
for (; R[q[size]] <= R[i] && size; size --)
if (R[q[size]] < L[i])
Modify(1, 1, n, q[size - 1] + 1, q[size], L[i] - R[q[size]]);
q[++ size] = i;
while (Ask[t].r == i && t <= T)
{
Ans[Ask[t].id] = Query(1, 1, n, Ask[t].l);
t ++;
}
}
for (int i = 1; i <= T; i ++)
printf("%I64d
", Ans[i]);
return 0;
}
Solution F
이 문제는 틀림없이 분치일 것이다.
우리는 Solve(l,r)를 만들 수 있는데,
처리 시간이 [l,r]에 있는 문의를 나타낸다.
우선, 어떤 item이 [l, r] 이 모든 시간 구간에서 살 수 있다면,
그럼 이 아이템 Dp를 한번,
01배낭이에요.
그리고 이 물건에'이미 처리되었다'는 표시를 하세요.
그런 다음 Solve(l,mid)와 Solve(mid + 1,r)를 반복합니다.
l==r가 될 때까지 문의 시간을 기록하면 딱 l의 답이다.
반드시 거슬러 올라가야 한다!
그리고 가장 중요한 점:
하나의 아이템은 O(log n)회 처리됩니다.
모든 세그먼트가 세그먼트 트리의 O(log n) 구간에 대응하는 것과 유사합니다.
그래서 시간의 복잡도는 O(nT + nB log n)
T는 시간의 최대치이고 B는 예산 금액의 최대치이다.
Code F
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 4000 + 5
#define M 20000 + 5
#define INF 0x7fffffff
int n, p, q, Max, _Max, C[N], W[N], A[N], Dp[21][N], Max_Dp[21][N], T[M], B[M], Ans[M], Done[N];
vector <int> Map[M];
inline void Solve(int depth, int l, int r)
{
for (int i = 1; i <= n; i ++)
if (!Done[i] && A[i] <= l && A[i] + p > r)
{
Done[i] = depth;
for (int j = _Max; j >= C[i]; j --)
Dp[depth][j] = max(Dp[depth][j], Dp[depth][j - C[i]] + W[i]);
}
for (int i = 0; i <= _Max; i ++)
Max_Dp[depth][i] = i == 0 ? Dp[depth][i] : max(Dp[depth][i], Max_Dp[depth][i - 1]);
if (l == r)
{
for (int i = 0; i < Map[l].size(); i ++)
Ans[Map[l][i]] = Max_Dp[depth][B[Map[l][i]]];
for (int i = 1; i <= n; i ++)
if (Done[i] == depth) Done[i] = 0;
return ;
}
int mid = l + r >> 1;
for (int i = 0; i <= _Max; i ++)
Dp[depth + 1][i] = Dp[depth][i];
Solve(depth + 1, l, mid);
for (int i = 0; i <= _Max; i ++)
Dp[depth + 1][i] = Dp[depth][i];
Solve(depth + 1, mid + 1, r);
for (int i = 1; i <= n; i ++)
if (Done[i] == depth) Done[i] = 0;
}
int main()
{
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i ++)
scanf("%d%d%d", C + i, W + i, A + i);
scanf("%d", &q);
for (int i = 1; i <= q; i ++)
{
scanf("%d%d", T + i, B + i);
Max = max(Max, T[i]);
_Max = max(_Max, B[i]);
Map[T[i]].push_back(i);
}
for (int i = 1; i < _Max; i ++)
Dp[0][i] = -INF;
Solve(0, 1, Max);
for (int i = 1; i <= q; i ++)
printf("%d
", Ans[i]);
return 0;
}
G문제에 관해서 나는 너무 약해서 할 줄 모른다.그러니 내가 만났을 때 다시 갱신하자.
그래서 이게 부분적인 문제라고 할 수 밖에 없어요...TAT...=_=
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
