Waiting for the dawn

刚面完DB，感觉贼傻逼，一个拓扑排序没DEBUG出来，操了，这下小丑完了😅，我真吐了，不会是秋招唯一一个机会了吧。 MD

CF 300B

void solve() {
  int n, m;
  cin >> n >> m;
  DSU dsu(n + 1);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    dsu.merge(u, v);
  }
  vector<vector<int>> group(n + 1);
  for (int i = 1; i <= n; ++i) {
    group[dsu.f[i]].push_back(i);
  }
  vector<vector<int>> ans;
  vector<vector<int>> one_set, two_set;
  for (int i = 1; i <= n; ++i) {
    if (group[i].size() == 3) {
      ans.push_back(group[i]);
    } else if(group[i].size() == 2) {
      two_set.push_back(group[i]);
    } else if (group[i].size() == 1) {
      one_set.push_back(group[i]);
    } else if (group[i].size() > 3) {
      cout << -1 << '\n';
      return;
    }
  }
  while (!one_set.empty() && !two_set.empty()) {
    one_set.front().insert(one_set.front().begin(), two_set.front().begin(), two_set.front().end());
    two_set.erase(two_set.begin());
    ans.push_back(one_set.front()); // front gives a reference
    one_set.erase(one_set.begin());
  }
  if (two_set.size() > 0) {
    cout << -1 << '\n';
    return;
  }
  while (one_set.size() >= 3) {
    int a, b, c;
    auto f = one_set.begin();
    a = f->front(), f = one_set.erase(f);
    b = f->front(), f = one_set.erase(f);
    c = f->front(), f = one_set.erase(f);
    ans.push_back({a, b, c});
  }
  if (one_set.size()) {
    cout << -1 << '\n';
    return;
  }
  for (auto &v : ans) {
    for (auto &e : v) {
      cout << e << ' ';
    }
    cout << '\n';
  }
  return ;
}

birthday

CF 1680E

void solve() {
  int n;
  cin >> n;
  int l = 1, r = n;
  vector<vector<int>> a(n + 2, vector<int>(3)), dp(a);
  for (int j = 0; j < 2; ++j) {
    for (int i = 1; i <= n; ++i) {
      char c;
      cin >> c;
      a[i][j] = (c == '*' ? 1 : 0);
    }
  }
  while (!a[l][0] && !a[l][1]) ++l;
  while (!a[r][0] && !a[r][1]) --r;
  for (int i = l; i <= r; ++i) {
    dp[i][0] = min(dp[i - 1][0] + 1 + a[i][1], dp[i - 1][1] + 2);
    dp[i][1] = min(dp[i - 1][1] + 1 + a[i][0], dp[i - 1][0] + 2);
  }
  cout << min(dp[r][0], dp[r][1]) - 1 << '\n';
}

CF 1728D

void solve() {
  string s;
  cin >> s;
  int n = s.size();
  s = ')' + s;
  auto check = [&](char x, char y) {
    if (x > y) return 1;
    if (x < y) return -1;
    return 0;
  };
  vector dp(n + 1, vector<int>(n + 1));
  for (int i = 1; i < n; ++i) {
    dp[i][i + 1] = (s[i] == s[i + 1]) ? 0 : 1;
  }
  int f1, f2, f3, f4;
  for (int len = 4; len <= n; len += 2) {
    for (int l = 1, r = len; r <= n; ++l, ++r) {
      dp[l][r] = -1;
      // case 1: Alice pick up s[l], Bob pick up s[l + 1]
      f1 = dp[l + 2][r] == 0 ? check(s[l], s[l + 1]) : dp[l + 2][r]; 
      // case 2: Alice pick up s[l], Bob pick up s[r]
      f2 = dp[l + 1][r - 1] == 0 ? check(s[l], s[r]) : dp[l + 1][r - 1];
      // case 1: Alice pick up s[r], Bob pick up s[r - 2]
      f3 = dp[l][r - 2] == 0 ? check(s[r], s[r - 1]) : dp[l][r - 2];
      // case 1: Alice pick up s[r], Bob pick up s[l]
      f4 = dp[l + 1][r - 1] == 0 ? check(s[r], s[l]) : dp[l + 1][r - 1];
      dp[l][r] = max(min(f1, f2), min(f3, f4));
    }
  }
  if (dp[1][n] == 1) {
    cout << "Alice" << '\n';
  } else if (dp[1][n] == -1) {
    cout << "Bob" << '\n';
  } else {
    cout << "Draw" << '\n';
  }
  return;
}

CF 721C

void solve() {
  int n, m, T;
  cin >> n >> m >> T;
  vector<vector<int>> E(n + 1), cost(n + 1);
  vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF)), pre(dp);
  vector<int> in(n + 1);
  for (int i = 1; i <= m; ++i) {
    int u, v, t;
    cin >> u >> v >> t;
    E[u].push_back(v);
    cost[u].push_back(t);
    in[v]++;
  }
  queue<int> q;
  for (int v = 1; v <= n; ++v) {
    if (!in[v]) {
      q.push(v);
    }
  }
  pre[1][1] = -1;
  dp[1][1] = 0;
  // dp[i][j] means the answer when passes j points and the current point is i
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    for (int i = 0; i < E[u].size(); ++i) {
      int v = E[u][i], c = cost[u][i];
      --in[v];
      if (!in[v]) {
        q.push(v);
      }
      for (int t = 2; t <= n; ++t) {
        if (dp[v][t] > dp[u][t - 1] + c) {
          dp[v][t] = dp[u][t - 1] + c;
          pre[v][t] = u;
        }
      }
    }
  }
  function<void(int, int)> print_trace = [&] (int cur, int t) {
    if (pre[cur][t] == -1) {
      cout << cur << ' ';
      return;
    }  
    print_trace(pre[cur][t], t - 1);
    cout << cur << ' ';
  };
  // reverse iteration
  for (int i = n; i >= 1; --i) {
    if (dp[n][i] <= T) {
      cout << i << '\n';
      print_trace(n, i);
      break;
    }
  }

  return;
}

CF 453 A

void solve() {
  int m, n;
  cin >> m >> n;
  long double ans = 0;
  for (double i = 1; i <= m; i += 1) {
    ans += i * (pow(i / m, n) - pow((i - 1) / m, n));  
  }
  cout << ans << '\n';
  return ;
}

CF 721C

void solve() {
  int n, m, T;
  cin >> n >> m >> T;
  vector<vector<int>> E(n + 1), cost(n + 1);
  vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF)), pre(dp);
  vector<int> in(n + 1);
  for (int i = 1; i <= m; ++i) {
    int u, v, t;
    cin >> u >> v >> t;
    E[u].push_back(v);
    cost[u].push_back(t);
    in[v]++;
  }
  queue<int> q;
  for (int v = 1; v <= n; ++v) {
    if (!in[v]) {
      q.push(v);
    }
  }
  pre[1][1] = -1;
  dp[1][1] = 0;
  // dp[i][j] means the answer when passes j points and the current point is i
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    for (int i = 0; i < E[u].size(); ++i) {
      int v = E[u][i], c = cost[u][i];
      --in[v];
      if (!in[v]) {
        q.push(v);
      }
      for (int t = 2; t <= n; ++t) {
        if (dp[v][t] > dp[u][t - 1] + c) {
          dp[v][t] = dp[u][t - 1] + c;
          pre[v][t] = u;
        }
      }
    }
  }
  function<void(int, int)> print_trace = [&] (int cur, int t) {
    if (pre[cur][t] == -1) {
      cout << cur << ' ';
      return;
    }  
    print_trace(pre[cur][t], t - 1);
    cout << cur << ' ';
  };
  // reverse iteration
  for (int i = n; i >= 1; --i) {
    if (dp[n][i] <= T) {
      cout << i << '\n';
      print_trace(n, i);
      break;
    }
  }

  return;
}