THUWC2025 题面
bunH2O
·
·
生活·游记
考得太差了，下次不来了。
不过还是记录一下，造福后人。
T1：
3s / 512MB
有一个长度为 n 的排列，以及 m 条限制，每条限制形如一个三元组 (l,r,p)。其含义为区间 [l,r] 单调增 / 减，p=0 时需单调增，p=1 时需单调减。
需构造一个排列，使得其满足的限制条数最多。
---
T2：
1s / 512MB
定义两个四元组 $(x,y,z,w),(x',y',z',w')$ 是无关的，当且仅当 $x\neq x'\land y\neq y'\land z\neq z'$。
你需要动态维护一个初始为空的集合 $S$，其元素均为四元组，需支持如下操作：
- 给定一个四元组 $(x,y,z,w)$，将其插入 $S$ 中，并询问 $S$ 中与该四元组无关的四元组中，$w$ 权值最大的。若不存在返回 $-1$。
$1\leq q\leq 5\times 10^5$，其中 $q$ 是操作次数。
---
T3：
2s / 512MB
你有三个变量 $s,r,k$，其中 $s,r$ 初始为 $0$ 而 $k$ 给定。你有一个操作序列包含如下两种操作，`L` 和 `D`，其规则如下：
- `L`：若 $s=k$，令 $r\leftarrow r+8$。否则令 $s\leftarrow s+1$。
- `D`：若 $s=0$，无事发生。否则令 $s\leftarrow s-1,r\leftarrow r+16$。
对于一组操作序列，在所有操作完成后，令 $r\leftarrow r+3\times s$。
给定一个长度为 $n$ 的操作序列 $a_1,a_2,\cdots,a_n$，其中 $a_i\in\{$`L`$,$`D`$\}$。定义 $f(l,r,x)$ 表示当 $k=x$ 时且操作序列为 $[a_l,a_{l+1},\cdots,a_r]$ 时，操作后 $r$ 的结果。
给定 $q$ 组询问，每次给定 $l,r$，求 $\max\limits_{x=0}^n f(l,r,x)$。
$1\leq n,q\leq 5\times 10^5$。
---
T4：
6s / 2GB
你有三个变量 $s,a,b$，其中 $s$ 初始为 $0$ 而 $a,b$ 给定。你有一个操作序列包含如下三种操作，`1`、`2` 和 `3`，其规则如下：
- `1`：令 $s\leftarrow s+a$。
- `2`：令 $a\leftarrow a+b$。
- `3`：令 $s\leftarrow s\times 2$。
给定 $a,b,k$ 和一个长度为 $n$ 的操作序列 $f$。你需要求出 $f$ 的一个长度为 $k$ 的子序列 $f'$。使得按照 $f'$ 操作后 $s$ 的权值最大。
答案对 $998244353$ 取模。
$1\leq n,k\leq 3\times10^5,1\leq a,b\leq 256$。