题目描述   Given , find the value of .  It can be proved that the value is a rational number .  Print the result as .  输入描述   The input consists of several test cases and is terminated by end-of-file.  Each test case contains an integer .  . The number of test cases does not exceed .  输出描述 For each test...

题目描述   For a string , Bobo defines , which is repeats for infinite times, resulting in a string of infinite length.  Bobo has two strings and . Find out the result comparing and in lexicographical order.  You can refer the wiki page for further information of Lexicographical Order.  输入描述   The input...

题目描述   Given three concentric circles whose radiuses are respectively, and are the moving points on the given three circles respectively. Determine the expected area of .  输入描述   The first line contains one integer , denoting the number of test cases.  For each test case, one line containing three i...

题目描述   Given a sequence of size and a sequence of size , determine the number of subintervals called of size in satisfying , .  输入描述   The first line contains two integers , . The second line contains integers , denoting the sequence .The third line contains integers , denoting the sequence .  输出描述 ...

题目描述   Bobo has a network of nodes and arcs. The -th arc goes from the -th node to the -th node, with cost .  Bobo also asks questions. The -th question is specified by two integers and , which is to ask the minimum cost to send one unit of flow from the -st node to the -th node, when all the edges ...

D. Quadratic Form 题目描述   Bobo has a positive-definite matrix and an -dimension vector . He would like to find where , and is maximum.  It can be shown that , which is rational.  Find the value of .  输入描述   The input consists of several test cases terminated by end-of-file.  The first line of each te...

分析 由于石子摆在圆形操场的四周，因此 堆石子会摆放成一个环，于是不妨将 堆石子复制一份，使得 。定义 为合并区间 内石子获得的最小得分，有状态转移方程 。同理，定义 为合并区间 内石子获得的最大得分，有状态转移方程 。所求即为 和 。  代码 #include<algorithm> #include<cstring> #include<iostream> #include<cstdio> #define N 302 using namespace std; int dp_min[N][N]; int dp_max[N][N]; int n; i...

题目描述 设有N堆沙子排成一排，其编号为 。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这 堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有 堆沙子分别为 ，我们可以先合并 堆，代价为 ，得到 ， 又合并 堆，代价为 ，得到 ，再合并得到 ，总代价为 ，如果第二步是先合并 堆，则代价为 ，得到 ，最后一次合并代价为 ，总代价为 。问题是：找出一种合理的方法，使总的代价最小。输出最小代价。  输入描述 第一行一个数 表示沙子的堆数 。第二行 个数，表示每堆沙子的质量...

题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。  输入描述  行，若干个整数（个数 ）。  输出描述  行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹...

分析 设 为从 走到点 的路径数。对于没有任何状态的格点图，显然有状态转移方程 ；然而在题给的图中，有一些点是不可走的，对于一个被马控制的点 有 。综上所述，需要预处理出马可以控制的 个点，定义 ，若 被马控制， 为真。有状态转移方程  接下来分析边界条件，即确定 和 。由于过河卒只能向下和向右走，因此对于边界上某一点，走到这个点上的路径数至多为 ；若沿着边界一直走，碰到一个被马控制的点，那么边界上剩下的点都不可达，路径数为 。  代码 #include<iostream> #define N 30 using namespace std; long long dp[N][N]; ...

分析 首先，要让最少的同学出列，就等价于让尽量多的同学留在队伍中。观察到合唱队形满足 ，在合唱队形中，以第 个同学为分界点（分界点即为最高点），从 到 递增，从 到 递减。设原队形中第 个同学的身高为 。假设我们选取第 个同学作为合唱队形的最高点，那么要使尽量多的同学留在队伍中，合唱队形左边应该是 数组中从左到右以 结尾的 ；右边应该是 数组中从右到左以 结尾的的 。我们可以预处理出 数组中正向和逆向的最长上升子序列长度，然后枚举合唱队形的最高点，就可以得到最多能有多少同学留在队伍中，也就能知道最少需要几位同学出列。设 为从左到右以 结尾的 长度， 为从右到左以 为结尾的 长度。有状态转移方程...

分析 设经过操作后所有成绩全部公布的时间为 ，所获得的不愉快度为 。当 很小，那么大部分同学都能在其能忍受的时间 内知晓成绩，但是由于 很小， 的情况是很多的，为了使所有科目的成绩都在时间 内出来，就需要将大于 的 减小，那么就会因为多次修改 获得较多的不愉快度，因此 是比较大的；当 很大，虽然不用怎么修改 ，但是 会超出大部分同学的时限 ，因此 也是比较大的。根据以上分析， 应当是一个下凸的单峰函数，可以用三分法找到极小值点。接下来分析如何计算 的值。假设强制所有成绩全部公布的时间为 ，将 分为两部分，等待成绩公布获得的不愉快度，以及修改 使得对于任意 有 所获得的不愉快度。等待成绩公布获得...

NC15446 的物品 [](https://ac.nowcoder.com/acm/problem/15446)   题目描述  学长现在手里有 个物品，这 个物品的重量和价值都告诉你，然后现在让你从中选取 个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的 个物品的总价值和总重量的比值）。  输入描述 输入第一行一个整数 。接下来有 组测试数据，对于每组测试数据，第一行输入两个数 和 。接下来有 行，每行两个是 和 ，代表这个物品的重量和价值。  输出描述 对于每组测试数据，输出对应答案，结果保留两位小数。  示例1 输入13 22 25 32 1输出0.75  说明 ...

题目描述 小阳手中一共有 个贝壳，每个贝壳都有颜色，且初始第 个贝壳的颜色为 。 现在小阳有 种操作。 ：给 区间里所有贝壳的颜色值加上 。 ：询问 区间里所有相邻贝壳颜色值的差（取绝对值） 的最大值（若 输出 ）。 ：询问 区间里所有贝壳颜色值的最大公约数。  输入描述 第一行输入两个正整数 ，分别表示贝壳个数和操作个数。第二行输入 个数 ，表示每个贝壳的初始颜色。第三到第 行，每行第一个数为 ，表示操作编号。接下来的输入的变量与操作编号对应。  输出描述 共 行，对于每个询问（操作 和操作 ）输出对应的结果。  示例1 输入5 62 2 3 3 31 2 3 32 2 43 3 51 1 ...