博主无聊时会出一些题目，难度不等。欢迎大家来玩！

注意：题目前带 * 的表示还没造完 / 已经投给某个比赛了，所以暂时不能查看。

「TopCoder 11351」The Cow Div One

题意

给定整数 $N, K$，问从 $0, 1, \cdots, N - 1$ 中选择 $K$ 个不同的数，满足它们的和为 $N$ 的倍数的方案数。

数据范围：$N \le 10^9, K \le 10^3$。

「Nowcoder 201916」简单字符串

题意

对于字符串 $s$ 和整数 $k$，定义 $f(s, k)$ 表示将 $s$ 划分成不超过 $k$ 段后字典序最大的段字典序最小是多少。

给定长度为 $n$ 的字符串 $S$。$q$ 次询问 $l_i, k_i$，你要求出 $a_i, b_i$，表示 $f(S[l_i \ldots n], k) = S[a_i \ldots b_i]$。你要在满足 $a_i \ge l_i$ 的同时最小化 $a_i$。

数据范围：$n, q \le 10^5$。

JOI 2020 春季合宿结束了。感想：dls、黄队、徐队、Dls 太神了！

汉堡肉

「JOISC 2020 Day1 T2」汉堡肉

思路：

我们找到左边界最靠右的、右边界最靠左的、下边界最靠上的、上边界最靠下的矩形。容易发现对于左边界最靠右的矩形，它上面的竹签的 x 坐标一定可以调整到左边界处（也就是可以强制它插在左边界的那条线段上）。其他方向同理。

Bombs

「Codeforces 1326E」Bombs

题意：

给定排列 $p_{1 \ldots n}$，假设某些位置有炸弹。考虑一开始有空集 $A$，然后对于 $1$ 到 $n$ 的每个 $i$：

• 在 $A$ 中加入 $p_i$。
• 如果位置 $i$ 有炸弹，那么删掉 $A$ 中的最大元素。

再给定排列 $q_{1\ldots n}$。你要对于每个 $i$ 求出：假设位置 $q_{1 \ldots i - 1}$ 有炸弹，那么执行上述操作后 $A$ 的最大元素是什么。

数据范围：$n \le 3 \times 10^5$。

题意

「Codeforces 700E」Cool Slogans

给定字符串 $S$，求最大的 $k$，使得存在一个字符串序列 $T_1, T_2, \cdots T_k$，满足所有元素都是 $S$ 的子串，并且 $T_{i - 1}$ 至少在 $T_i$ 中出现了两次。

数据范围：$\vert S \vert \le 2 \times 10^5$。

比赛地址：「ZROI 557」2020 省选十联测 Day10

评价：后两道题目很有趣，300iq nb!

基本概念

线性规划问题：

一般的线性规划是指这样一类问题：有 $n$ 个非负实数变量 $x_1, x_2, \cdots, x_n$，需要满足 $m$ 个限制，第 $i$ 个限制形如 $\sum_{j = 1}^{n} a_{i, j} x_j \le b_i$。要求出一组解，满足 $\sum_{j = 1}^{n} c_j x_j$ 最大。这里的 $a_{i, j}, b_i, c_j$ 都是实数，不一定非负。把这些限制写成式子就是：

比赛地址：「ZROI 552」2020 省选十联测 Day9

评价：三道题目都很有趣，区分度也很高。徐队又把我吊打了（悲）

题目描述

「UOJ 207」共价大爷游长沙

给定 $n$ 个点的树，还有一个集合 $S$ 初始为空。依次执行 $m$ 个操作，操作共四种：

• 1 x y u v：删去边 $(x, y)$，加入边 $(u, v)$。保证操作后还是树。
• 2 x y：在 $S$ 中加入链 $x \to y$。
• 3 x：在 $S$ 中删去第 $x$ 次加入的链。
• 4 x y：询问是否所有 $S$ 中的链都经过边 $(x, y)$。

数据范围：$n \le 10^5, m \le 3 \times 10^5$。