2024/10/17 模拟赛总结

\(100+50+0+35=185\)，呃呃呃，终于吃上 LRX 了

#A. 语言

考虑名词性词组的性质，由于它可以由任意名词，形容词和名词性词组拼接起来，那么连续的名词，形容词或交替出现都是可行的

但是如果最后一个是形容词不可行，不然它就无法修饰其他词语了

于是可以枚举那一个单独的动词，判断前面和后面知否可以全部是名词/形容词，再判断最后一个单词是不是名词就可以了

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5, kL = 26 + 5;

int t, n, a[kL], l, r;
bool ans;
string s;

void pr(bool pr) {
  cout << (pr ? "Yes" : "No") << '\n';
}

int main() {
  freopen("language.in", "r", stdin), freopen("language.out", "w", stdout);
  for (cin >> t; t; t--, ans = 0) {
    for (int i = 0; i < 26; i++) {
      cin >> a[i];
    }
    cin >> s, n = s.size(), s = ' ' + s, l = n, r = 1;
    if (!(a[s[n] - 'a'] & 2) || n < 3) {
      pr(0);
      continue;
    }
    for (int i = 1; i <= n; i++) {
      if (a[s[i] - 'a'] == 4) {
        l = i - 1;
        break;
      }
    }
    for (int i = n; i; i--) {
      if (a[s[i] - 'a'] == 4) {
        r = i + 1;
        break;
      }
    }
    for (int i = 2; i < n; i++) {
      if ((a[s[i] - 'a'] & 4) && (a[s[i - 1] - 'a'] & 2)) {
        if (l >= i && r <= i) {
          ans = 1;
          break;
        }
      }
    }
    pr(ans);
  }
  return 0;
}

#B. 色球

考场上写不出来入门组 T3 了……

几乎是双向链表板题，对于每一个栈开一个双向链表，前两个操作可以直接均摊 \(O(1)\) 暴力做，复杂度瓶颈在操作三

对于两个双向链表，可以直接将两个栈顶接起来，然后清空一个栈，就可以 \(O(1)\) 解决操作三了

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 5e5 + 5;

struct P {
  LL p, e, l, r;
};

int n, m, y, z, tot, hd[kMaxN], tl[kMaxN];
LL x, c[kMaxN];
P f[kMaxN];
string op;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("ball.in", "r", stdin), freopen("ball.out", "w", stdout);
  for (cin >> n >> m; m; m--) {
    cin >> op >> x >> y;
    if (op == "push") {
      cin >> z, c[z] += x;
      f[++tot] = (P){y, x, hd[z], 0};
      !hd[z] ? tl[z] = tot : (f[hd[z]].l ? f[hd[z]].r = tot : f[hd[z]].l = tot);
      hd[z] = tot;
    } else if (op == "pop") {c[y] -= x;
      for (int L; f[hd[y]].e < x; hd[y] = L) {
        x -= f[hd[y]].e, L = f[hd[y]].l | f[hd[y]].r;
        L && (f[L].l == hd[y] ? f[L].l = 0 : f[L].r = 0);
      }
      f[hd[y]].e -= x;
      cout << f[hd[y]].p << '\n';
    } else {
      c[y] += c[x], c[x] = 0;
      if (hd[x]) {(
        !hd[y] ? tl[y] = hd[x] : (f[hd[y]].l ? f[hd[y]].r = hd[x] : f[hd[y]].l = hd[x]), (f[hd[x]].l ? f[hd[x]].r = hd[y] : f[hd[x]].l = hd[y])); 
        hd[y] = tl[x], hd[x] = tl[x] = 0;
      }
    }
  }
  return 0;
}

#C. 斐波

人机线段树优化区间矩阵乘法，谁爱写谁写

#D. 偶数

若当前“偶数”是 \(\bf{ss}\)，那么其拓展出的新“偶数”一定形如 \(\bf{svsv}\)，其中 \(\bf v\) 是 \(\bf s\) 的前缀

为了使新的“偶数”更短，\(\bf v\) 要尽量短，那么这就是 \(\bf s\) 的周期

那么如果 \(\text{sz}(\textbf{v})\) 是 \(\text{sz}(\textbf{s})\) 的因数，最后的字符串会形如 \(\bf svvvv\dots\)

否则 \(\bf sv\) 将会变成 \(\bf svs\) 并一直循环下去，即 \(\textbf{s}_i=\textbf{s}_{i-1}\textbf{s}_{i-2}\)

于是我们可以维护每一个 \(\textbf{s}\) 的长度，用分治的思想求出当前的值即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e6 + 5;
const LL kP = 998244353;

int t;
LL n, m, q, sz, l, r, h[kMaxN], L[kMaxN], F[kMaxN], mx;
vector<int> br;
string s;

vector<int> Border(string c) {
  int sz = c.size();
  vector<int> ret;
  ret.push_back(0);
  for (int i = 1, k; i < sz; i++) {
    for (k = ret[i - 1]; k && c[i] != c[k]; k = ret[k - 1]) {
    }
    ret.push_back(k + (c[i] == c[k]));
  }
  return ret;
}
LL P(LL x, LL y, LL ret = 1) {
  for (; y; (y & 1) && ((ret *= x) %= kP), (x *= x) %= kP, y >>= 1) {
  }
  return ret;
}
LL Calc(LL m, LL ret = 0, LL cnt = 0) {
  for (int i = mx; ~i; i--) {
    if (cnt + L[i] <= m) {
      ((ret *= P(10, L[i])) += F[i]) %= kP, cnt += L[i];
    }
  }
  ((ret *= P(10, m - cnt)) += h[m - cnt]) %= kP;
  return ret;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("even.in", "r", stdin), freopen("even.out", "w", stdout);
  for (cin >> t; t; t--) {
    cin >> s, n = s.size(), n >>= 1, br = Border(s);
    for (int i = 1; i <= n; i++) {
      h[i] = (h[i - 1] * 10 + (s[i - 1] - '0')) % kP;
    }
    cin >> m >> q, L[0] = n - br[n - 1], L[1] = n, F[0] = h[L[0]], F[1] = h[n];
    for (int i = 2; i < kMaxN; i++) {
      L[i] = L[i - 1] + L[i - 2], F[i] = (F[i - 1] * P(10, L[i - 2]) % kP) + F[i - 2] % kP;
      if (L[i] >= m) {
        mx = i;
        break;
      }
    }
    for (; q; q--) {
      cin >> l >> r;
      cout << (((Calc(r) - Calc(l - 1) * P(10, r - l + 1) % kP) % kP) + kP) % kP << '\n';
    }
  }
  return 0;
}