「AHOI/HNOI2018」道路问题描述 W 国的交通呈一棵树的形状。W 国一共有 $n − 1$ 个城市和 $n$ 个乡村，其中城市从 $1$ 到 $n − 1$ 编号，乡村从 $1$ 到 $n$ 编号，且 $1$ 号城市是首都。道路都是单向的，本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市，恰有一条公路和一条铁路通向这座城市。对于城市 $i$，通向该城市的道路（公路或铁路）的起点 ...

「AHOI / HNOI2018」排列问题描述 给定 $n$ 个整数 $a_1, a_2, …, a_n(0 \le a_i \le n)$，以及 $n$ 个整数 $w_1, w_2, …, w_n$。称 $a_1, a_2, …, a_n$ 的一个排列 $a_{p[1]}, a_{p[2]}, …, a_{p[n]}$ 为 $a_1, a_2, …, a_n$ 的一个合法排列，当且仅当该排列满 ...

「AHOI / HNOI2018」游戏问题描述 一次小 G 和小 H 在玩寻宝游戏，有 $n$ 个房间排成一列，编号为 $1,2,…,n$，相邻房间之间都有 $1$ 道门。其中一部分门上有锁（因此需要对应的钥匙才能开门），其余的门都能直接打开。 现在小 G 告诉了小 H 每把锁的钥匙在哪个房间里（每把锁有且只有一把钥匙），并作出 $p$ 次指示：第 $i$ 次让小 H 从第 $S_i$ 个房间出 ...

[SDOI2015]道路修建问题描述 某国有2N个城市，这2N个城市构成了一个2行N列的方格网。现在该国政府有一个旅游发展计划，这个计划需要选定L、R两列(L<=R)，修建若干条专用道路，使得这两列之间（包括这两列）的所有2(R-L+1)个城市中每个城市可以只通过专用道路就可以到达这2(R-L+1)个城市中的任何一个城市。这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建， ...

P4029 [CodeChef] COUNTARI问题描述 给定一个长度为N的数组A[]，求有多少对$i, j, k（1\leq i<j<k\leq N）$满足$A[k]-A[j]=A[j]-A[i]$ 输入格式 第一行一个整数$N（N<=10^5）$。 接下来一行N个数$A[i]（A[i]<=30000）$。 输出格式 一行一个整数。 样例输入 10 3 5 ...

【NOI2016】区间问题描述 在数轴上有 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],…,[l_n,r_n]$。现在要从中选出 $m$ 个区间，使得这 $m$ 个区间共同包含至少一个位置。换句话说，就是使得存在一个 $x$，使得对于每一个被选中的区间 $[l_i,r_i]$，都有 $l_i\leq x\leq r_i$。 对于一个合法的选取方案，它的花费为被选中的最长区间长度 ...

【NOI2016】循环之美问题描述 牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。 现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac x y$ 表示，其中 $1\le x\le n,1\le y\ ...

【NOI2016】网格问题描述 跳蚤国王和蛐蛐国王在玩一个游戏。 他们在一个 $n$ 行 $m$ 列的网格上排兵布阵。其中的 $c$ 个格子中 $(0 \leq c \leq nm)$，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。 我们称占据的格子有公共边的两只跳蚤是相邻的。 我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。 现在，蛐蛐国王希望，将某 ...

【NOI2016】优秀的拆分问题描述 如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。例如，对于字符串 $ \texttt{aabaabaa} $ ，如果令 $\text{A}=\texttt{aab}$，$\text{B}=\texttt{a}$，我们就找到了这个字符串拆 ...

「NOI2017」蔬菜问题描述 小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。在蔬菜仓库中，共存放有 $n$ 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。在计算销售蔬菜的收益时，每销售一个单位第 $i$ 种蔬菜，就可以获得 $a_i$ 的收益。特别地，由于政策鼓励商家进行多样化销售，第一次销售第 $i$ 种蔬菜时，还会额外得到 $s_i ...