T1 密码锁

// CSP-S 2023 密码锁
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
int main() {
#ifdef ONLINE_JUDGE
  freopen("lock.in", "r", stdin);
  freopen("lock.out", "w", stdout);
#endif
  int n;
  cin >> n;
  set<VI> AS;      // 输入的n种状态
  map<VI, int> M;  // 可能的一些来源状态
  VI A(5), B;
  for (int i = 0; i < n; i++) {
    for (int& a : A) cin >> a;
    AS.insert(A);
    for (int i = 0; i < 5; i++)       // 转动的起点
      for (int k = 1; k <= 9; k++) {  // 转动的幅度
        B = A;
        (B[i] += k) %= 10, M[B]++;                     // [i,i] += k
        if (i + 1 < 5) (B[i + 1] += k) %= 10, M[B]++;  // [i,i+1] += k;
      }
  }
  int ans = 0;
  for (auto p : M) ans += (!AS.count(p.first) and p.second == n);
  return printf("%d\n", ans), 0;
}
// AC 100

T2 消消乐

90分代码

// CSP-S 2023 密码锁
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
#ifdef ONLINE_JUDGE
  freopen("game.in", "r", stdin);
  freopen("game.out", "w", stdout);
#endif
  int n;
  string A;
  cin >> n >> A;
  string stk;
  unordered_map<string, int> SM{{stk, 1}};
  LL ans = 0;
  for (char c : A) {
    if (!stk.empty() and stk.back() == c)
      stk.pop_back();
    else
      stk += c;
    ans += SM[stk], SM[stk]++;
  }
  return printf("%lld\n", ans), 0;
}
// AC 90

100分代码

// CSP-S 2023 消消乐
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
#ifdef ONLINE_JUDGE
  freopen("game.in", "r", stdin);
  freopen("game.out", "w", stdout);
#endif
  int n;
  string A;
  cin >> n >> A;
  string stk;
  using ULL = unsigned long long;
  vector<ULL> R(n + 1);
  ULL P = 1e9 + 7;
  R[0] = 1;
  for (int i = 1; i <= n; i++) R[i] = R[i - 1] * P;  // Pⁱ
  unordered_map<ULL, int> HM{{0, 1}};  // 所有前缀消除之后的hash
  LL ans = 0, h = 0;
  for (char c : A) {
    if (!stk.empty() and stk.back() == c)      // 栈顶可以消除
      stk.pop_back(), h -= c * R[stk.size()];  // 消除并更新hash
    else
      h += c * R[stk.size()], stk += c;  // 入栈并更新hash
    ans += HM[h], HM[h]++;  // 更新区间个数，记录栈的状态
  }
  return printf("%lld\n", ans), 0;
}
// AC 100

T3 结构体

// CSP-S 2023 结构体
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct STInfo;
// 基础类型及其长度
map<string, int> MT{{"byte", 1}, {"short", 2}, {"int", 4}, {"long", 8}};
vector<STInfo> Ts;        // 所有的类型
map<string, int> TIDs;    // 类型名:id
struct STInfo {           // 结构体信息
  string name;            // 类型名
  LL align, size;         // 对齐要求, 大小
  vector<int> mTypes;     // 成员类型
  vector<string> mNames;  // 成员名称
  map<string, int> mId;   // 成员名称:编号
  vector<LL> m_st, m_ed;  // 每个成员占用内存的起始和结束地址
  STInfo() : align(0), size(0) {}
  void add_var(const string& t, const string& n) {  // 增加一个类型为t的成员n
    assert(TIDs.count(t));     // 类型t必须已经存在
    int ti = TIDs[t];
    auto& mt = Ts[ti];
    align = max(align, mt.align);  // 对齐要求等于其成员的对齐要求的最大值
    mId[n] = mNames.size();    // 成员名称对应的编号
    mNames.push_back(n), mTypes.push_back(ti);  // 成员名称类型
    LL st = m_ed.empty() ? 0 : m_ed.back();     // 新变量的起点
    while (st % mt.align) ++st;   // 起点要考虑对齐
    LL ed = st + mt.size;   // 终点不用考虑对齐
    m_st.push_back(st), m_ed.push_back(ed), size = ed;
    while (size % align) ++size;  // 整体大小考虑对齐
  }
  LL mem_addr(const string& m) const {  // 成员m的地址
    return m_st.at(mId.at(m));
  }
  int mem_type(const string& m) const {  // 成员m的类型
    return mTypes.at(mId.at(m));
  }
  int mid_of_addr(LL a) const {
    assert(a >= 0);
    int msz = m_st.size();  // 看看哪个成员包含了这个地址, 数据量不大
    for (int i = 0; i < msz; ++i)
      if (m_st[i] <= a && a < m_ed[i]) return i;
    return -1;
  }
};
STInfo G;    // 全局看做一个大结构体
void init() {      // 基础类型初始化
  for (auto p : MT) {  // byte，short，int，long
    string s = p.first;
    // 对于基本类型：对齐要求等于其占据空间大小, 并且没有成员
    STInfo si;
    si.name = s, si.align = MT[s], si.size = MT[s];
    si.m_st.push_back(0), si.m_ed.push_back(MT[s]);
    TIDs[s] = Ts.size(), Ts.push_back(si);
  }
  G.name = "root";
}
// 读入并添加一个类型
const STInfo& add_type() {
  int k;
  STInfo si;
  cin >> si.name >> k;  // 示类型名与成员数量，
  for (string t, n; k--;) cin >> t >> n, si.add_var(t, n);  // 添加成员
  TIDs[si.name] = Ts.size(), Ts.push_back(si);
  return Ts.back();
}
// 所有被定义的元素将按顺序，从内存地址为0开始依次排开
LL def_var(const string& type, const string& name) {
  return G.add_var(type, name), G.m_st.back();
}
// 如a.b.c，需要输出如上被访问的最内层元素的起始地址。
LL find_addr(string v) {
  replace(begin(v), end(v), '.', ' ');
  stringstream ss(v);
  vector<string> ns;
  for (string s; ss >> s; ns.push_back(s))
    ;
  assert(!ns.empty());
  LL a = G.mem_addr(ns[0]);  // 起始地址
  for (int i = 1, ti = G.mem_type(ns[0]); i < (int)ns.size(); i++) {
    a += Ts[ti].mem_addr(ns[i]);  // 成员的内存中的起始位置(偏移量)
    ti = Ts[ti].mem_type(ns[i]);  // 成员的类型, 进入下一级
  }
  return a;
}
string addr_type_name(LL a) {  // 找到addr对应的变量类型
  string s, er = "ERR";
  int mi = G.mid_of_addr(a);
  if (mi == -1) return er;
  s += G.mNames[mi], a -= G.m_st[mi];  // 进入下一级
  for (int ti = G.mTypes[mi]; !MT.count(Ts[ti].name);) {
    const auto& tp = Ts[ti];
    mi = tp.mid_of_addr(a);
    if (mi == -1) return er;
    s += '.' + tp.mNames[mi], a -= tp.m_st[mi], ti = tp.mTypes[mi];
  }
  return s;
}
int main() {
#ifdef ONLINE_JUDGE
  freopen("struct.in", "r", stdin);
  freopen("struct.out", "w", stdout);
#endif
  init();
  int T;
  cin >> T;
  string t, n, s;
  LL addr;
  for (int i = 0, op; i < T; i++) {
    cin >> op;
    if (op == 1) {
      const STInfo& tp = add_type();
      printf("%lld %lld\n", tp.size, tp.align);
    } else if (op == 2)  // 该元素的类型与名称
      cin >> t >> n, printf("%lld\n", def_var(t, n));
    else if (op == 3)
      cin >> s, printf("%lld\n", find_addr(s));
    else if (op == 4)
    cin >> addr, puts(addr_type_name(addr).c_str());
  }
  return 0;
}
// AC 100

T4 种树

// CSPS-2023 种树
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int NN = 1e5 + 4;
LL A[NN], B[NN], C[NN];
int N, F[NN];  // F[i] 表示i这个点最晚种树的天数
vector<int> G[NN];
void dfs(int u, int fa) {
  for (auto v : G[u])  // v一定比父亲u晚一天种
    if (v != fa) dfs(v, u), F[u] = min(F[u], F[v] - 1);
}
using BI = __int128;
// 要求点i在t天后达到目标(≥aᵢ)，必须在第f天前开始种，返回f
LL solve_f(int i, const LL t) {
  LL x = 4e18, b = B[i], c = C[i];  // x树的高度的拐点
  if (c < 0) x = (b - 1 - c - 1) / -c - 1;  // 一开始递减, 第x+1天开始增长率=1
  LL l = 1, r = min(2LL * N, t) + 1;
  while (l + 1 < r) {
    LL m = (l + r) / 2;
    BI s = 0;   // x是拐点
    if (x > t)  // 直接计算从1到t(梯形面积)
      s = (BI)(b + c * m + b + c * t) * (t - m + 1) / 2;
    else if (x >= m)  // m到x, x+1到t两段, 梯形+矩形的面积
      s = (BI)(b + c * m + b + c * x) * (x - m + 1) / 2 + t - x;
    else  // x < m, 所以m到t一路增长率都是1
      s = t - m + 1;
    (s < A[i] ? r : l) = m;
  }
  return r;
}
bool check(LL t) {
  for (int i = 1; i <= N; i++) {
    LL f = solve_f(i, t);
    if (f == 1) return false;
    F[i] = f - 1;
  }
  dfs(1, 0);  // 父亲u还要考虑儿子v的种植时间要求(可能更早)
  sort(F + 1, F + N + 1);  // 按照最晚种植的要求从低到高排序
  for (int i = 1; i <= N; i++)
    if (F[i] < i) return false;  // 无法满足要求
  return true;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i];
  for (int i = 1, u, v; i < N; i++)
    cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
  int l = N, r = 1e9;  // 保证r一直是合法解
  while (l + 1 < r) {
    int m = (l + r) / 2;
    (check(m) ? r : l) = m;
  }
  return printf("%d\n", r), 0;
}
// AC 100