{"id":908,"date":"2023-11-15T18:53:25","date_gmt":"2023-11-15T10:53:25","guid":{"rendered":"http:\/\/ggapa.net:81\/?p=908"},"modified":"2023-11-15T18:53:25","modified_gmt":"2023-11-15T10:53:25","slug":"csp-s-2023-%e4%bb%a3%e7%a0%81","status":"publish","type":"post","link":"http:\/\/ggapa.net:81\/2023\/11\/15\/csp-s-2023-%e4%bb%a3%e7%a0%81\/","title":{"rendered":"CSP-S 2023 \u4ee3\u7801"},"content":{"rendered":"

T1 \u5bc6\u7801\u9501<\/h1>\n
\/\/ CSP-S 2023 \u5bc6\u7801\u9501\n#include <bits\/stdc++.h>\nusing namespace std;\nusing VI = vector<int>;\nint main() {\n#ifdef ONLINE_JUDGE\n  freopen("lock.in", "r", stdin);\n  freopen("lock.out", "w", stdout);\n#endif\n  int n;\n  cin >> n;\n  set<VI> AS;      \/\/ \u8f93\u5165\u7684n\u79cd\u72b6\u6001\n  map<VI, int> M;  \/\/ \u53ef\u80fd\u7684\u4e00\u4e9b\u6765\u6e90\u72b6\u6001\n  VI A(5), B;\n  for (int i = 0; i < n; i++) {\n    for (int& a : A) cin >> a;\n    AS.insert(A);\n    for (int i = 0; i < 5; i++)       \/\/ \u8f6c\u52a8\u7684\u8d77\u70b9\n      for (int k = 1; k <= 9; k++) {  \/\/ \u8f6c\u52a8\u7684\u5e45\u5ea6\n        B = A;\n        (B[i] += k) %= 10, M[B]++;                     \/\/ [i,i] += k\n        if (i + 1 < 5) (B[i + 1] += k) %= 10, M[B]++;  \/\/ [i,i+1] += k;\n      }\n  }\n  int ans = 0;\n  for (auto p : M) ans += (!AS.count(p.first) and p.second == n);\n  return printf("%d\\n", ans), 0;\n}\n\/\/ AC 100<\/code><\/pre>\n
T2 \u6d88\u6d88\u4e50<\/h1>\n
90\u5206\u4ee3\u7801<\/h2>\n
\/\/ CSP-S 2023 \u5bc6\u7801\u9501\n#include <bits\/stdc++.h>\nusing namespace std;\nusing LL = long long;\nint main() {\n#ifdef ONLINE_JUDGE\n  freopen("game.in", "r", stdin);\n  freopen("game.out", "w", stdout);\n#endif\n  int n;\n  string A;\n  cin >> n >> A;\n  string stk;\n  unordered_map<string, int> SM{{stk, 1}};\n  LL ans = 0;\n  for (char c : A) {\n    if (!stk.empty() and stk.back() == c)\n      stk.pop_back();\n    else\n      stk += c;\n    ans += SM[stk], SM[stk]++;\n  }\n  return printf("%lld\\n", ans), 0;\n}\n\/\/ AC 90<\/code><\/pre>\n
100\u5206\u4ee3\u7801<\/h2>\n
\/\/ CSP-S 2023 \u6d88\u6d88\u4e50\n#include <bits\/stdc++.h>\nusing namespace std;\nusing LL = long long;\nint main() {\n#ifdef ONLINE_JUDGE\n  freopen("game.in", "r", stdin);\n  freopen("game.out", "w", stdout);\n#endif\n  int n;\n  string A;\n  cin >> n >> A;\n  string stk;\n  using ULL = unsigned long long;\n  vector<ULL> R(n + 1);\n  ULL P = 1e9 + 7;\n  R[0] = 1;\n  for (int i = 1; i <= n; i++) R[i] = R[i - 1] * P;  \/\/ P\u2071\n  unordered_map<ULL, int> HM{{0, 1}};  \/\/ \u6240\u6709\u524d\u7f00\u6d88\u9664\u4e4b\u540e\u7684hash\n  LL ans = 0, h = 0;\n  for (char c : A) {\n    if (!stk.empty() and stk.back() == c)      \/\/ \u6808\u9876\u53ef\u4ee5\u6d88\u9664\n      stk.pop_back(), h -= c * R[stk.size()];  \/\/ \u6d88\u9664\u5e76\u66f4\u65b0hash\n    else\n      h += c * R[stk.size()], stk += c;  \/\/ \u5165\u6808\u5e76\u66f4\u65b0hash\n    ans += HM[h], HM[h]++;  \/\/ \u66f4\u65b0\u533a\u95f4\u4e2a\u6570\uff0c\u8bb0\u5f55\u6808\u7684\u72b6\u6001\n  }\n  return printf("%lld\\n", ans), 0;\n}\n\/\/ AC 100<\/code><\/pre>\n
T3 \u7ed3\u6784\u4f53<\/h1>\n
\/\/ CSP-S 2023 \u7ed3\u6784\u4f53\n#include <bits\/stdc++.h>\nusing namespace std;\nusing LL = long long;\nstruct STInfo;\n\/\/ \u57fa\u7840\u7c7b\u578b\u53ca\u5176\u957f\u5ea6\nmap<string, int> MT{{"byte", 1}, {"short", 2}, {"int", 4}, {"long", 8}};\nvector<STInfo> Ts;        \/\/ \u6240\u6709\u7684\u7c7b\u578b\nmap<string, int> TIDs;    \/\/ \u7c7b\u578b\u540d:id\nstruct STInfo {           \/\/ \u7ed3\u6784\u4f53\u4fe1\u606f\n  string name;            \/\/ \u7c7b\u578b\u540d\n  LL align, size;         \/\/ \u5bf9\u9f50\u8981\u6c42, \u5927\u5c0f\n  vector<int> mTypes;     \/\/ \u6210\u5458\u7c7b\u578b\n  vector<string> mNames;  \/\/ \u6210\u5458\u540d\u79f0\n  map<string, int> mId;   \/\/ \u6210\u5458\u540d\u79f0:\u7f16\u53f7\n  vector<LL> m_st, m_ed;  \/\/ \u6bcf\u4e2a\u6210\u5458\u5360\u7528\u5185\u5b58\u7684\u8d77\u59cb\u548c\u7ed3\u675f\u5730\u5740\n  STInfo() : align(0), size(0) {}\n  void add_var(const string& t, const string& n) {  \/\/ \u589e\u52a0\u4e00\u4e2a\u7c7b\u578b\u4e3at\u7684\u6210\u5458n\n    assert(TIDs.count(t));     \/\/ \u7c7b\u578bt\u5fc5\u987b\u5df2\u7ecf\u5b58\u5728\n    int ti = TIDs[t];\n    auto& mt = Ts[ti];\n    align = max(align, mt.align);  \/\/ \u5bf9\u9f50\u8981\u6c42\u7b49\u4e8e\u5176\u6210\u5458\u7684\u5bf9\u9f50\u8981\u6c42\u7684\u6700\u5927\u503c\n    mId[n] = mNames.size();    \/\/ \u6210\u5458\u540d\u79f0\u5bf9\u5e94\u7684\u7f16\u53f7\n    mNames.push_back(n), mTypes.push_back(ti);  \/\/ \u6210\u5458\u540d\u79f0\u7c7b\u578b\n    LL st = m_ed.empty() ? 0 : m_ed.back();     \/\/ \u65b0\u53d8\u91cf\u7684\u8d77\u70b9\n    while (st % mt.align) ++st;   \/\/ \u8d77\u70b9\u8981\u8003\u8651\u5bf9\u9f50\n    LL ed = st + mt.size;   \/\/ \u7ec8\u70b9\u4e0d\u7528\u8003\u8651\u5bf9\u9f50\n    m_st.push_back(st), m_ed.push_back(ed), size = ed;\n    while (size % align) ++size;  \/\/ \u6574\u4f53\u5927\u5c0f\u8003\u8651\u5bf9\u9f50\n  }\n  LL mem_addr(const string& m) const {  \/\/ \u6210\u5458m\u7684\u5730\u5740\n    return m_st.at(mId.at(m));\n  }\n  int mem_type(const string& m) const {  \/\/ \u6210\u5458m\u7684\u7c7b\u578b\n    return mTypes.at(mId.at(m));\n  }\n  int mid_of_addr(LL a) const {\n    assert(a >= 0);\n    int msz = m_st.size();  \/\/ \u770b\u770b\u54ea\u4e2a\u6210\u5458\u5305\u542b\u4e86\u8fd9\u4e2a\u5730\u5740, \u6570\u636e\u91cf\u4e0d\u5927\n    for (int i = 0; i < msz; ++i)\n      if (m_st[i] <= a && a < m_ed[i]) return i;\n    return -1;\n  }\n};\nSTInfo G;    \/\/ \u5168\u5c40\u770b\u505a\u4e00\u4e2a\u5927\u7ed3\u6784\u4f53\nvoid init() {      \/\/ \u57fa\u7840\u7c7b\u578b\u521d\u59cb\u5316\n  for (auto p : MT) {  \/\/ byte\uff0cshort\uff0cint\uff0clong\n    string s = p.first;\n    \/\/ \u5bf9\u4e8e\u57fa\u672c\u7c7b\u578b\uff1a\u5bf9\u9f50\u8981\u6c42\u7b49\u4e8e\u5176\u5360\u636e\u7a7a\u95f4\u5927\u5c0f, \u5e76\u4e14\u6ca1\u6709\u6210\u5458\n    STInfo si;\n    si.name = s, si.align = MT[s], si.size = MT[s];\n    si.m_st.push_back(0), si.m_ed.push_back(MT[s]);\n    TIDs[s] = Ts.size(), Ts.push_back(si);\n  }\n  G.name = "root";\n}\n\/\/ \u8bfb\u5165\u5e76\u6dfb\u52a0\u4e00\u4e2a\u7c7b\u578b\nconst STInfo& add_type() {\n  int k;\n  STInfo si;\n  cin >> si.name >> k;  \/\/ \u793a\u7c7b\u578b\u540d\u4e0e\u6210\u5458\u6570\u91cf\uff0c\n  for (string t, n; k--;) cin >> t >> n, si.add_var(t, n);  \/\/ \u6dfb\u52a0\u6210\u5458\n  TIDs[si.name] = Ts.size(), Ts.push_back(si);\n  return Ts.back();\n}\n\/\/ \u6240\u6709\u88ab\u5b9a\u4e49\u7684\u5143\u7d20\u5c06\u6309\u987a\u5e8f\uff0c\u4ece\u5185\u5b58\u5730\u5740\u4e3a0\u5f00\u59cb\u4f9d\u6b21\u6392\u5f00\nLL def_var(const string& type, const string& name) {\n  return G.add_var(type, name), G.m_st.back();\n}\n\/\/ \u5982a.b.c\uff0c\u9700\u8981\u8f93\u51fa\u5982\u4e0a\u88ab\u8bbf\u95ee\u7684\u6700\u5185\u5c42\u5143\u7d20\u7684\u8d77\u59cb\u5730\u5740\u3002\nLL find_addr(string v) {\n  replace(begin(v), end(v), '.', ' ');\n  stringstream ss(v);\n  vector<string> ns;\n  for (string s; ss >> s; ns.push_back(s))\n    ;\n  assert(!ns.empty());\n  LL a = G.mem_addr(ns[0]);  \/\/ \u8d77\u59cb\u5730\u5740\n  for (int i = 1, ti = G.mem_type(ns[0]); i < (int)ns.size(); i++) {\n    a += Ts[ti].mem_addr(ns[i]);  \/\/ \u6210\u5458\u7684\u5185\u5b58\u4e2d\u7684\u8d77\u59cb\u4f4d\u7f6e(\u504f\u79fb\u91cf)\n    ti = Ts[ti].mem_type(ns[i]);  \/\/ \u6210\u5458\u7684\u7c7b\u578b, \u8fdb\u5165\u4e0b\u4e00\u7ea7\n  }\n  return a;\n}\nstring addr_type_name(LL a) {  \/\/ \u627e\u5230addr\u5bf9\u5e94\u7684\u53d8\u91cf\u7c7b\u578b\n  string s, er = "ERR";\n  int mi = G.mid_of_addr(a);\n  if (mi == -1) return er;\n  s += G.mNames[mi], a -= G.m_st[mi];  \/\/ \u8fdb\u5165\u4e0b\u4e00\u7ea7\n  for (int ti = G.mTypes[mi]; !MT.count(Ts[ti].name);) {\n    const auto& tp = Ts[ti];\n    mi = tp.mid_of_addr(a);\n    if (mi == -1) return er;\n    s += '.' + tp.mNames[mi], a -= tp.m_st[mi], ti = tp.mTypes[mi];\n  }\n  return s;\n}\nint main() {\n#ifdef ONLINE_JUDGE\n  freopen("struct.in", "r", stdin);\n  freopen("struct.out", "w", stdout);\n#endif\n  init();\n  int T;\n  cin >> T;\n  string t, n, s;\n  LL addr;\n  for (int i = 0, op; i < T; i++) {\n    cin >> op;\n    if (op == 1) {\n      const STInfo& tp = add_type();\n      printf("%lld %lld\\n", tp.size, tp.align);\n    } else if (op == 2)  \/\/ \u8be5\u5143\u7d20\u7684\u7c7b\u578b\u4e0e\u540d\u79f0\n      cin >> t >> n, printf("%lld\\n", def_var(t, n));\n    else if (op == 3)\n      cin >> s, printf("%lld\\n", find_addr(s));\n    else if (op == 4)\n    cin >> addr, puts(addr_type_name(addr).c_str());\n  }\n  return 0;\n}\n\/\/ AC 100<\/code><\/pre>\n
T4 \u79cd\u6811<\/h1>\n
\/\/ CSPS-2023 \u79cd\u6811\n#include <bits\/stdc++.h>\nusing namespace std;\nusing LL = long long;\nconst int NN = 1e5 + 4;\nLL A[NN], B[NN], C[NN];\nint N, F[NN];  \/\/ F[i] \u8868\u793ai\u8fd9\u4e2a\u70b9\u6700\u665a\u79cd\u6811\u7684\u5929\u6570\nvector<int> G[NN];\nvoid dfs(int u, int fa) {\n  for (auto v : G[u])  \/\/ v\u4e00\u5b9a\u6bd4\u7236\u4eb2u\u665a\u4e00\u5929\u79cd\n    if (v != fa) dfs(v, u), F[u] = min(F[u], F[v] - 1);\n}\nusing BI = __int128;\n\/\/ \u8981\u6c42\u70b9i\u5728t\u5929\u540e\u8fbe\u5230\u76ee\u6807(\u2265a\u1d62)\uff0c\u5fc5\u987b\u5728\u7b2cf\u5929\u524d\u5f00\u59cb\u79cd\uff0c\u8fd4\u56def\nLL solve_f(int i, const LL t) {\n  LL x = 4e18, b = B[i], c = C[i];  \/\/ x\u6811\u7684\u9ad8\u5ea6\u7684\u62d0\u70b9\n  if (c < 0) x = (b - 1 - c - 1) \/ -c - 1;  \/\/ \u4e00\u5f00\u59cb\u9012\u51cf, \u7b2cx+1\u5929\u5f00\u59cb\u589e\u957f\u7387=1\n  LL l = 1, r = min(2LL * N, t) + 1;\n  while (l + 1 < r) {\n    LL m = (l + r) \/ 2;\n    BI s = 0;   \/\/ x\u662f\u62d0\u70b9\n    if (x > t)  \/\/ \u76f4\u63a5\u8ba1\u7b97\u4ece1\u5230t(\u68af\u5f62\u9762\u79ef)\n      s = (BI)(b + c * m + b + c * t) * (t - m + 1) \/ 2;\n    else if (x >= m)  \/\/ m\u5230x, x+1\u5230t\u4e24\u6bb5, \u68af\u5f62+\u77e9\u5f62\u7684\u9762\u79ef\n      s = (BI)(b + c * m + b + c * x) * (x - m + 1) \/ 2 + t - x;\n    else  \/\/ x < m, \u6240\u4ee5m\u5230t\u4e00\u8def\u589e\u957f\u7387\u90fd\u662f1\n      s = t - m + 1;\n    (s < A[i] ? r : l) = m;\n  }\n  return r;\n}\nbool check(LL t) {\n  for (int i = 1; i <= N; i++) {\n    LL f = solve_f(i, t);\n    if (f == 1) return false;\n    F[i] = f - 1;\n  }\n  dfs(1, 0);  \/\/ \u7236\u4eb2u\u8fd8\u8981\u8003\u8651\u513f\u5b50v\u7684\u79cd\u690d\u65f6\u95f4\u8981\u6c42(\u53ef\u80fd\u66f4\u65e9)\n  sort(F + 1, F + N + 1);  \/\/ \u6309\u7167\u6700\u665a\u79cd\u690d\u7684\u8981\u6c42\u4ece\u4f4e\u5230\u9ad8\u6392\u5e8f\n  for (int i = 1; i <= N; i++)\n    if (F[i] < i) return false;  \/\/ \u65e0\u6cd5\u6ee1\u8db3\u8981\u6c42\n  return true;\n}\nint main() {\n  ios::sync_with_stdio(false), cin.tie(0);\n  cin >> N;\n  for (int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i];\n  for (int i = 1, u, v; i < N; i++)\n    cin >> u >> v, G[u].push_back(v), G[v].push_back(u);\n  int l = N, r = 1e9;  \/\/ \u4fdd\u8bc1r\u4e00\u76f4\u662f\u5408\u6cd5\u89e3\n  while (l + 1 < r) {\n    int m = (l + r) \/ 2;\n    (check(m) ? r : l) = m;\n  }\n  return printf("%d\\n", r), 0;\n}\n\/\/ AC 100<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
T1 \u5bc6\u7801\u9501 \/\/ CSP-S 2023 \u5bc6\u7801\u9501 #include <bits\/stdc++.h> […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"_links":{"self":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/908"}],"collection":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/comments?post=908"}],"version-history":[{"count":1,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/908\/revisions"}],"predecessor-version":[{"id":909,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/908\/revisions\/909"}],"wp:attachment":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/media?parent=908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/categories?post=908"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/tags?post=908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}