电子科大校赛初赛Code

C 箭串

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

int find(std::vector<int> &parent, int x) {
  while (parent[x] != x) {
    parent[x] = parent[parent[x]];
    x = parent[x];
  }
  return x;
}

void solve() {
  int n, m;
  std::cin >> n >> m;
  std::vector<pii > ops(m);
  for(int i = 0; i < m; ++i) {
    int p, l;
    std::cin >> p >> l;
    ops[i] = {p, l};
  }

  std::vector<int> parent(n + 2);
  for(int i = 0; i <= n + 1; ++i) {
    parent[i] = i;
  }
  std::vector<int> last_p(n + 2, 0);
  std::vector<int> last_l(n + 2, 0);

  for(int k = m - 1; k >= 0; --k) {
    int p = ops[k].first;
    int l = ops[k].second;
    int a = p;
    int b = p + l - 1;
    int current = a;
    while (current <= b) {
      int i = find(parent, current);
      if (i > b) break;
      last_p[i] = p;
      last_l[i] = l;
      int next_parent = find(parent, i + 1);
      parent[i] = next_parent;
      current = i + 1;
    }
  }

  std::string res(n, '*');
  for(int i = 1; i <= n; ++i) {
    if (last_p[i] != 0) {
      int pos = i - last_p[i] + 1;
      int l = last_l[i];
      if (pos == 1) {
        res[i - 1] = '>';
      } else if (pos <= l - 3) {
        res[i - 1] = '-';
      } else {
        res[i - 1] = '>';
      }
    }
  }
  std::cout << res.c_str() << endl;
}

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

D 阿罗祖斯坦的桥

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

double angle(double a, double b, double c) { // c
  double res = (a * a + b * b - c * c) / (2 * a * b);
  return std::acos(std::max(-1.0, std::min(1.0, res)));
}

void solve() {
  int n;
  double r;
  std::cin >> n >> r;
  r /= 2.0;
  std::vector<double> a(n + 1, 0.0);
  for(int i = 1, x; i <= n; i++) {
    std::cin >> a[i];
    a[i] += a[i - 1];
  }
  double res = 0;
  for(int i = 0; i < n; i++) {
    res += r * angle(r, r, a[i + 1] - a[i]);
  }

  for(int i = 2; i <= n; i++) {
    res += r * angle(r, r, a[i] - a[0]);
  }
  std::cout << fix(12) << res << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

F 我知道你姓啥

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

int bit_length(int x) {
  if (x == 0) return 0;
  return 32 - __builtin_clz(x);
}

void solve() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::string> s(n);
  for(int i = 0; i < n; ++i) {
    std::cin >> s[i];
  }

  std::unordered_map<std::string, int> ump;
  for(int j = 0; j < m; j++) {
    std::string str;
    for(int i = 0; i < n; ++i)
      str.push_back(s[i][j]);
    ump[str]++;
  }

  int ma = 0;
  for(auto [x, cnt] : ump) {
    if (cnt <= 1) continue;
    int t = bit_length(cnt - 1);
    if (t > ma) ma = t;
  }

  std::cout << ma << endl;
}

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

G 猜数游戏

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

void solve() {
  //x % p = a; l <= x <= r
  i64 a, p, l, r;
  std::cin >> a >> p >> l >> r;
  i64 ans = ((l / p)) * p;

  if (ans + a >= l && ans + a <= r) {
    std::cout << "Yes" << ' ' << ans + a << endl;
    return;
  }
  ans += p;
  if (ans + a >= l && ans + a <= r) {
    std::cout << "Yes" << ' ' << ans + a << endl;
    return;
  } else {
    std::cout << "No" << endl;
  }
}

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

H 独立事件

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int mod = 998244353;

void solve() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> a(n);
  for(int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }

  if (k == 0) {
    i64 ans = 1;
    for(int i = 0; i < n; ++i) {
      ans = ans * 2 % mod;
    }
    std::cout << ans << endl;
    return;
  }

  int sum_A = 0;
  for(int i = 0; i < k; ++i) {
    sum_A += a[i];
  }

  if (sum_A == 1000) {
    i64 ans = 1;
    for(int i = 0; i < n; ++i) {
      ans = ans * 2 % mod;
    }
    std::cout << ans << endl;
    return;
  }

  auto sum_nA = 1000 - sum_A;

  std::vector<int> dp_A(sum_A + 1, 0);
  dp_A[0] = 1;
  for(int i = 0; i < k; ++i) {
    int ai = a[i];
    for(int j = sum_A; j >= ai; --j) {
      dp_A[j] = (dp_A[j] + dp_A[j - ai]) % mod;
    }
  }

  std::vector<int> dp_nA(sum_nA + 1, 0);
  dp_nA[0] = 1;
  for(int i = k; i < n; ++i) {
    int ai = a[i];
    for(int j = sum_nA; j >= ai; --j) {
      dp_nA[j] = (dp_nA[j] + dp_nA[j - ai]) % mod;
    }
  }

  i64 ans = 0;
  for(int x = 0; x <= sum_A; ++x) {
    if (dp_A[x] == 0) continue;
    i64 t = (1000LL - sum_A) * x;
    if (t % sum_A != 0) continue;
    int y = t / sum_A;
    if (y < 0 || y > sum_nA) continue;
    ans = (ans + 1LL * dp_A[x] * dp_nA[y]) % mod;
  }

  std::cout << ans << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

I 圆与直线交点

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

struct Point {
  double x, y;

  explicit Point(double x = 0, double y = 0) : x(x), y(y) {}
};

struct Line {
  Point p, v;

  explicit Line(Point p = Point(), Point v = Point()) : p(p), v(v) {}
};

struct Circle {
  Point c;
  double r;

  explicit Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
};

Point waixin(Point a, Point b, Point c) {
  double a1 = 2 * (b.x - a.x), b1 = 2 * (b.y - a.y), c1 = (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y);
  double a2 = 2 * (c.x - a.x), b2 = 2 * (c.y - a.y), c2 = (c.x * c.x + c.y * c.y - a.x * a.x - a.y * a.y);
  double d = a1 * b2 - a2 * b1, h = (c1 * b2 - c2 * b1) / d, k = (a1 * c2 - a2 * c1) / d;
  return Point(h, k);
}

std::string getLineCircleIntersection(Line L, Circle C) {
  double a = L.v.x, b = L.p.x - C.c.x;
  double c = L.v.y, d = L.p.y - C.c.y;
  double e = a * a + c * c;
  double f = 2 * (a * b + c * d);
  double g = b * b + d * d - C.r * C.r;
  double delta = f * f - 4 * e * g;

  const double eps = 1e-3;
  if (delta < -eps) return "No";
  if (fabs(delta) < eps) return "Or";
  return "Yes";
}

void solve() {
  Point a[3];
  for(auto &i : a) std::cin >> i.x >> i.y;
  Point center = waixin(a[0], a[1], a[2]);
  double r = hypot(center.x - a[0].x, center.y - a[0].y);
  Circle cir(center, r);
  Point p, v;
  std::cin >> p.x >> p.y >> v.x >> v.y;
  Line L = Line(p, v);
  std::cout << getLineCircleIntersection(L, cir) << endl;
}

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

J 创建用户

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

void solve() {
  std::map<std::string, int> mp;
  std::string s;
  int n;
  std::cin >> n;
  std::cin.ignore();
  while (n--) {
    std::getline(std::cin, s);
    std::string str;
    for(auto i : s) {
      if (i != ' ') {
        str.push_back(i);
      } else {
        break;
      }
    }
    int pos = 0;
    while ((pos = s.find(' ', pos + 1)) != -1) {
      str.push_back(s[pos + 1]);
      pos++;
    }
    if (mp.count(str)) {
      std::string t = std::to_string(mp[str] + 1);
      mp[str]++;
      str.insert(str.size(), t);
    } else {
      mp[str] = 0;
    }
    std::cout << str << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

N 幸运之环 II

题目传送门

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

void solve() {
  int n;
  std::cin >> n;
  std::vector<std::vector<int> > a(n + 1, std::vector<int>());
  std::vector<int> deg(n + 1, 0);
  for(int i = 0; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    a[u].push_back(v);
    a[v].push_back(u);
    deg[u]++, deg[v]++;
  }

  std::queue<int> q;
  for(int i = 1; i <= n; ++i) {
    if (deg[i] == 1) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    for(auto v : a[u]) {
      if (deg[v] > 1) {
        deg[v]--;
        if (deg[v] == 1) {
          q.push(v);
        }
      }
    }
  }

  int node = 0;
  for(int i = 1; i <= n; i++) {
    if (deg[i] >= 2 && !node) node = i;
    std::sort(a[i].begin(), a[i].end());
  }

  std::vector<int> res;
  res.push_back(node);
  q.push(node);
  std::vector<bool> vis(n + 1, false);
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for(auto v : a[u]) {
      if (deg[v] >= 2 && !vis[v]) {
        q.push(v);
        res.push_back(v);
        break;
      }
    }
  }

  std::cout << res.size() << ' ';
  for(auto i : res) std::cout << i << ' ';
  std::cout << endl;
}

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

O 不走回头路

题目传送门

error code

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAXN = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

std::vector<std::vector<int> > adj;
std::vector<int> disc, low, scc, stt;
std::stack<int> stk;
int ct_scc, cnt;

void tarjan(int u) {
  disc[u] = low[u] = ++cnt;
  stk.push(u);
  stt[u] = 1;
  for(int v : adj[u]) {
    if (!disc[v]) {
      tarjan(v);
      low[u] = std::min(low[u], low[v]);
    } else if (stt[v]) {
      low[u] = std::min(low[u], disc[v]);
    }
  }
  if (low[u] == disc[u]) {
    ct_scc++;
    while (true) {
      int x = stk.top();
      stk.pop();
      stt[x] = 0;
      scc[x] = ct_scc;
      if (x == u) break;
    }
  }
}

void solve() {
  int n, m;
  std::cin >> n >> m;
  adj = std::vector<std::vector<int> >(n + 1);
  for(int i = 0, u, v; i < m; i++) {
    std::cin >> u >> v;
    adj[u].push_back(v);
  }
  disc.assign(n + 1, 0);
  low.assign(n + 1, 0);
  scc.assign(n + 1, 0);
  stt.assign(n + 1, 0);
  ct_scc = cnt = 0;
  for(int i = 1; i <= n; i++) {
    if (!disc[i]) {
      tarjan(i);
    }
  }
  std::vector<int> in(ct_scc + 1, 0), out(ct_scc + 1, 0);
  std::unordered_map<int, std::unordered_set<int> > mp;
  for(int u = 1; u <= n; u++) {
    for(int v : adj[u]) {
      int su = scc[u], sv = scc[v];
      if (su != sv && !mp[su].count(sv)) {
        mp[su].insert(sv);
        out[su]++;
        in[sv]++;
      }
    }
  }
  int ct1 = 0, ct2 = 0;
  bool flag = true;
  for(int i = 1; i <= ct_scc; i++) {
    if (in[i] == 0) ct1++;
    else if (in[i] != 1) flag = false;
    if (out[i] == 0) ct2++;
    else if (out[i] != 1) flag = false;
  }
  flag &= (ct1 == 1) && (ct2 == 1);
  std::cout << (flag ? "Yes" : "No") << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}