Atcoder Grand Contest 029 요약 문제 풀이

Irreversible operation
역순 을 구하 다.

#include 

using namespace std;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  string s;
  cin >> s;
  long long answer = 0;
  int current = 0;
  for (auto c : s) {
    if (c == 'B') {
      ++current;
    } else {
      answer += current;
    }
  }
  cout << answer << endl;
  return 0;
}

Powers of two
큰 것 부터 작은 욕심 까지.

#include 

using namespace std;

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]);
  }
  sort(a.begin(), a.end());
  vector<int> b(n);
  for (int i = n - 1; ~i; --i) {
    b[i] = 1;
    while (b[i] <= a[i]) {
      b[i] <<= 1;
    }
    b[i] -= a[i];
  }
  int answer = 0;
  map<int, int> c;
  for (int i = 0; i < n; ++i) {
    ++c[a[i]];
  }
  for (int i = n - 1; ~i; --i) {
    if (c[a[i]]) {
      --c[a[i]];
      if (c[b[i]]) {
        --c[b[i]];
        ++answer;
      }
    }
  }
  printf("%d
", answer);
  return 0;
}

Lexicographic constraints
만약 a i < a i + 1 ai

#include 

using namespace std;

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]);
  }
  auto check = [&](int b) {
    map<int, int> s;
    for (int i = 0; i < n - 1; ++i) {
      if (a[i] >= a[i + 1]) {
        while (!s.empty() && s.rbegin()->first >= a[i + 1]) {
          s.erase(--s.end());
        }
        for (int j = a[i + 1] - 1; ~j; --j) {
          ++s[j];
          if (s[j] == b) {
            s.erase(j);
          } else {
            break;
          }
          if (!j) {
            return false;
          }
        }
      }
    }
    return true;
  };
  bool flag = true;
  for (int i = 0; i < n - 1; ++i) {
    if (a[i] >= a[i + 1]) {
      flag = false;
      break;
    }
  }
  if (flag) {
    puts("1");
    return 0;
  }
  int l = 2, r = n + 1;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  printf("%d
", r);
  return 0;
}

Grid game
분명히 첫 번 째 사람 은 계속 아래로 내 려 갈 것 이다. 현재 두 번 째 사람 이 [1, r] [1, r] [1, r] 에 도착 할 수 있다 고 가정 하면 게임 은 끝난다.r + 1 r + 1 r + 1 에 장애 가 없 으 면 오른쪽으로 한 걸음 걸 어서 [1, r + 1] [1, r + 1] [1, r + 1] [1, r + 1] 로 변 할 수 있 습 니 다.

#include 

using namespace std;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n, m, q;
  scanf("%d %d %d", &n, &m, &q);
  vector<int> mins(n, m);
  for (int i = 0; i < q; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    mins[x] = min(mins[x], y);
  }
  int right = 0;
  for (int i = 1; i < n; ++i) {
    if (right >= mins[i]) {
      printf("%d
", i);
      return 0;
    }
    if (right + 1 < mins[i]) {
      ++right;
    }
  }
  printf("%d
", n);
  return 0;
}

Wandering TKHS
x x x 의 답 은 대략 11 에서 x x x 의 체인 접두사 의 최대 치 위치 와 관련 이 있 고 x x x x 가 볼 수 있 는 것 은 p a r e n t x parent 이다.x parentx 가 얻 을 수 있 는 초 집합 은 답 의 차이 점 에 대해 모든 접두사 의 최대 치 를 계산 하여 공헌 하면 됩 니 다.

#include 

using namespace std;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  scanf("%d", &n);
  vector<vector<int>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  vector<int> up(n), parent(n, -1);
  function<void(int)> dfs = [&](int x) {
    if (x) {
      up[x] = max(up[parent[x]], parent[x]);
    }
    for (auto y : adj[x]) {
      if (y != parent[x]) {
        parent[y] = x;
        dfs(y);
      }
    }
  };
  dfs(0);
  vector<int> p(n), size(n);
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    if (i) {
      size[i] = 1;
    }
  }
  auto find = [&](int x) {
    while (x != p[x]) {
      x = p[x] = p[p[x]];
    }
    return x;
  };
  vector<vector<int>> sub(n);
  for (int i = 1; i < n; ++i) {
    sub[up[i]].push_back(i);
  }
  vector<int> value(n), answer(n);
  for (int i = 0; i < n; ++i) {
    for (auto x : sub[i]) {
      if (x < i) {
        answer[x] = size[find(x)];
      } else {
        answer[x] = 1;
        for (auto y : adj[x]) {
          if (y < i) {
            if (y != parent[x]) {
              value[y] = size[find(y)];
            }
            answer[x] += size[find(y)];
          }
        }
      }
    }
    for (auto j : adj[i]) {
      if (j < i) {
        int x = find(i), y = find(j);
        size[x] += size[y];
        p[y] = x;
      }
    }
  }
  vector<int> pos(n);
  vector<int> st;
  function<void(int)> solve = [&](int x) {
    pos[x] = st.size();
    st.push_back(x);
    if (x) {
      answer[x] += answer[up[x]] - value[st[pos[up[x]] + 1]];
    }
    for (auto y : adj[x]) {
      if (y != parent[x]) {
        solve(y);
      }
    }
    st.pop_back();
  };
  solve(0);
  for (int i = 1; i < n; ++i) {
    printf("%d%c", answer[i], i == n - 1 ? '
' : ' ');
  }
  return 0;
}

Construction of a tree
1, 1 이 뿌리 라 고 가정 하면 집합 마다 (u i, p a r e n t u i) (u i, parent {u i}) (ui, parentui) 를 선택 하면 u i ui ui 는 반드시 [2, n] [2, n] [2, n] 의 배열 이 고 네트워크 흐름 으로 이러한 그룹 u i u 를 구 할 것 이다.i ui, 그리고 욕심 구조 p a r e n t u i parent{u i} parentui: 처음에 1, 1 을 대기 열 에 추가 한 다음, 어떤 집합 에 1, 1 이 있 으 면 p a r e n t u i parent{u i} parentui 를 1, 1 로 설정 하고 u i ui ui 가 대기 열 에 가입 합 니 다.이때 풀 리 지 않 으 면 초기 그림 이 연결 되 지 않 는 다 는 것 을 고려 하여 임의로 u ui ui 는 답 에 영향 을 주지 않 습 니 다.

#include 

using namespace std;

const int inf = 0x3f3f3f3f;

namespace flow {
struct edge_t {
  int to, cap, rev;

  edge_t(int t, int c, int r) {
    to = t;
    cap = c;
    rev = r;
  }
};

int n, source, sink, answer;
vector<vector<edge_t>> adj;
vector<int> dist, current;

void init(int v, int s, int t) {
  n = v;
  source = s;
  sink = t;
  answer = 0;
  adj.clear();
  adj.resize(n);
  dist.resize(n);
  current.resize(n);
}

void add(int x, int y, int c) {
  adj[x].push_back(edge_t(y, c, adj[y].size()));
  adj[y].push_back(edge_t(x, 0, adj[x].size() - 1));
}

bool bfs() {
  queue<int> q;
  for (int i = 0; i < n; ++i) {
    dist[i] = -1;
  }
  dist[source] = 0;
  q.push(source);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto e : adj[x]) {
      if (e.cap && !~dist[e.to]) {
        dist[e.to] = dist[x] + 1;
        if (e.to == sink) {
          return true;
        }
        q.push(e.to);
      }
    }
  }
  return false;
}

int dfs(int x, int f) {
  if (x == sink) {
    return f;
  }
  for (int &i = current[x]; ~i; --i) {
    edge_t &e = adj[x][i];
    if (e.cap && dist[e.to] == dist[x] + 1) {
      int w = dfs(e.to, min(e.cap, f));
      if (w) {
        e.cap -= w;
        adj[e.to][e.rev].cap += w;
        return w;
      }
    }
  }
  return 0;
}

int max_flow() {
  while (bfs()) {
    for (int i = 0; i < n; ++i) {
      current[i] = adj[i].size() - 1;
    }
    while (true) {
      int flow = dfs(source, inf);
      if (!flow) {
        break;
      }
      answer += flow;
    }
  }
  return answer;
}
}

using flow::source;
using flow::sink;
using flow::init;
using flow::add;
using flow::adj;
using flow::max_flow;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  scanf("%d", &n);
  vector<vector<int>> a(n - 1);
  vector<vector<int>> v(n);
  init(n * 2, n * 2 - 2, n * 2 - 1);
  for (int i = 0; i < n - 1; ++i) {
    int s;
    scanf("%d", &s);
    a[i].resize(s);
    add(source, i, 1);
    for (int j = 0; j < s; ++j) {
      scanf("%d", &a[i][j]);
      --a[i][j];
      v[a[i][j]].push_back(i);
      if (a[i][j]) {
        add(i, a[i][j] - 1 + n - 1, 1);
      }
    }
  }
  for (int i = 0; i < n - 1; ++i) {
    add(i + n - 1, sink, 1);
  }
  if (max_flow() != n - 1) {
    puts("-1");
    return 0;
  }
  vector<int> match(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    for (auto e : adj[i]) {
      if (e.to < n * 2 - 2 && !e.cap) {
        match[i] = e.to - (n - 1) + 1;
      }
    }
  }
  vector<bool> visit(n);
  vector<int> parent(n - 1);
  int cc = 0;
  function<void(int)> insert = [&](int x) {
    ++cc;
    visit[x] = true;
    for (auto i : v[x]) {
      if (!visit[match[i]]) {
        parent[i] = x;
        insert(match[i]);
      }
    }
  };
  insert(0);
  if (cc != n) {
    puts("-1");
    return 0;
  }
  for (int i = 0; i < n - 1; ++i) {
    printf("%d %d
", match[i] + 1, parent[i] + 1);
  }
  return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Atcoder Grand Contest 029 요약 문제 풀이

좋은 웹페이지 즐겨찾기