Posts by hostmaster

Problem Statement There are $n$ nodes, and you are given an array $t$ of length $n$, where $t_i$ denotes that when you are at node $i$, you can teleport to node $t_i$. Yo…

题意 有一个未知的排列 $a$，其长度为 $n$，你通过进行不超过 $4n$ 次交互将排列排序。 给出 $l, r$，将 $a_l, a_{l + 1}, \ldots, a_r$ 翻转，即变成 $a_r, a_{r - 1}, \ldots, a_l$。操作完成后返回当前数组逆序对个数。 题解 考虑翻转 $\left[l, r\right]$…

Problem Statement You are given an array $a$ of length $n$. Let $f\left(x, y\right) = \left(x \bmod y\right) + \left(y \bmod x\right)$. For each $i \in \left[1, n\right]$…

线性递推 我们说明，如果一个生成函数 $\frac{P\left(x\right)}{Q\left(x\right)}$，满足 $\deg\left(P\left(x\right)\right) < \deg\left(Q\left(x\right)\right)$，那么，该封闭形式所对应的原函数 $A\left(x\right)$ 是一…

题目 题解 考虑一个计算量 $nm$ 的 DP，设 $f_{i, j}$ 表示能否让 $x_i$ 与 $y_j$ 匹配。转移为 $$f_{i, j} = \left(x_i < y_j\right) \land \left(f_{i - 1, j} \vee f_{i, j - 1} \vee f_{i - 1, j - 1}\right)$$…

16:9 的显示器，用的是 4:3 分辨率，锁定了改不了，愤怒。 提前 20 分钟进考场，赛前尝试改分辨率，尝试 10 min 以失败告终。然后趁没开始打了个线段树。 t1 发现是要求一个最小链覆盖，转最长反链 7 min 做完了。 t2 发现是个小模拟，50 min 差不多做完了。加速度公式也没看，直接看的样例解释里面的那个算法。 t3…

题意 有 $n$ 栋楼，第 $i$ 栋楼的高度为 $H_i$。在坐标轴上用一条 $\left(i, 0\right)$ 到 $\left(i, H_i\right)$ 的线段表示。称第 $i$ 栋楼可以被看到，当且仅当从 $\left(0, 0\right)$ 到 $\left(i, H_i\right)$ 的线段上，与 $\left[1, i - 1\right]$…

This post is password protected. Enter the password to read it.

题意 给定的 $n$ 个数 $a_i$。 求 $\operatorname{lcm}\left(a_1, a_2, \ldots, a_n\right) \bmod 998244353$。 $1 \leq n \leq 5000, 1 \leq a_i \leq 10^{18}$ 题解 我们设 $$f_i = \operatorname{lcm}\left(a_1, a_2, \ldots, a_i\right) = b_1b_2 \cdots b_i$$…

概述 摩尔投票算法用于求解区间中出现次数严格大于 $len / k$ 的数。 普通摩尔投票 普通摩尔投票只能解决 $k = 2$ 时的问题。 我们先考虑一个暴力的方法。维护当前答案 $x$，和 $x$ 的权值 $c$。依次扫描 $l$ 到 $r$ 的每个数。 假设当前数为 $a$： 如果 $x = a$，那么将 $c$ 加上 $1$ 否则…