【题目描述】

设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。

【输入描述】

输入：M。

【输出描述】

输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。

【样例输入】

3

【样例输出】

1 2 3 4 5 6 7 8  2 1 4 3 6 5 8 7  3 4 1 2 7 8 5 6  4 3 2 1 8 7 6 5  5 6 7 8 1 2 3 4  6 5 8 7 2 1 4 3  7 8 5 6 3 4 1 2  8 7 6 5 4 3 2 1

1. 前言

   所谓分治算法就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。

   比如，我们玩过最简单的猜数游戏，一开始，对方先想一个1000以内的正整数，然后你给出一个数x。对方只要回答“比x大”或者“比x小”或者“猜中”。

   开始猜测是1到1000之间，你可以先猜500。运气好的一次猜中，如果比500大，显然结果不是1到500之间，那么下一次就猜501到1000。如果比500下，那么下次就猜1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。这样不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。

2. 基本思想及策略

   分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

    分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

     如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

应用

（1）二分搜索

 （11）一元三次方程求解

快速排序：

void qsort(int left, int right){  	int i=left; j =right;  	mid=a[left+right]/2;  	while(i<=j){  		while(a[i]<mid) i++;   		while(a[j>mid]) j--;  		if(i<=j){  			swap(a[i],a[j]);  			i++;  			j--;  		}  	}  	if(left<j) qsort(left,j);  	if(i<right) qsort(i,right);  }

一元三次方程求解：

描述

有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。

给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。

输入

一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。

输出

一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。

样例输入

1.0 -5.0 -4.0 20.0

样例输出

-2.00 2.00 5.00

【题目描述】

Kri 喜欢玩数字游戏。 一天，他在草稿纸上写下了t 对正整数(x,y) ，并对于每一对正整数计算出了z=x*y*gcd(x,y);可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 y都擦除了，还可能改动了一些 z。

现在 Kri 想请你帮忙还原每一组的 y，具体地，对于每一组中的 x和 z，你需要输出最小的正整数 y，使得 z=x*y*gcd(x,y)  。如果这样的 y不存在，也就是 Zay 一定改动了z ，那么请输出 -1。 注：gcd(x,y) 表示 x和 y的最大公约数，也就是最大的正整数 d，满足 既是x 的约数，又是 y的约数。

【输入描述】

第一行一个整数 t ，表示有 对正整数 x和z 。

 接下来 t 行，每行两个正整数 x和z ，含义见题目描述。

【输出描述】

对于每对数字输出一行，如果不存在满足条件的正整数y ，请输出-1 ，否则输出满足条件的最小正整 数 y。

【样例输入1】

1  10 240

【样例输出1】

12

【样例1解释】

x*y*gcd(x,y)=10*12*gcd(10,12)=240

【样例输入2】

3  5 30  4 8  11 11

【样例输出2】

6  -1  1

【数据范围】

对于20%的数据，t,x,z<=103。 

对于40%的数据，t<=103,  x<106,  z<=109。 

对于另30% 的数据，t<104 。 

对于另20% 的数据，x<106 。 

对于100%的数据，1<=t<=5*105, 1<=x<=109, 1<=z<=263 。

【题目描述】

智慧之王 Kri 统治着一座王国。 这天 Kri 决定举行一场比赛，来检验自己大臣的智慧。 比赛由 n道判断题组成，有 m位大臣参加。现在你已经知道了所有大臣的答题情况，但尚未拿到答 案，于是你决定先行预测。 具体来说，对于第 i道题，有 x个大臣选对， y个大臣选错（显然有x+y=m ），如果x>y，那 么你预测这题答案为对，否则为错。为了方便，我们保证 m是奇数。 在统计完成后，你拿到了答案，你想知道通过你的预测方式你最后有几道题预测正确。

【输入描述】

第一行两个正整数 n,m，保证m 是奇数。 接下来 m行，每行n 个整数，第i 行第j个整数 aij代表第 i位大臣对第 j道题的答案， 1表示他选 对， 0表示他选错。 接下来1 行 n个整数， 表示比赛答案， 第i 个数 bi若为 1表示第i 道题答案是对，若为 0表示答案是 错。

【输出描述】

输出一个整数，表示你最后有几题预测正确。

【样例输入1】

3 3  1 0 1  0 1 1  0 1 0  1 1 1

【样例输出1】

2

【样例1解释】

第一题 你预测答案为错（即0），实际答案为1，预测错误。 

第二题 你预测答案为对（即1），实际答案为1，预测正确。

第三题 你预测答案为对（即1），实际答案为1，预测正确。 所以预测正确的题数为2。

【样例2输入】

5 6  1 0 1 1 1 0  0 1 0 1 1 1  0 0 1 0 1 0  1 0 1 0 1 0  0 1 0 1 0 0  1 0 1 0 1 0

【样例2输出】

4

【数据范围】

对于20%的数据，n<=5，m=1 。 

对于50%的数据，n<=10，m<=10 。 

对于100%的数据， n<=1000 , m<=1000，m为奇数 。

【题目描述】

路飞在和他朋友们一块玩一个游戏。由于路飞的机智，这个游戏由路飞担任裁判。

首先，路飞会给他们一个人一个编号，并且每个人的编号都不相同。接下来的每一个回合，会给一个数，编号不超过它的最大编号

的人要报出自己的编号。如果没有人的编号比路飞给出的数要小，那么编号最小的人要报出自己的编号。每个人可以重复报号。

路飞会按照一个列表顺次报出每个回合的数，他的朋友们想知道每回合报出的编号应该是多少？

【输入描述】

输入数据共3行。

第一行有两个整数n,m( 1<=n<=105 , 1<=m<=105 )，分别表示参与游戏的路飞朋友的个数和游戏回合数。

第二行n个整数 ai (1<=ai<=108) ，表示朋友们每个人的编号。对于 0<=i<j<n， 都有 ai<aj，即他们的编号递增排列。

第三行m个整数 qi(1 <= qi <=108), 表示每回合路飞给的数字。

【输出描述】

 输出共一行m个整数，表示每回合报出的编号，每两个整数之间一个空格，最后一个数后面没有空格。

【样例输入】

5 5  1 5 10 15 20  3 6 12 18 24

【样例输出】

1 5 10 15 20

【题目描述】

话说在一场牛客练习赛中，东哥力压群雄，挣得第一，牛客为了奖励东哥的发挥，送他一个马克杯。奖励的马克杯是一个标准的

圆台形状，它的上底为R1，下底为R2，高为H, 东哥向杯子里倒V毫升的水，你知道倒完水后，杯子里的水位有多高吗?

【输入描述】

多组数据

每组数据只有一行，为R1(1<=R1<=10,000)，R2(1<=R2<=100,000), H(1<=H<=100,000),V(1<=V<=1000,000,000)。

【输出描述】

输出倒完水后的杯子的水位高，结果保留三位小数

【样例输入】

10 100 10 1000  1 1 1 10

【样例输出】

1.250  1.000

【公式】

r为上底半径、R为下底半径、h为高。

【题目描述】

农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N(1 ≤N≤ 100,000) 天里每天需要的开销。

约翰打算为连续的M(1 ≤M≤N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。

约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。

【输入描述】

第一行包含两个整数N,M，用单个空格隔开。

接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。

【输出描述】

一个整数，即最大月度开销的最小值。

【样例输入】

7 5  100  400  300  100  500  101  400

【样例输出】

500

【题目描述】

小明的生日要到了！根据习俗，他需要将一些派分给大家。

他有 $$N 个不同口味、不同大小的派。有 $F$ 个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为 $1$，半径不等的圆柱体。

【输入描述】

第一行包含两个正整数 n$N$ 和m $F$，表示派的数量和朋友的数量。（N>=1, F<=10000）

第二行包含 $N$ 个 1 到 $10000$ n之间的整数，表示每个派的半径

【输出描述】

输出每个人能得到的最大的派的体积，精确到小数点后三位。

【样例输入】

3 3 

4 3 3

【样例输出】

25.133