OI
「NOI2015」寿司晚宴-状压dp
· ✏️ 1428 words · ☕ 3 mins read

为了庆祝 $NOI$ 的成功开幕,主办方为大家准备了一场寿司晚宴。小 $G$ 和小 $W$ 作为参加 $NOI$ 的选手,也被邀请参加了寿司晚宴。

在晚宴上,主办方为大家提供了 $n−1$ 种不同的寿司,编号 $1,2,3,⋯,n-1$ ,其中第种寿司的美味度为 $i+1$(即寿司的美味度为从 $2$ 到 $n$ )。

现在小 $G$ 和小 $W$ 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当:小 $G$ 品尝的寿司种类中存在一种美味度为 $x$ 的寿司,小 $W$ 品尝的寿司中存在一种美味度为 $y$ 的寿司,而 $x$ 与 $y$ 不互质。

现在小 $G$ 和小 $W$ 希望统计一共有多少种和谐的品尝寿司的方案(对给定的正整数 $p$ 取模)。注意一个人可以不吃任何寿司。


「NOI2009」诗人小G-动态规划+决策单调性
· ✏️ 996 words · ☕ 2 mins read

小 $\text{G}$ 是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。

一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小 $\text{G}$ 给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小 $\text{G}$ 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小 $\text{G}$ 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方,而一个排版的不协调度为所有行不协调度的总和。

小 $\text{G}$ 最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。


「APIO2014」序列分割-动态规划-斜率优化
· ✏️ 670 words · ☕ 2 mins read

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次:

  • 选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
    • 选择两个相邻元素把这个块从中间分开,得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。


「NOI2012」魔幻棋盘-差分+树套树
· ✏️ 1480 words · ☕ 3 mins read

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘,它是一个 $N$ 行 $M$ 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列(行与列均从 $1$ 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:

  1. 询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。

  2. 修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 $19930324$ 次询问后会得到一个惊喜噢!”。小 Q 十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 $100%$ 的正确率。

为了简化问题,你的程序只需要完成棋盘守护者的 $T$ 次操作,并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。


「NOI2012」随机数生成器-矩阵快速幂
· ✏️ 286 words · ☕ 1 mins read

给定正整数 $n,m,a,c,X[0],g$ ,求按照 $X[n+1] = (a X[n] + c) \bmod m$ 生成出的第 $n$ 项 $X[n] \bmod g$ 的值。

数据范围: $n,m,a,c,X[0] \leq 10^{18}$


「APIO2008」免费道路-生成树+并查集
· ✏️ 496 words · ☕ 1 mins read

给定一个 $n$ 个点,$m$ 条边的无向图,每条边有两种权值: $0$ 或者 $1$ 。

先询问能不能找出一个生成树,使得其中恰有 $k$ 条 $0$ 边,若存在,输出任意一个方案,否则输出 no solution


「SHOI2016」随机序列-线段树
· ✏️ 919 words · ☕ 2 mins read

你的面前有 $n$ 个数排成一行,分别为 $a_1,a_2,…,a_n$ 。你打算在每相邻的两个 $a_i$c和 $a _ {i+1}$ 间都插入一个加号、减号或者乘号。那么一共有 $3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了,所以你还打算支持一个修改操作,可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗?注意,修改是永久的,也就是说每次修改都是在上一次修改的基础上进行,而不是在最初的表达式上进行。


「NOI2010」航空管制-拓扑排序
· ✏️ 756 words · ☕ 2 mins read

假设目前被延误航班共有 $n$ 个,编号为 $1$ 至 $n$ 。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。

起飞序列还存在两类限制条件:

  • 第一类(最晚起飞时间限制):编号为 $i$ 的航班起飞序号不得超过 $k_i$ ;

  • 第二类(相对起飞顺序限制):存在一些相对起飞顺序限制 $(a, b)$ ,表示航班 $a$ 的起飞时间必须早于航班 $b$ ,即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。

小 $\text{X}$ 思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。


「POI2012」Cloakroom-类背包dp
· ✏️ 605 words · ☕ 2 mins read

有 $n$ 件物品,每件物品有三个属性 $a[i], b[i], c[i]$ , $(a[i] < b[i])$ 。

再给出 $q$ 个询问,每个询问由非负整数 $m$ , $k$ , $s$ 组成,问是否能够选出某些物品使得:

  • 对于每个选的物品 $i$ ,满足 $a[i] \leq m$ 且 $b[i]>m+s$ 。

  • 所有选出物品的 $c[i]$ 的和正好是 $k$ 。


「ZJOI2012」小蓝的好友-Treap
· ✏️ 1673 words · ☕ 4 mins read

简单版题意:

给定一个 $R \times C$ 的矩形,在其中 $N$ 个位置有随机生成的资源点。现在请你求出在所有的子矩形中,至少包含一个资源点的矩形数量。


「POI2014」Salad Bar-瞎搞
· ✏️ 503 words · ☕ 2 mins read

有一个长度为 $n$ 的字符串,每一位只会是 $\text{p}$ 或 $\text{j}$ 。求一个最长子串,使得不管是从左往右还是从右往左取,都保证每时每刻已取出的 $\text{p}$ 的个数不小于 $\text{j}$ 的个数。


「BZOJ4278」[ONTAK2015]Tasowanie-后缀数组
· ✏️ 491 words · ☕ 1 mins read

给定两个数字串 $A$ 和 $B$ ,通过将 $A$ 和 $B$ 进行二路归并得到一个新的数字串 $T$ ,请找到字典序最小的 $T$ 。


「POI2013」Price List-图论
· ✏️ 1109 words · ☕ 3 mins read

给定一个 $n$ 个点,$m$ 条边的无向联通图,每条边的权值均为 $a$。

原图所有满足 $u$ 节点和 $v$ 节点间最短路为 $2 \times a$ 的点对 $(u,v)$ 间建立一条无向边,边的权值均为 $b$。

给定一个起始节点$k$,求在上述操作后,$k$到所有节点的最短路径。