查看源代码：
GZOI2025-1.md

---
title: GZOI 2025 两日游 · 其一
createTime: 2025/9/13
categories:
    - IT
tags:
    - OI
    - OI-travel-notes
---

## 写在前面

没有报高联，以为轻松了，但是 GZOI 是什么意思？  
广州市中学生数学与科学联赛（信息学）怎么不算一种高联呢（笑）

主办方还挺好的，不仅有饭票，还送了水果和面包。

以及，今天忘记带笔了（这在其他的竞赛里面显然是不会忘的），结果没法打草稿，找监考老师借了一支。（明天不会了）

但是必须吐槽的是系统很烂，是旧版的 win7，复制粘贴很难受，专武 Dev C++ 还歪了，`fc` 还去不了尾随空格（我记得去年 NOIP 可以去）。

## T1

:::note
有一个序列 $\{a_i\}$ 以及 0-1 序列 $\{t_i\}$，求 $x \in [-10^9, 10^9] \cap \mathbb{Z}$ 时，序列 $\{a_i + x t_i\}$ 前缀最小值个数的出现次数。
:::

首先我们知道对 $t_i=0,1$ 的项分别取前缀最小值，显然不会改变答案。

发挥一下 *Olympaid in Imagination* 的想象力，可以想象出两个点集上下平移，相互穿过的场景。

想象出这一个动态过程之后，可以顺理成章的对答案做一次差分，即考虑答案随 $x$ 移动时的变化。

因为我们之前求过前缀最小值，答案出现变化当且仅当一个值穿越到了在它下标之前的前缀最小值（注意只有 $t_i$ 不同的才能互相穿越），把不超过 $n$ 次穿越（每个点最多一次）全部找出来，就可以得到差分。

然后通过特殊值把答案重建出来即可。

另外，不开 **long long** 见祖宗。（虽然我不知道为什么会见）

## T2

:::note 题意
给定一个长度为 $n$ 的序列 $\{a_i\}$，求子序列求和中出现次数不小于 k 的和。

$n \le 200, a_i \le 10^4, k \le 7$，时间限制 $0.5 \text{s}$。
:::
​
在 set 上​打了个 DP。

​后知后觉地发现自己的解法没有把超过 $k$ 的值变成 $k$，溢出了。结果喜提 $\color{red} \textbf{WA 0}$。

### T2 正解

​注意已经超过 $k$ 的就没必要再更新了。由于我们需要处理“不为 $0$ 的位置 $+ a_i$”和“不超过 $k$ 的位置”的交集，需要使用 bitset。

此时由于每次转移都不为 $0$，DP 值必定增加，于是一个和最多被访问 $k$ 次。时间复杂度 $O\left( \dfrac{n \sum a}{w} + k \sum a \right)$，能过。

## T3

:::note ​题意

给定一棵树，点有点权。有三种操作：

0. 修改点权
1. 把一条路径上的点编号及其权值反转
2. 对于一条有向路径上的点权序列 $a_1, a_2, ..., a_k$，  
   求 $(((a_1 \mathop{\text{op}_1} a_2) \mathop{\text{op}_2} a_3) ... ) \mathop{\text{op}_{k-1}} a_k ,\  \text{op}_i\in\{+,\times\}$ 的最大值。

:::

先看看序列上操作 2 怎么做。对于 $a \operatorname{op} b$ 来说，只有 $a=1 \lor b=1$ 时才使用 $+$，否则使用 $\times$。

​考虑两端还是太复杂了。不难发现 $\displaystyle\max_{\text{op} \in \{+, \times\}} a \operatorname{op} b$ 一定大于 $1$，因此单独把前两项拆出来。

​之后采用哪种符号只跟 $b$ 有关，可以把点权抽象成线性函数

$$
\begin{cases}
f_i (x) = x+1, &a_i=1 \\
​f_i (x) = a_i x, &\text{otherwise}
\end{cases}
$$

​函数的复合满足结合律，使用线段树维护。在树上再加一个树链剖分，即可过没有操作 1 的子任务。

​有区间翻转，这种东西一般是用平衡树的，但是我不会。

然后线段树还调了俩小时，还是写挂了。这就是整天写注意力神题，不练板子的代价。

## T4

:::note 题意
求一个序列中至少包含一个最长上升子序列的子序列个数。保证数据随机。
:::

​神秘随机，逆天题目，大病期望。

​我不会。正解用了期望来算复杂度，但是连讲题的也没写证明。