赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 奇怪的齿轮 入门 T2 奇怪的数组 普及- T3 奇怪的数学 普及/提高- T4 奇怪的探针 普及+/提高 T5 奇怪的树 普及+/提高 T6 奇怪的集市 普及+/提高
T1 奇怪的齿轮
题目大意
在一个 h×wh \times wh×w 的网格平面上 每个格子可以放一个齿轮 或者留空
若两个放了齿轮的格子相邻 即共享一条边 它们会啮合 且啮合齿轮的转向必须相反
一次放置被称为合理 当且仅当 已放置的所有齿轮可以被赋予顺时针或逆时针的方向 使每一对相邻齿轮的方向相反
只区分放与不放 不把具体顺逆视为不同方案
求合理放置的总数 输出对 998244353998244353998244353 取模后的结果
题解思路
网格按上下左右相邻建边 是棋盘图的子图 因而天然二分
任意选取的格子诱导出的子图仍是二分图 总能给黑白两侧分别赋相反方向
于是每个格子都是独立的二元选择
答案等于 2h×w2^{ h \times w}2h×w 次方 取模 998244353998244353998244353
注意 h×wh \times wh×w可能会爆 llllll
T2 奇怪的数组
题目大意
给定长度为 nnn 的整数数组 a=(a1,a2,…,an)a=(a_1,a_2,\dots,a_n)a=(a1 ,a2 ,…,an )。需要按原下标顺序将其拆成两条单调不降链：存在标记 ci∈{1,2}c_i\in\{1,2\}ci ∈{1,2} 使得
i<j, ci=cj=1 ⇒ ai≤aj,i<j, ci=cj=2 ⇒ ai≤aj.i<j,\ c_i=c_j=1 \;\Rightarrow\; a_i\le a_j,\qquad i<j,\ c_i=c_j=2 \;\Rightarrow\; a_i\le a_j. i<j, ci =cj =1⇒ai ≤aj ,i<j, ci =cj =2⇒ai ≤aj .
判断是否存在可行划分。多组数据。
题解思路
维护两条链的末尾值 t1,t2t_1,t_2t1 ,t2 （初始为 −∞-\infty−∞），从左到右扫描每个 x=aix=a_ix=ai ：
* 若 x≥t1x\ge t_1x≥t1 且 x≥t2x\ge t_2x≥t2 ，将 xxx 放入末尾更大的那条链，即令 tk←xt_k\gets xtk ←x 其中 k=argmax{t1,t2}k=\arg\max\{t_1,t_2\}k=argmax{t1 ,t2 }；
* 否则若仅有一条满足（如 x≥t1x\ge t_1x≥t1 或 x≥t2x\ge t_2x≥t2 ），放入可行的那条并更新末尾；
* 否则两条都接不上，无解。
该贪心等价于耐心排序在 k=2k=2k=2 时的最少堆判定。时间复杂度 O(n)O(n)O(n)，空间复杂度 O(1)O(1)O(1)。
参考代码
T3 奇怪的数组
题目大意
给定一个初始数组 A={a1,…,an}A=\{a_1,\dots,a_n\}A={a1 ,…,an }。允许无限次执行操作：从当前数组中选取两个数 u,vu,vu,v，把 u AND vu\ \mathbf{AND}\ vu AND v
或 u OR vu\ \mathbf{OR}\ vu OR v 的结果插回数组。给出 qqq 次询问，每次给定一个数 xxx，判断是否存在一系列操作
，使得最终数组中出现 xxx。只需回答 Yes / No。
数值按 64 位带符号整型读入与运算；建议测试数据非负且不超过 260−12^{60}-1260−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解思路
把每个整数视为 0/1 位向量。允许的操作只有逐位的 AND\text{AND}AND 与 OR\text{OR}OR，因此闭包是一个单调布尔代数
。关键在于：要让目标数 xxx 的某一位 jjj 最终为 1，在整个构造过程中所有进行 AND\text{AND}AND 的中间数在位 jjj 上都必须为
1，否则这一位会被清零。
基于此定义
Fj = ⋀ ai: (ai)j=1 ai,F_j \;=\; \bigwedge_{\ a_i:\ (a_i)_j=1}\ a_i, Fj = ai : (ai )j =1⋀ ai ,
即把所有第 jjj 位为 1 的原始数逐位与起来得到的掩码。若没有任何 aia_iai 在位 jjj 上为 1，则位 jjj 不可获得。
对一个查询 x>0x>0x>0，令
M(x) = ⋁ j: (x)j=1Fj.M(x)\;=\;\bigvee_{\,j:\ (x)_j=1} F_j. M(x)=j: (x)j =1⋁ Fj .
这代表在“保证 xxx 的每个所需位始终为 1”的前提下，不可避免地会被携带上的最小附带位集合。于是有如下充要条件：
* 必要性：若最终得到 xxx，则对每个 j∈bits(x)j\in \text{bits}(x)j∈bits(x)，整个过程中所有与运算的参与者在位 jjj 都为 1，因此 xxx
必定包含 FjF_jFj 的所有 1 位，合起来得到 x⊇M(x)x \supseteq M(x)x⊇M(x)。若 M(x)M(x)M(x) 在某些位上多于 xxx，这些多出来的 1
是无论如何都无法“去掉”的，故不可达。
* 充分性：可以先把具有位 jjj 的所有原始数逐位与，构造出每个 FjF_jFj ，再把这些 FjF_jFj 逐位或起来得到 M(x)M(x)M(x)。若 M(x)=xM(x)=xM(x)=x，则确实可达。
对 x=0x=0x=0 的特判：要把所有位都变成 0，只能不断做与运算，极小值是全体按位与
Aall = ⋀i=1nai.A_{\text{all}}\,=\,\bigwedge_{i=1}^n a_i. Aall =i=1⋀n ai .
当且仅当 Aall=0A_{\text{all}}=0Aall =0 时，能得到 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复杂度分析
预处理 FjF_jFj 与 AallA_{\text{all}}Aall 的时间 O(n⋅B)O(n\cdot B)O(n⋅B)，单次查询 O(B)O(B)O(B)，其中 B=61B=61B=61；总复杂度 O((n+q)⋅61)O((n+q)\cdot 61)O((n+q)⋅61)
，空间 O(61)O(61)O(61)。
参考代码
T4
题目大意
给定一个长度为 nnn 的排列。对若干内点 iii（2≤i≤n−12\le i\le n-12≤i≤n−1）给出局部要求：
* P：位置 iii 必须是 {ai−1,ai,ai+1}\{a_{i-1},a_i,a_{i+1}\}{ai−1 ,ai ,ai+1 } 中严格最大；
* V：位置 iii 必须是 {ai−1,ai,ai+1}\{a_{i-1},a_i,a_{i+1}\}{ai−1 ,ai ,ai+1 } 中严格最小；
* .：该处无要求。
求满足全部要求的排列个数，对 998244353998244353998244353 取模。多组数据。
题解思路
1. 快速可行性检查
若存在相邻的两位都被标记且相同（PP 或 VV），必然矛盾，答案为 0。
2. 从三元极值到二元不等式
P 在 iii 处意味着 ai−1<aia_{i-1}<a_iai−1 <ai 且 ai+1<aia_{i+1}<a_iai+1 <ai ；
V 在 iii 处意味着 ai−1>aia_{i-1}>a_iai−1 >ai 且 ai+1>aia_{i+1}>a_iai+1 >ai 。
可将这些三元约束折算到相邻两点之间的“上升/下降”要求，并用数组 ccc 标记到位置 iii 的插入方向：
* 令 c[i]=1c[i]=1c[i]=1 表示新放的 aia_iai 应当大于上一位（下降到当前，上一位更小）；
* 令 c[i]=2c[i]=2c[i]=2 表示新放的 aia_iai 应当小于上一位；
* 无要求则 c[i]=0c[i]=0c[i]=0。
3. 插入式 DP（名次法）
令 fi[j]f_i[j]fi [j] 表示用 {1,…,i}\{1,\ldots,i\}{1,…,i} 构成长度为 iii 的前缀，且第 iii 个数在前 iii 个中的相对名次为第 jjj 小的方案数。
用前缀和 prei[j]=∑k=1jfi[k]pre_i[j]=\sum_{k=1}^j f_i[k]prei [j]=∑k=1j fi [k] 优化转移，初值 f1[1]=1f_1[1]=1f1 [1]=1。
转移到第 iii 位：
* 若 c[i]=1c[i]=1c[i]=1（“前一位 < 当前”）：上一名次 k∈[j,i−1]k\in[j,i-1]k∈[j,i−1]
⇒fi[j]=prei−1[i−1]−prei−1[j−1]\Rightarrow f_i[j]=pre_{i-1}[i-1]-pre_{i-1}[j-1]⇒fi [j]=prei−1 [i−1]−prei−1 [j−1]。
* 若 c[i]=2c[i]=2c[i]=2（“前一位 > 当前”）：上一名次 k∈[1,j−1]k\in[1,j-1]k∈[1,j−1]
⇒fi[j]=prei−1[j−1]\Rightarrow f_i[j]=pre_{i-1}[j-1]⇒fi [j]=prei−1 [j−1]。
* 若无要求：上一名次任意
⇒fi[j]=prei−1[i−1]\Rightarrow f_i[j]=pre_{i-1}[i-1]⇒fi [j]=prei−1 [i−1]。
答案为 ∑j=1nfn[j]=pren[n]\sum_{j=1}^n f_n[j]=pre_n[n]∑j=1n fn [j]=pren [n]。为节省空间，使用滚动数组。
复杂度分析
双层循环 i=1…n, j=1…ii=1\ldots n,\ j=1\ldots ii=1…n, j=1…i，每步 O(1)O(1)O(1) 转移，总时间 O(n2)O(n^2)O(n2)；空间 O(n)O(n)O(n)。
参考代码
T5 题解
题目大意
多次询问“以某点为根的整棵子树里，出现次数 ≥ T 的颜色有多少种”。朴素每次扫子树会超时。
题解思路
核心做法：DSU on tree（重儿子保留）
* 先 DFS 求每个点的子树大小与重儿子。
* 处理某点 u 时：
1. 先递归处理所有轻儿子并清空它们的贡献；
2. 再处理重儿子并“保留”它的贡献；
3. 把 u 自己和所有轻儿子的整棵子树颜色“加回到”重儿子已保留的桶里；
4. 现在桶里正好是 u 的整棵子树，可以回答 u 的所有询问；
5. 若 u 是轻分支，处理完就清空；若是重分支，保留给父亲复用。
这样保证每个节点的颜色只被加入/删除少数次，整体近似 O(nlogn)O(n \log n)O(nlogn)。
如何快速回答“≥ T”
* 维护两层计数：
* cnt[color]：当前桶里该颜色出现了几次；
* freq[t]：出现次数恰为 t 的颜色种数。
* 当某个颜色次数增减时，同时把它在 freq 里的位置移动一格。
* 询问“≥ T”的数量，就是把 freq[T..n] 的和求出来即可。
* 用 Fenwick（树状数组）维护 freq 的前缀和，区间求和就变成两次前缀相减，单次 O(logn)O(\log n)O(logn)。
正确性直觉
* DSU 的“先轻后重、重保留、轻合并”让你在处理 u 时，数据结构里恰好放着 u 子树的全部节点颜色；
* freq 记录“每个出现次数上有多少颜色”，问“≥ T”直接查后缀和，自然正确。
复杂度
* 预处理 DFS：O(n)O(n)O(n)
* DSU 合并 + Fenwick 更新：约 O(nlog2n)O(n \log^2 n)O(nlog2n)
* q 次询问：O(qlogn)O(q \log n)O(qlogn)
代码
T6
题目大意
给定一张有向图，点编号 1…n1\ldots n1…n。你可以从任意点出发行走：
* 若沿边 u→vu\to vu→v 移动，且 u,vu,vu,v 同属同一强连通分量（即同一“环”内），则本次移动无需费用；
* 否则需要支付该边的费用；
* 你有 ppp 张代金券，可用于任意 ppp 条需要付费的边，使其费用记为 0；
* 第一次访问某个点可获得该点的收益，多次访问不重复计收益；
* 可自由选择起点与路径。给定初始资金 www。
问通过合理选择起点、路径与代金券使用策略，最多能获得多少资金。
题解思路
1. 缩点：用 Tarjan 求强连通分量，将同一 SCC 的点合并为一个点，节点权为该 SCC 内所有点收益之和。只有跨 SCC 的边保留其费用。缩点后得到 DAG。
2. DAG 上 DP：允许从任意 SCC 启动，进入即领取该 SCC 的汇总收益；跨边行走时
* 不用券：资金 ←\gets← 资金 −-− 边费 +++ 目标 SCC 汇总收益；
* 用券：资金 ←\gets← 资金 +++ 目标 SCC 汇总收益，券数 −1-1−1。
对 DAG 拓扑顺序进行转移，状态为 (SCC,剩余券数)(\text{SCC}, \text{剩余券数})(SCC,剩余券数)，取最大值。
3. 答案：所有状态中的最大资金。
复杂度分析
Tarjan 缩点 O(n+m)O(n+m)O(n+m)；DAG 上 DP 约为 O((S+E)⋅(p+1))O((S+E)\cdot(p+1))O((S+E)⋅(p+1))，其中 S,ES,ES,E 为缩点后点边数。
参考代码
