2024.10.17 模拟赛

题目：2024.10.17 题目

语言

有一种新的语言，这种语言有 $26$ 个单次分别对应 $\text{a}$ 到 $\text{z}$。其中，第 $i$ 个字符词性为第 $a_i$ 类。第 $1\sim 7$ 类分别为：A, N, A/N, V, A/V, N/V, A/N/V。一个合法的句子为名词词组+动词+名词词组。名词词组可以由一个名词（N）、一个形容词（V）加一个名词词组、两个名词词组组成。现在给定字符序列 $S$，判断 $S$ 能否组成一个合法的句子。

---

签到题。根据题意，并结合学习英语的经验，不难发现只有 XX…N V XX…N 的形式才能组成一个合法的句子，其中 X 既可以是形容词 A 也可以是名词 N。因此我们枚举 V 的位置，然后对于两边做前/后缀逻辑与并特判即可。

#include <fstream>
#include <string>
 
using namespace std;
 
const int kMaxN = 1e5 + 5;
 
ifstream cin("language.in");
ofstream cout("language.out");
 
int w[kMaxN], pre[kMaxN], suf[kMaxN], t, n, ans;
string s;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    for (int i = 'a'; i <= 'z'; i++) {
      cin >> w[i];
    }
    cin >> s, ans = 0;
    n = s.size();
    s = ' ' + s;
    pre[0] = 1;
    for (int i = 1; i <= n; i++) {
      pre[i] = pre[i - 1] && (w[s[i]] != 4);
    }
    suf[n + 1] = 1;
    for (int i = n; i >= 1; i--) {
      suf[i] = suf[i + 1] && (w[s[i]] != 4);
    }
    for (int i = 2; i < n && !ans; i++) {
      ans = w[s[i]] >= 4 &&                      // 自己是动词
            w[s[i - 1]] != 1 && w[s[n]] != 1 &&  // 左边和右边最后一个是名词
            pre[i - 1] && suf[i + 1];            // 名词词组
    }
    cout << (ans ? "Yes" : "No") << '\n';
  }
  return 0;
}
 

色球

有 $n$ 种颜色的小球，每种颜色有无限个。还有 $n$ 个球桶，每个球桶能够容下无限多的小球。一开始的球桶都是空的，有 $m$ 次操作，每次操作都是以下三种的任意一种：

• 把 $x$ 个颜色为 $y$ 的彩色小球放到第 $z$ 个桶的最上面；
• 把嘴上面的 $x$ 个小球从第 $z$ 个桶里面拿出来，并输出最后拿出来的球的颜色。保证第 $z$ 个桶里面的球数不小于 $x$ 个；
• 把第 $u$ 个桶里面的小球依次从顶部拿出并放入第 $v$ 个桶内。

---

由于颜色数量最多只有 $m$ 种，且每种颜色的球数很多，不难考虑以颜色为单位进行处理。可以想到 $\mathcal{O}(m^2)$ 的暴力：对于每一个桶都开一个 vector，加入新的球 $\mathcal{O}(1)$，弹出球总共 $\mathcal{O}(m)$ 均摊 $\mathcal{O}(1)$，只有移动球的时间复杂度会达到 $\mathcal{O}(m)$，这将使我们超时。

收到启发式合并的影响，我们不如思考一下对于第三种操作怎么使用启发式合并。模拟可以得到，将小的合并到大的顺序会反转，因此我们还需要额外的变量来记录合并后是否反转，那么合并又要进行四种方式的特判了，过于复杂。

由于时间复杂度的瓶颈主要在第三种操作上面，因此考虑如何优化第三种操作的时间复杂度就成了刚需。在脑海中经过短暂思考，容易想到有一种冷门数据结构叫做「链表」。链表同样支持一二操作的 $\mathcal{O}(1)$ 时间复杂度，因为只需要进行头尾的插删，而第三种操作实际上就是将链表头连接到目标链表的链表头上。至此，本题便结束了。

注意：本题代码难度较高，且特别需要注意细节。好渴鹅就是因为一个小错误调试了两个小时半。（代码是删掉了文明用语的文明绿色版，调试给我调红温了）

#include <fstream>
#include <string>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
ifstream cin("ball.in");
ofstream cout("ball.out");
 
struct Node {
  LL color, count, nxt, prv;
} lst[kMaxN];
 
LL head[kMaxN], tail[kMaxN], n, m, c;
string s;
 
void fuckedAdd(LL x, LL y, LL z) {
  lst[++c].color = y, lst[c].count = x;
  lst[c].prv = tail[z];
  if (tail[z]) {
    (lst[tail[z]].prv ? lst[tail[z]].nxt : lst[tail[z]].prv) = c;
  } else {
    head[z] = c;
  }
  tail[z] = c;
}
 
void fuckedDelete(LL shit) {
  LL p;
  if (lst[tail[shit]].prv) {
    p = lst[tail[shit]].prv;
  } else {
    p = lst[tail[shit]].nxt;
  }
  if (p)  {
    (lst[p].prv == tail[shit] && (lst[p].prv = 0, 1)) || (lst[p].nxt = 0);
  }
  tail[shit] = p;
}
 
void nodeUGetMarriedWithFuckedNodeVWhoIsYourMother(LL x, LL y) {
  if (head[y]) {
    lst[tail[x]].prv ? lst[tail[x]].nxt = tail[y] : lst[tail[x]].prv = tail[y];
    lst[tail[y]].prv ? lst[tail[y]].nxt = tail[x] : lst[tail[y]].prv = tail[x];
  } else {
    head[y] = tail[x];
  }
  tail[y] = head[x];
  head[x] = tail[x] = 0;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL x, y, z; m; m--) {
    cin >> s >> x >> y;
    if (s == "push") {
      cin >> z;
      fuckedAdd(x, y, z);
    } else if (s == "pop") {
      while (x > lst[tail[y]].count) {
        x -= lst[tail[y]].count;
        fuckedDelete(y);
      }
      lst[tail[y]].count -= x;
      cout << lst[tail[y]].color << '\n';
    } else if (s == "put") {
      if (!tail[x]) {
        continue;
      }
      nodeUGetMarriedWithFuckedNodeVWhoIsYourMother(x, y);
    } else {
      cout << "Fuck your mother!" << endl;
    }
  }
  return 0;
}

斐波

令 $fib(n)=\{\begin{array}{ll}0& \text{if }n=0\\ 1& \text{if }n=1\\ fib(n-1)+fib(n-2)& \text{else}\end{array}$。假设 $S$ 为可重集 $\{s_1,s_2,\cdots ,s_{|s|}\}$，则 $f(S)$ 定义为 $f(S)=\sum _{T\subseteq S}{\left[fib(\sum _{s\in T}s)\right]}^2$。有一个数组 $a_1,a_2,\cdots ,a_n$，会进行 $q$ 次操作。每次操作都是以下两种操作的一种：

• 把 $a_p$ 变为 $v$；
• 计算 $\sum _{i=l}^r\sum _{j=i}^{r}f(\{a_i,a_{i+1},a_j\})$。

对于操作 $2$，答案对 $998244353$ 取模。

---

刚调完第二题，没时间写了，文件都没有创建，$0$ 分。出题人，我爱你。

偶数

对于一个正整数（去掉前导 $0$），如果它在十进制下位数为偶数且前一半与后一半一致，则称这个数为“偶数”。对于一个“偶数”，牛牛可以在这个数后面继续添加数字，使它成为一个新的偶数。牛牛总是添加最少的数字获得新的“偶数”，因此添加的方式唯一。

牛牛会对于一个偶数 $u$，一直产生新的偶数，直到偶数的位数超过给定的正整数 $n$。牛牛会多次询问你这个偶数的第 $l$ 到 $r$ 为所组成的整数摸 $998244353$ 的值是多少。$T$ 组数据。

---

刚调完第二题，没时间写了，而且题目都没有完全读懂，文件都没有创建，$0$ 分。出题人，我爱你。

总结

• 排名：$3$；
• 比赛分数：$200/400$；
• 情况：相比 2024.10.14 模拟赛，没区别；
• 问题：调不出就红温。