标签：女生 2022ccpc int tt cin i64 2022 using dp

A

签到，双端队列模拟。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int n, k;
  cin >> n >> k;
  deque<array<int, 2>> q;
  vector<array<int, 2>> a(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    q.push_back({x, i});
    a[i] = {x, i};
  }
  vector<int> cnt(n);
  int pre = -1;
  for (int i = 0; i < n; i++) {
    auto [now1, id1] = q.front();
    q.pop_front();
    auto [now2, id2] = q.front();
    q.pop_front();
    if (now1 < now2) {
      swap(now1, now2);
      swap(id1, id2);
    }
    q.push_front({now1, id1});
    q.push_back({now2, id2});
    if (id1 == pre) {
      cnt[id1]++;
    } else {
      if (pre != -1)
        cnt[pre] = 0;
      cnt[id1]++;
    }
    pre = id1;
    if (cnt[id1] == k) {
      cout << id1 + 1 << '\n';
      return;
    }
  }
  cout << q.front()[1] + 1 << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

C

签到

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

const double Pi = acos(-1.0);

void solve() {
  int n;
  double R, theta;
  cin >> n >> R >> theta;
  theta = min(theta, 2 * Pi - theta);
  double ans = theta * R;
  for (int i = 0; i < n; i++) {
    double r;
    cin >> r;
    ans = min(ans, R - r + R - r + theta * r);
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << fixed << setprecision(12);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

E

签到，听两遍歌然后特判一下。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int x, t, k, n, d;
  cin >> x >> t >> k >> n >> d;
  vector<int> a(n << 1);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] <= d) {
      a[i] = -1;
    } else {
      a[i] = 1;
    }
    a[n + i] = a[i];
  }
  int now = x;
  int cnt = 0;
  for (int i = 0; i < (n << 1); i++) {
    now += a[i];
    if (now <= k) {
      cnt++;
    } else {
      cnt = 0;
    }
    if (cnt == t) {
      cout << "YES" << '\n';
      return;
    }
  }
  if (now < x || cnt == 2 * n) {
    cout << "YES" << '\n';
    return;
  }
  cout << "NO" << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

G

C++ Code

模拟。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  i64 t, n;
  cin >> t >> n;
  int m;
  i64 k;
  cin >> m >> k;
  vector<array<int, 2>> a(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i][0] >> a[i][1];
  }
  sort(a.begin(), a.end());
  i64 cnt = 0;
  i64 pre = 0;
  int now = 0;
  for (int i = 0; i < m; i++) {
    if (a[i][0] >= t) {
      now = i;
      break;
    }
    cnt -= min(cnt, k * (a[i][0] - pre));
    cnt += a[i][1];
    pre = a[i][0];
  } 
  cnt -= min(cnt, k * (t - pre));
  pre = t;
  if (cnt != n) {
    cout << "Wrong Record" << '\n';
    return;
  }
  i64 ans = 9E18;
  int time = 0;
  for (int i = now; i < m; i++) {
    cnt -= min(cnt, k * (a[i][0] - pre));
    cnt += a[i][1];
    pre = a[i][0];
    if ((cnt + 1 + k - 1) / k <= ans) {
      ans = (cnt + 1 + k - 1) / k;
      time = a[i][0];
    }
  }
  cout << time << ' ' << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

H

记录下从起点开始花多少步到某处的代价，最后加一下取 \(min\) 就行。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<array<int, 2>>> adj(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  vector<vector<i64>> dis(n + 1, vector<i64>(n + 1, 9E18));
  dis[0][1] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (auto [nex, w] : adj[j]) {
        dis[i][j] = min(dis[i][j], dis[i - 1][nex] + w);
      }
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int e;
    cin >> e;
    i64 ans = 9E18;
    i64 sum = 0;
    for (int i = 1; i < n; i++) {
      int x;
      cin >> x;
      sum += x;
      ans = min(ans, dis[i][e] + sum);
    }
    cout << ans << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

I

\(dp[i][0/1]\) 表示组成询问串的前 \(i\) 位，结尾的串属于 A/B 类串的最短
步数。

枚举一下 \(i\)，\(j\) 表示上一个可以匹配位置 \(f[i][0/1]=min(f[j][1/0]+1)\)。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

static constexpr int p[2] = {223333333, 773333333};
static constexpr int mod[2] = {1000000033, 1000002233};

constexpr int N = 5E5;

i64 pw[2][N + 10];

void init() {
  pw[0][0] = 1;
  pw[1][0] = 1;
  for (int i = 1; i <= N; i++) {
    pw[0][i] = pw[0][i - 1] * p[0] % mod[0];
    pw[1][i] = pw[1][i - 1] * p[1] % mod[1];
  }
}

class StringHash {
public:
  vector<vector<i64>> h;
  StringHash() : h(2, vector<i64>(1)) {}
  inline void push_back(char ch) {
    h[0].push_back((h[0].back() * p[0] + ch) % mod[0]);
    h[1].push_back((h[1].back() * p[1] + ch) % mod[1]);
  }
  inline i64 get(int l, int r) {
    return (h[0][r + 1] - h[0][l] * pw[0][r - l + 1] % mod[0] + mod[0]) % mod[0] + (((h[1][r + 1] - h[1][l] * pw[1][r - l + 1] % mod[1] + mod[1]) % mod[1]) << 30);
  }
};

void solve() {
  int n;
  cin >> n;
  map<int, unordered_set<i64>> a, b;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    StringHash h;
    for (auto x : s) {
      h.push_back(x);
    }
    int len = s.size();
    a[len].insert(h.get(0, len - 1));
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    string s;
    cin >> s;
    StringHash h;
    for (auto x : s) {
      h.push_back(x);
    }
    int len = s.size();
    b[len].insert(h.get(0, len - 1));
  }
  string s;
  cin >> s;
  int len = s.size();
  StringHash hs;
  for (auto x : s) {
    hs.push_back(x);
  }
  vector<vector<int>> dp(N + 10, vector<int>(2, 1E9));
  dp[0][0] = dp[0][1] = 0;
  for (int i = 1; i <= len; i++) {
    for (auto &[l, v] : a) {
      if (l > i) {
        continue;
      }
      if (v.count(hs.get(i - l, i - 1))) {
        dp[i][0] = min(dp[i][0], dp[i - l][1] + 1);
      }
    }
    for (auto &[l, v] : b) {
      if (l > i) {
        continue;
      }
      if (v.count(hs.get(i - l, i - 1))) {
        dp[i][1] = min(dp[i][1], dp[i - l][0] + 1);
      }
    }
  }
  i64 ans = min(dp[len][0], dp[len][1]);
  if (ans == 1E9) {
    cout << -1 << '\n';
    return;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  init();
  while (tt--) {
    solve();
  }
  return 0;
}

F

构造，先考虑如果知道哪个对应 \(A\oplus B,A\oplus C\) \(B\oplus C,A|B,B|C,A|C,A\& B,B\& C,A\& C\) 的哪个，问题就会变得简单。

位运算具有性质：\(a\oplus b=(a|b)\oplus(a\& b)\)。

运用该性质进行枚举就可以分出 \(3\) 组。

然后考虑如何构造。

标签：女生,2022ccpc,int,tt,cin,i64,2022,using,dp
From： https://www.cnblogs.com/kiddingma/p/16942247.html

2022ccpc女生赛（2022年中国大学生程序设计竞赛女生专场）

A

C

E

G

H

I

F

相关文章

赞助商

阅读排行