Posts by hostmaster

题意 有一张 $2 \times n$ 的网格图，你要从左上角 $\left(1, 1\right)$ 走到右下角 $\left(2, n\right)$。每条边有边权，并且有额外的 $m$ 条限制。每条限制形如：给定 $i, j, c$，如果同时走了 $\left(1, i\right)$ 到 $\left(1, i + 1\right)$…

概述 某些问题使用比较暴力的方法也可以通过，这种解法的复杂度均摊之后是对的。分析方式一般需要用到势能分析法。 例子 1 给定长度为 $n$ 的数组 $a_i$（$a_i \leq V$），$m$ 次操作。 操作 1：区间对给定数 $x$ 取模。 操作 2：查询区间和。 操作 2：单点加。 $1 \leq n, m \leq 10^5, V \leq 10^9$…

题意 给出一个 $n \times n$ 的黑白棋盘。你要处理 $m$ 次修改，每次修改给出一个点 $\left(x, y\right)$，表示你要把 $\left(x, y\right)$ 的颜色反转。每次修改后输出有多少个白色连通块和有多少个黑色连通块（四联通）。 $1 \leq n \leq 200, 1 \leq m \leq 10^4$…

题意 给定一个长度为 $n$ 的排列 $a_i$，问是否存在 $1 \leq i < j < k \leq n$，使得 $a_j = \dfrac{a_i + a_k}2$ 题解 首先，枚举 $j$，我们只需要判断是否存在一个 $d$，使得有一个 $a_j - d$ 在 $j$ 左边，并且有一个 $a_j + d$ 在 $j$ 右边。 我…

概述 快速傅里叶变换（Fast Fourier Transform, FFT）可以在 $\Theta\left(n \log n\right)$ 的时间内计算多项式乘法。 但 FFT 的用处远不止于此。 多项式 一个多项式 $F\left(x\right) = a_0 + a_1x + a_2x^2 + \cdots$。 其中，$a_i$…

前置知识 FFT 快速傅里叶变换 概述 FFT 可以在 $\mathcal O\left(n \log n\right)$ 解决几乎所有字符串匹配问题。但在解决复杂字符串匹配问题时，可能要做 $2$ 到 $3$ 次 FFT 和 IFFT。 普通字符串匹配 给定 $S$ 和 $T$，长度分别为 $m$ 和 $n$。求 $S$ 在 $T$ 中…

上午 CSP-J 长沙理工大学好像有一个机房没断网，导致题目泄露了。。。 下午考前都没开网，导致没法下载 VSCode 的 C++ 插件。。。 甚至还上了信号屏蔽。。。 题目依旧无法解压。。。又是去别的机房拿 U 盘把题目拷过来的。。。 延迟 $20$ 分钟，14: 50 才开考。。。真无语。。。 首先开 T1。直接暴力枚举。 发现不能不…

这个游记是在我考试时候写的。 8: 10 就到了考场 座位右边居然正是 yq 同学！ 居然没断网。我直接把 VSCode 的 C++ 插件给下载了。 顺便还下了个颜色主题（ 然后跟前年一样，去洛谷上签了个到。 8: 30 开考，解压不了压缩包，卡了 30 分钟，老师说考试延长 30 分钟。 好像是因为压缩包是 Windows 里压的，Li…

题意 给定 $n$ 个数，编号为 $1$ 到 $n$。$m$ 次操作，每次操作给定一个 $x$，询问编号最小的大于等于 $x$ 的数。若没有则输出 $0$，若有则输出位置，并将该位置上的数减去 $x$。 $1 \leq n, m \leq 2 \times 10^5$ 题解 这里提供两个做法。 做法 1 大力分块。每次暴力循环遍历每个块，…

题意 有 $n$ 个砝码，编号为 $1$ 到 $n$。编号大的砝码一定比编号小的砝码重。 做 $n$ 操作，每次操作是把某个还没放在天平上的砝码放到天平的左边或者右边。问能否确定天平两边重量关系。 题解 定义 $l_i$ 为天平左边中，编号大于等于 $i$ 的砝码个数，$r_i$ 为天平右边中，编号大于等于 $i$ 的砝码个数。 左边比右…