题目：[[2024.10.17 题目]]
## 语言
有一种新的语言，这种语言有 $26$ 个单次分别对应 $\texttt{a}$ 到 $\texttt{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 的位置，然后对于两边做前/后缀逻辑与并特判即可。
```cpp
#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)$ 时间复杂度，因为只需要进行头尾的插删，而第三种操作实际上就是将链表头连接到目标链表的链表头上。至此，本题便结束了。
**注意**：本题代码难度较高，且特别需要注意细节。好渴鹅就是因为一个小错误调试了两个小时半。（代码是删掉了文明用语的文明绿色版，调试给我调红温了）
```cpp
#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{cases}0&\text{if }n=0\\1&\text{if }n=1\\ fib(n-1)+fib(n-2)&\text{else}\end{cases}$。假设 $S$ 为可重集 $\{s_1,s_2,\cdots,s_{|s|}\}$，则 ${} f(S) {}$ 定义为 $f(S)=\sum\limits_{T\subseteq S}\left[fib(\sum\limits_{s\in T}s)\right]^2$。有一个数组 $a_1,a_2,\cdots,a_n$，会进行 $q$ 次操作。每次操作都是以下两种操作的一种：
- 把 $a_p$ 变为 $v$；
- 计算 $\sum\limits_{i=l}^r\sum\limits_{j=i}^rf(\{a_i,a_{i+1},a_j\})$。
对于操作 $2$，答案对 $998244353$ 取模。
---
刚调完第二题，没时间写了，文件都没有创建，$0$ 分。出题人，我爱你。
## 偶数
对于一个正整数（去掉前导 $0$），如果它在十进制下位数为偶数且前一半与后一半一致，则称这个数为“偶数”。对于一个“偶数”，牛牛可以在这个数后面继续添加数字，使它成为一个新的偶数。牛牛总是添加最少的数字获得新的“偶数”，因此添加的方式唯一。
牛牛会对于一个偶数 $u$，一直产生新的偶数，直到偶数的位数超过给定的正整数 $n$。牛牛会多次询问你这个偶数的第 $l$ 到 $r$ 为所组成的整数摸 $998244353$ 的值是多少。$T$ 组数据。
---
刚调完第二题，没时间写了，而且题目都没有完全读懂，文件都没有创建，$0$ 分。出题人，我爱你。
## 总结
- **排名**：${} 3$；
- **比赛分数**：$200/400$；
- **情况**：相比 [[2024.10.14 模拟赛]]，没区别；
- **问题**：调不出就红温。