题目

链接

[ZJOI2007]棋盘制作

题意简述

给定一个长度为 $n \ (n <= 2e3) \ * \ m \ (m <= 2e3)$ 的矩形，求黑白相间的最大正方形和矩形。

题目

链接

[CTSC2014]企鹅QQ

题意简述

给定 $n \ (n <= 3e4)$ 个长度为 $l \ (l <= 2e2)$ 的字符串，求有多少对字符串等长且恰好只有一位不同。

题目

链接

[SHOI2009]会场预约

题意简述

编写一个数据结构支持 $2$ 种 $n \ (n <= 200000)$ 次操作。

• 删除与 $(begin \ , \ end)$ 有交集的区间，插入并输出删除数。
• 查询区间数。

题目

链接

[NOIp2013]火柴排队

题意简述

有两列共 $n \ (n <= 100000)$ 支火柴

两列火柴之间的距离定义为：

通过交换使得两列火柴之间的距离最小，出这个最小交换次数对 99,999,997 取模。

题目

链接

[HNOI2004]打鼹鼠

题意简述

在一个 $n * n \ (n <= 1000)$ 的网格中。你可以控制一个机器人来打 $m \ (m <= 10000)$ 只鼹鼠，如果 $i$ 时刻鼹鼠和机器人处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能向相邻的网格移动一格或停留在原地不动。

机器人不能走出整个 $n * n$ 的网格。可以自由选定机器人的初始位置。

求在这一段时间内打死尽可能多的鼹鼠的数目。

题目

链接

[AHOI2012]信号塔

题意简述

求 $n \ (n <= 1000000)$ 个点的最小圆覆盖。

题目

链接

[HNOI2010]弹飞绵羊

题意简述

地上沿着一条直线摆着 $n (n <= 200000)$ 个装置，每个装置设定初始弹力系数 $k_{i}$ ，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_{i}$步，达到第 $i + k_{i}$ 个装置，若不存在第 $i + k_{i}$ 个装置，则绵羊被弹飞。

要支持 $m (m <= 100000)$ 次 $2$ 种操作。

• 查询从 $x$ 出发后几次被弹飞。
• 将 $x$ 处的弹力系数改为 $y$ 。

题目

链接

[SDOI2008]洞穴勘测

题意简述

使 $n \ (n <= 10000)$ 个节点的一棵树支持 $m \ (m <= 200000)$ 3种操作：

• 连接 $(u, v)$ 。
• 断开 $(u, v)$ 。
• 查询 $(u, v)$ 是否联通。

题目

链接

[SCOI2008]配对

题意简述

有一个 $n \ (n <= 100000)$ 对整数需要配对。

所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。

题目

链接

[HAOI2009]逆序对数列

题意简述

求 $n \ (n <= 1000)$ 的全排列中逆序对个数为 $k \ (k <= 1000)$ 的数目。

题目

链接

[HAOI2007]理想的正方形

题意简述

有一个 $n * m \ (n, \ m <= 1000)$ 的整数组成的矩阵。

找出一个 $k * k \ (k <= 100)$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

题目

链接

[HNOI2003]消防局的设立

题意简述

给出一棵节点数为 $n \ (n <= 1000)$ 的树，每条边长度为 $1$ 。

一次操作作用于一个节点，并将距此节点 $dist <= 2$ 的节点染色，求将整棵树染上颜色的最小次数。

题目

链接

CF962D Merge Equals

题意简述

给出一个长度为 $n \ (2<= n <= 150000)$ 的数组， 数组内元素 $a{i} \ (1 <= a{i} <= 1e9)$ 。

每次操作将数组内两个相同的最小的最靠左的元素取出，并将左边的合并到右边，直到不能操作为止，输出最后的数组。

例：
$[1, 1, 3, 1, 1]~\rightarrow~[2, 3, 1, 1]~\rightarrow~[2, 3, 2]~\rightarrow~[3, 4]$

题目

链接

[SCOI2009]生日礼物

题意简述

有一条纸带上挂着 $n \ (n <= 1000000)$ 个小球，小球有 $k \ (k <= 60)$ 种颜色。
s
找出一个最小的包含所有颜色的区间。

题目

链接

[SCOI2011]糖果

题意简述

有 $n \ (n <= 100000)$ 个点， $k \ (k <= 100000)$ 种关系。

有 $5$ 种关系类型。

• $$W_{A} == W_{B}$$
• $$W_{A} < W_{B}$$
• $$W_{A} >= W_{B}$$
• $$W_{A} > W_{B}$$
• $$W_{A} <= W_{B}$$

找出满足关系的最小总权值。