祝馀宫

题面：FJ’s Favorite Permutation B题目描述Farmer John 有一个长为 $N$（$2\le N\le 10^5$）的排列 $p$，包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而，Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 $p$。为了不至于太过残忍，FN 写了一些能够帮助 FJ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时，FN 会执行以下操作： 令 $p$ 的剩余元素为 $p_1^\prime,p_2^\prime,\ldots,p_n^\prime$， 如果 $p_1^\prime>p_n^\prime$，他写下 $p_2^\prime$ 并从排列中删除 $p_1^\prime$。 否则，他写下 $p_{n−1}^\prime$ 并从排列中删除 $p_n^\prime$。 最终，Farmer Nhoj 将按顺序写下 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$。给定 $h$，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 $p$，或者判断 ...

题面：[COTS 2018] 直方图 Histogram题目背景译自 Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,1G}$。 题目描述给定笛卡尔坐标系中的直方图，宽度为 $n$，第 $i$ 格的高度为 $h_i$。也就是说，对于 $\forall 1\le i\le n$，第 $i$ 格所占矩形的顶点坐标分别为 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$。 给定正整数 $p$，求出满足以下条件的矩形的数量： 矩形的四个顶点的坐标均为整数； 矩形有一条边在 $x$ 轴上； 矩形完全位于直方图内部（可以与边界相切）； 矩形的面积至少为 $p$。 输入格式第一行，两个正整数 $n,p$。 第二行，$n$ 个正整数 $h_1,h_2,\ldots,h_n$。 输出格式输出一行一个整数，表示答案。 样例 #1样例输入 #1126 91 4 4 5 2 3 样例输出 #113 样例 #2样例输入 #21210 53 6 1 3 2 1 5 3 4 2 样例输出 #21 ...

题面：[TJOI2011] 树的序题目描述众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲： 空树中加入一个键值 $k$，则变为只有一个结点的二叉查找树，此结点的键值即为 $k$。 在非空树中插入一个键值 $k$，若 $k$ 小于其根的键值，则在其左子树中插入 $k$，否则在其右子树中插入 $k$。 我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为 $n$ 的生成序列，先比较第一个插入键值，再比较第二个，依此类推。 输入格式第一行，一个整数 $n$，表示二叉查找树的结点个数。第二行，有 $n$ 个正整数 $k_1, k_2, \cdots,k_n$，表示生成序列，简单起见，$k_1 \sim k_n$ 为一个 $1$ 到 $n$ 的排列。 输出格式一行，$n$ 个正整数，为能够生成同样二叉查找树的所有生成序列中最小的。 样例 #1样例输入 #11241 3 4 2 样例输出 #111 3 2 4 提示数据范围及约定 对于 $20\%$ 的数据， $1\l ...

题面：Redundant Paths G大秦为你打开题目传送门 题面翻译为了从 $F(1 \le F \le 5000)$ 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。 每对草场之间已经有至少一条路径．给出所有 $R\ (F-1 \le R \le 10000)$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。 题目描述In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the re ...

题面：[POI2008] BLO-Blockade大秦为你打开题目传送门 题面翻译B 城有 $n$ 个城镇（从 $1$ 到 $n$ 标号）和 $m$ 条双向道路。 每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。 把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。 请你对于每个节点 $i$ 求出，把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。 【输入格式】 第一行包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示城镇 $a$ 和 $b$ 之间存在一条道路。 【输出格式】 输出共 $n$ 行，每行输出一个整数。 第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。 【数据范围】 $n\le 100000$，$m\le500000$。 题目描述There are exactly $n$ towns in By ...

题面：[ZJOI2004] 嗅探器大秦为你打开题目传送门 题目描述某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。 蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。 但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。 现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？ 输入格式输入文件的第一行一个整数 $n$，表示蓝军网络中服务器的数目。 接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i,j$ 表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在双向连接。 服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a,b$ 分别表示两个中心服务器的编号。 输出格式输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。 样例 #1样例输入 #112345678952 12 51 45 32 35 10 04 2 样例输出 #111 ...

题面：[HNOI2012] 矿场搭建大秦为你打开题目传送门 题目描述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。 请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。 输入格式输入文件有若干组数据。 每组数据的第一行是一个正整数 $N\ (N \le 500)$，表示工地的隧道数。 接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$，表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。 输入数据以 $0$ 结尾。 输出格式对于每组数据，输出一行。 第 $i$ 行组数据以 Case i: 开始。 其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。 输入数据保证答案小于 $2^{64}$。输出格式参照以下输入输出样例。 样例 # ...

题面：间谍网络大秦为你打开题目传送门 题目描述由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。 我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 $n$ 个间谍（$n$ 不超过 $3000$），每个间谍分别用 $1$ 到 $3000$ 的整数来标识。 请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。 输入格式第一行只有一个整数 $n$。 第二行是整数 $p$。表示愿意被收买的人数，$1\le p\le n$。 接下来的 $p$ 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个 ...