首页 > 其他分享 >2022icpc杭州(The 2022 ICPC Asia Hangzhou Regional Programming Contest)

2022icpc杭州(The 2022 ICPC Asia Hangzhou Regional Programming Contest)

时间:2022-12-09 17:44:46浏览次数:104  
标签:std Contest int Regional Programming cin i64 ++ using

链接:https://codeforces.com/gym/104090

A. Modulo Ruins the Legend

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  i64 d = exgcd(b, a % b, x, y);
  i64 t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}

void solve() {
  i64 n, m;
  cin >> n >> m;
  vector<i64> A(n);
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }
  i64 sum = accumulate(A.begin(), A.end(), 0LL) % m;
  i64 m1 = n % m;
  i64 m2 = n * (n + 1) / 2 % m;
  i64 s = 0, d = 0, a = 0, b = 0;
  i64 m0 = exgcd(m1, m2, s, d);
  i64 m3 = exgcd(m0, m, a, b);
  s = s * a % m;
  d = d * a % m;
  i64 t = (m - sum + m3 - 1) / m3;
  cout << (t * m3 + sum) % m << '\n' << (s * t % m + m) % m << ' ' << (d * t % m + m) % m << '\n';
}

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

D. Money Game

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  double sum = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
  }
  double tmp = sum / (n + 1);
  cout << tmp * 2 << ' ';
  for (int i = 1; i < n; i++) {
    cout << tmp << ' ';
  }
  cout << '\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;
}

F. Da Mi Lao Shi Ai Kan De

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  set<string> mp;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    bool ok = 0;
    for (int j = 0; j < k; j++) {
      string s;
      cin >> s;
      for (int p = 0; p + 2 < (int) s.size(); p++) {
        if (s[p] == 'b' && s[p + 1] == 'i' && s[p + 2] == 'e' && !mp.count(s)) {
          mp.insert(s);
          cout << s << '\n';
          ok = 1;
          break;
        }
      }
    }
    if (!ok) {
      cout << "Time to play Genshin Impact, Teacher Rice!" << '\n';
    }
  }
}

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

G. Subgraph Isomorphism

#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};

using Hash = pair<i64, i64>;

#define x first
#define y second

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  vector<int> deg(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }
  if (m == n - 1) {
    cout << "YES" << '\n';
    return;
  }
  if (m > n) {
    cout << "NO" << '\n';
    return;
  }
  queue<int> q;
  vector<bool> vis(n + 1);
  for (int i = 1; i <= n; i++) {
    if (deg[i] == 1) {
      q.push(i);
    }
  }
  int SIZE = n;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    vis[cur] = 1;
    SIZE--;
    for (auto nex : g[cur]) {
      if (!vis[nex] && --deg[nex] == 1) {
        q.push(nex);
      }
    }
  }
  vector<i64> sz(n + 1);
  auto TreeHash = [&](int root) {
    function<Hash(int, int)> dfs = [&](int cur, int pre) {
      Hash res;
      sz[cur] = 1;
      vector<Hash> s;
      for (auto nex : g[cur]) {
        if (vis[nex] && nex != pre) {
          s.push_back(dfs(nex, cur));
          sz[cur] += sz[nex];
        }
      }
      sort(s.begin(), s.end(), greater<>());
      for (auto si : s) {
        res.x = (res.x * p[0] + si.x) % mod[0];
        res.y = (res.y * p[1] + si.y) % mod[1];
      }
      res.x = (res.x * p[0] + sz[cur]) % mod[0];
      res.y = (res.y * p[1] + sz[cur]) % mod[1];
      return res;
    };   
    return dfs(root, 0);
  };  
  vector<Hash> h;
  int pre = 0;
  int cur = 0;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      cur = i;
      break;
    }
  }
  for (int i = 0; i < SIZE; i++) {
    h.push_back(TreeHash(cur));
    int now = 0;
    for (auto nex : g[cur]) {
      if (!vis[nex] && nex != pre) {
        now = nex;
        break;
      }
    }
    pre = cur;
    cur = now;
  }
  for (int i = 0; i < SIZE; i++) {
    if (h[i] != h[(i + 2) % SIZE]) {
      cout << "NO" << '\n';
      return;
    }
  }
  cout << "YES" << '\n';
}

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

K. Master of Both

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int N = 26;

constexpr int M = 2E6;

i64 cnt[M + 10];
i64 add;
i64 num[N][N];
i64 ed[M + 10];

class Trie {
 public:
  int tot;
  vector<vector<int>> t;
  Trie(const int &n = 2E6) : t(n, vector<int>(N)), tot(0) {}
  inline void insert(const string &s) {
    int SIZE = s.size();
    int u = 0;
    for (int i = 0; i < SIZE; i++) {
      int c = s[i] - 'a';
      for (int j = 0; j < N; j++) {
        if (c != j && t[u][j]) {
          num[c][j] += cnt[t[u][j]];
        }
      }
      if (t[u][c] == 0) {
        t[u][c] = ++tot;
      }
      u = t[u][c];
      cnt[u]++;
    }
    ed[u]++;
    add += cnt[u] - ed[u];
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  Trie tree;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    tree.insert(s);
  }
  for (int i = 0; i < q; i++) {
    string s;
    cin >> s;
    i64 ans = 0;
    for (int j = 0; j < N; j++) {
      for (int k = j; k < N; k++) {
        ans += num[s[j] - 'a'][s[k] - 'a'];
      }
    }
    cout << ans + add << '\n';
  }
}

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

标签:std,Contest,int,Regional,Programming,cin,i64,++,using
From: https://www.cnblogs.com/kiddingma/p/16969596.html

相关文章

  • 2022ccpc威海(2022 China Collegiate Programming Contest (CCPC) Weihai Site)
    链接:https://codeforces.com/gym/104023A.Dunai签到C++Code#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidsolve(){intn;......
  • [Leetcode Weekly Contest]322
    链接:LeetCode[Leetcode]2490.回环句句子是由单个空格分隔的一组单词,且不含前导或尾随空格。例如,"HelloWorld"、"HELLO"、"helloworldhelloworld"都是符合要求的......
  • 【题解】The 2022 ICPC Asia Hangzhou Regional Programming Contest (第 47 届 ICPC
    D.MoneyGame一开始有\(n\)个人围成一圈,第\(i\)个人手上有\(a_i\)的存款(实数),每一轮从第一个人开始,每个人把自己手上的一半存款给下一个人,问稳定时每个人手上存款......
  • The 2022 ICPC Asia Xian Regional Contest B
    B.CellsColoring题链转化题意就是将这些'.'点分成两类第一类就是一个组内每个点都不在同行同列这样一组的贡献就是c第二类就是一些个没被选上的散点每个贡献是d我......
  • AtCoder Beginner Contest 280
    A-PawnonaGrid(abc280a)题目大意给定一个矩形格子,问#的数量。解题思路直接统计即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=......
  • AtCoder Beginner Contest 280 A-F
    AtCoderBeginnerContest280A-Fhttps://atcoder.jp/contests/abc280个人认为D>>E,F被D搞心态了,导致EF都没看()A-PawnonaGrid统计#的个数#include<bits/stdc......
  • AtCoder Beginner Contest 280
    D-FactorialandMultiple对\(k\)进行质因数分解。如果\(k\)最大的质因子\(p\)满足\(p*p>k\),那么答案就是\(p\)。因为一定要包含一次,也只需要包含一次。......
  • AtCoder Beginner Contest 280
    D-FactorialandMultiple数论  首先上这道题需要的数论知识:n!的素因子分解中,n!=p1^a1*p2^a2*p3^a3*.....*pk^ak中对于素因数pi,其对于的ai=n/pi+n/p......
  • AtCoder Beginner Contest 280 题解
    A-PawnonaGrid看样例猜题意(要求的是#的数量,直接判断。//If,oneday,Ifinallymanagetomakemydreamsareality...//Iwonder,willyoustillbethere......
  • AtCoder Beginner Contest 280 D-E
    D-FactorialandMultiple前置知识\(n!\)中包含素因子\(p\)的个数为\[cnt=\sum\limits_{k\geq1}^{p^k\leqn}\lfloor\frac{n}{p^k}\rfloor\]例如:\(n!\)......