VP 记录 - 2022 CCPC 桂林站

发表于 2022-11-17 更新于 2024-06-25 分类于算法竞赛，题解， CCPC 合著者：Foi 本文字数： 578 阅读时长 ≈ 2 分钟

进度: 5 / 13

数学场

题目概览

题号 ¹	标题 ²	做法
A	Lily	签到
*B	Code With No Forces	状压 DP
C	Array Concatenation	前缀和
*D	Alice's Dolls	概率论，EGF
E	Draw a triangle	计算几何，数论
*F	Union of Circular Sectors	计算几何，高数题 (Green 公式，曲线积分)
*G	Group Homework	换根 DP
*H	Hysteretic Racing	线段树二分
*I	Invincible Hotwheels	AC 自动机
*J	Permutation Puzzle	DAG DP, 拓扑排序
*K	Barrel Theory	构造
L	Largest Unique Wins	博弈论，构造
M	Youth Finale	签到 (逆序对)

官方题解

A - Lily

解题思路

复杂度

代码参考

Show code

A.cppview raw

#include <bits/stdc++.h>
using namespace std;
void solve(int t_ = 0) {
  string s;
  cin >> s >> s;
  for (auto &ch : s) ch = (ch == '.' ? 'C' : ch);
  for (size_t i = 0; i < s.size(); ++i)
    if (s[i] == 'L') {
      if (i - 1 >= 0 && s[i - 1] == 'C') s[i - 1] = '.';
      if (i + 1 < s.size() && s[i + 1] == 'C') s[i + 1] = '.';
    }
  cout << s << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  solve(i_);
  return 0;
}

B - Code With No Forces

解题思路

复杂度

代码参考

Show code

C - Array Concatenation

解题思路

复杂度

代码参考

Show code

C.cppview raw

#include <bits/stdc++.h>
#define int long long
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
#define rep(i, a, b) for (int i = (a), i##Limit = (b); i >= i##Limit; --i)
using namespace std;
const int Mod = 1000000007, INV2 = (1000000007 + 1) / 2,
          INV3 = (1000000007 + 1) / 3;
int KSM(int x, int p) {
  int ret = 1;
  while (p) {
    if (p & 1) (ret *= x) %= Mod;
    (x *= x) %= Mod, p >>= 1;
  }
  return ret;
}
signed main() {
  int n, m, S = 0;
  cin >> n >> m;
  vector<int> A(n), pre(n), suf(n);
  Rep(i, 0, n - 1) cin >> A[i], (S += A[i]) %= Mod;
  Rep(i, 0, n - 1) pre[i] = (i == 0 ? A[i] : (A[i] + pre[i - 1]) % Mod);
  rep(i, n - 1, 0) suf[i] = (i == n - 1 ? A[i] : (A[i] + suf[i + 1]) % Mod);
  Rep(i, 0, n - 1) pre[i] = (i == 0 ? pre[i] : (pre[i] + pre[i - 1]) % Mod);
  rep(i, n - 1, 0) suf[i] = (i == n - 1 ? suf[i] : (suf[i] + suf[i + 1]) % Mod);
  auto sum1 = [](int n) -> int { return n * (n + 1) % Mod * INV2 % Mod; };
  auto sum2 = [](int n) -> int {
    return n * (n + 1) % Mod * (2 * n + 1) % Mod * INV2 % Mod * INV3 % Mod;
  };
  int Sum1, Sum2, x = KSM(2, m);
  Sum1 = Sum2 = (((n * (sum1(x - 1)) % Mod) + Mod) % Mod) * S % Mod;
  (Sum1 += x * pre[n - 1] % Mod) %= Mod;
  (Sum2 += (x * INV2 % Mod) * (pre[n - 1] + suf[0]) % Mod) %= Mod;
  cout << max(Sum1, Sum2);
  return 0;
}

D - Alice's Dolls

解题思路

复杂度

代码参考

Show code

E - Draw a triangle

解题思路

复杂度

代码参考

Show code

E.cppview raw

#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
using pll = std::pair<ll, ll>;
using namespace std;
i64 exgcd(i64 &x, i64 &y, i64 a, i64 b) {
  if (b) {
    i64 d = exgcd(y, x, b, a % b);
    y -= a / b * x;
    return d;
  }
  x = 1;
  y = 0;
  return a;
}
void solve(int t_ = 0) {
  pll a, b;
  cin >> a.first >> a.second >> b.first >> b.second;
  i64 lx = b.first - a.first, ly = b.second - a.second;
  if (lx == 0) {
    cout << a.first - 1 << ' ' << a.second << '\n';
    return;
  }
  if (ly == 0) {
    cout << a.first << ' ' << a.second - 1 << '\n';
    return;
  }
  i64 x = 0, y = 0;
  i64 g = exgcd(y, x, lx, ly);
  cout << a.first + x << ' ' << a.second - y << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

F - Union of Circular Sectors

解题思路

复杂度

代码参考

Show code

G - Group Homework

解题思路

复杂度

代码参考

Show code

H - Hysteretic Racing

解题思路

复杂度

代码参考

Show code

I - Invincible Hotwheels

解题思路

复杂度

代码参考

Show code

J - Permutation Puzzle

解题思路

复杂度

代码参考

Show code

K - Barrel Theory

解题思路

复杂度

代码参考

Show code

L - Largest Unique Wins

解题思路

复杂度

代码参考

Show code

L.cppview raw

#include <bits/stdc++.h>
#define inc(i) (++(i))
#define dec(i) (--(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  if (n <= 2 * m) {
    int ans = m, flag = 0;
    Rep(i, 1, n) {
      Rep(j, 1, m)
        if (j == ans && flag < 2) {
          cout << "1 ", inc(flag);
          if (flag == 2) dec(ans);
        } else cout << "0 ";
      cout << '\n';
      if (flag == 2) flag = 0;
    }
  } else {
    int ans = m, flag = 0;
    Rep(i, 1, 2 * m) {
      Rep(j, 1, m)
        if (j == ans && flag < 2) {
          cout << "1 ", inc(flag);
          if (flag == 2) dec(ans);
        } else cout << "0 ";
      cout << '\n';
      if (flag == 2) flag = 0;
    }
    Rep(i, 2 * m + 1, n) {
      Rep(j, 2, m) cout << "0 ";
      cout << "1\n";
    }
  }
  return 0;
}

M - Youth Finale

解题思路

复杂度

代码参考

Show code

M.cppview raw

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 300010;
int n, m, a[N], t[N];
void insert(int x) {
  for (; x <= n; x += x & (-x)) t[x]++;
}
int query(int x) {
  int y = 0;
  for (; x; x -= x & (-x)) y += t[x];
  return y;
}
void solve(int t_ = 0) {
  cin >> n >> m;
  ll ans = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ans += i - 1 - query(a[i]);
    insert(a[i]);
  }
  cout << ans << "\n";
  string s;
  cin >> s;
  int now = 1, flag = 1;
  for (int i = 0; i < m; ++i) {
    if (s[i] == 'S') {
      ans = ans + n + 1 - 2ll * a[now];
      if (flag == 1) now = now % n + 1;
      else {
        now--;
        if (!now) now = n;
      }
    } else {
      ans = (ll)n * (n - 1) / 2 - ans;
      flag = -flag;
      if (flag == 1) now = now % n + 1;
      else {
        now--;
        if (!now) now = n;
      }
    }
    cout << ans % 10;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  solve(i_);
  return 0;
}

打 * 的是还没写的题↩︎
带超链接的是找到了原题或原型↩︎