点击联系发帖人
时间：2022-11-04 14:20
版权声明：本文为博主原创文章，遵循 版权协议，转载请附上原文出处链接和本声明。
真就错的很离谱 好多错
//做到网线与给定的k一样，且网线尽量长对于一个规模为 n n n的问题：若该问题可以容易地解决（比如说规模 n n n较小）则直接解决，否则将其分解为 k k k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。
分治法所能解决的问题一般具有以下几个特征：
(1) 该问题的规模缩小到一定的程度就可以容易地解决。
(2) 该问题可以分解为若干个规模较小的相同问题。
(3) 利用该问题分解出的子问题的解可以合并为该问题的解。
(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
① 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
② 求解子问题：若子问题规模较小而容易被解决则直接求解，否则递归地求解各个子问题。
③ 合并：将各个子问题的解合并为原问题的解。
在修罗王和邪狼亡命天涯的同时，魔法学院一年一度的运动会正开的如火如荼。赛场上，业余评论员墨老师正在给观众做激情解说：“鬣狗群……咬住！咬住！鬣狗头子立功了！不要给斑马任何的机会！伟大的鬣狗！伟大的鬣狗头子！它继承了猛兽光荣的历史和传统！豹子、老虎、雄狮在这一刻灵魂附体！”
呃，这个，我们不要管那些场上选手的绰号了，现在的问题是有某个项目的 n n n个选手进行循环比赛，其中 n = 2 m n=2^{m} n=2m，要求每名选手要与其他 n － 1 n－1 n－1名选手都赛一次。每名选手每天比赛一次，循环赛共进行 n － 1 n－1 n－1天，要求每天没有选手轮空。比赛时间表格如图所示（假定 m = 3 m=3 m=3）。
输出为 n n n行 n n n列的整型矩阵，即比赛表格。每个元素之间由空格隔开，行末无多余空格。（注意：无需文件输入输出！）
通过样例，我们可以发现规律:
(如图)，每一个(除边长为 1 1 1的)正方形都可以分成 4 4 4个完全相同的小正方形。
每一个小正方形也可以继续分下去，直到边长为 1 1 1为止。
先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处之，直到每一个待处理的序列的长度为1, 处理结束。
题目类型：传统 评测方式：文本比较对 n n n个数使用快速排序进行从小到大排序
n n个int范围内的整数，用空格隔开
从小到大排序之后的 n n n个数
int的范围，需要用long long存储。
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
内存限制：64 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
O(nlogn)的时间复杂度，理论上说与快排是一样的快。但真的很快吗，请大家试一试。 这是一个测试归并排序算法正确性的题，没有别的意义。
N(1≤N≤100000)表示排序元素的个数。
仅 1 1 1行： N N N个从小到大排序的数字。数字之间用 1 1 1个空格分开。
16枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。（注意：必须用分治做！）
一行，两个数，用空格隔开 第一个数是伪币的输入编号，第二个数是伪币的重量
对于查找最小元素，有以下三种情况。
任意取 1 1 1枚硬币，与其他硬币进行比较，若发现轻者，这枚为伪币。最多可能有 15 15 15次比较。
把硬币分为 8 8 8组，每组 2 2 2个，每组比较一次，若发现轻的，则为伪币。最多可能有 8 8 8次比较
上述三种方法，分别需要比较 15 15 15次， 8 8 8次和 4 4 4次，那么形成比较次数差异的根本原因是什么？
方法a: 每枚硬币都至少进行了一次比较，而有一枚硬币进行了 15 15 15次比较。
方法b: 每一枚硬币只进行了 1 1 1次比较。
方法c: 将硬币分成两组后一次比较可以将硬币的范围缩小到原来的一半，这样充分利用了只有 1 1 1枚伪币的性质。
在一个非降序列中，查找与给定值最接近的元素。
第二行包含 n n n个整数，为非降序列各元素。所有元素的大小均在 0 0 0~ 1 0 9 10^{9}
m(1≤m≤10000)，为要询问的给定值个数。
接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在 0 0 0~ 1 0 9 10^{9} 109之间。
m m m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。
本例题是利用二分查找区间中的点与 x x x的大小。如果相等，直接返回这个元素的值。
因为最终的答案一定是有效的下标，所以出事查找的范围可以设为 [ 1 , n ] [1,n] [1,n]。
r，直到区间失效，此时 l , r l,r l,r指向的均为有效下标，可以比较对应的值。
l，直到区间失效，与上面同理。
在一个 N N N个元素的不递减数列中，查找大于或等于 X X X的第一个位置，如果找不到则输出 n + 1 n+1
第二行n个不递减的整数
第三行查找目标数 x x x
从样例可以得出: 我们要周全考虑 x x x在数列中各种可能出现的位置。甚至在左右边界之外的情况。
如果在数列中有连续的一段 x x x，那么找到a[mid] == x时还不能停下来，还得继续在左侧查找，即向左逼近答案，此时更新右端点: r = mid;。
当l + 1 == r时，即左右断点相邻，退出循环。
通过前面几个例子，我们可以知道具有什么特征的题目适合二分?
注:函数的返回类型为double
仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。
为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。
该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。
你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。
N(1≤N≤10000)是库存中的网线数， K(1≤K≤10000)是需要的网线数量。
接下来N行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。
网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。
若无法得到长度至少为1cm的指定数量的网线，则必须输出0.00（不包含引号）。
首先定义两个整数 n n n和 k k k,表示网线的数量和需要的截数。
再定义一个整型数组 a a a，表示每根网线的长度(不定义浮点数是因为避免精度误差)。
定义整型函数check，统计截数。
注: 计算截数时，暴力枚举每一段线可分出的截数，注意计算时用取整除。
check函数。
队列(Queue)一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(Rear)，允许插入的一端称为队头 (Front),如图所示：
请先用一个数组，来模拟队列的功能。
队列（queue）：在线性表的一端插入元素，在另一端删除元素，所以遵循先进先出（ FIFO）原则，元素从队尾进，队首出，不允许插队！
其中删除元素的一端称为队首(front)，插入元素的一端称为队尾（rear）。
队列就像我们排队打饭，先来的先打饭，后来的只能排在队尾。
第1行包含一个整数 ，表示有 条关于 queue 的操作，在进行任何操作之前，queue 都是空的。接来的 行，每行是一个关于 queue 的操作，格式和含义如下：
clear：把队列置空。
empty：判断队列是否为空。
pop： 队首元素出队列。
front：获取队首元素的值。
对于 front 操作，输出一个整数，如果这个操作失败，则输出单词 error。
对于 pop 操作，如果这个操作失败，则输出单词 error。
这道题目是一道模拟题，只需要写出五种语句的函数即可。
判断front和rear是否相等即可。
该函数就是将该“队列”加上一个数，只需rear自加1，再赋值即可。
首先要判断是否为空 (利用empty) 。
若“队列”为空，输出error；否则，输出队首元素。
首先要判断是否为空 (利用empty) 。
若“队列”为空，输出error；否则，front自加1。
queue的用法及功能
判断是否为空。即若队列q为空则返回true，否则返回false。
返回队列q中元素的个数。
返回队列q的首元素的值。
在队列q尾处压入新元素 ， x x x为要压入的元素。
返回队列q的尾元素的值。
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：
栈：插入元素和删除元素只能在线性表的一端进行，所以遵循“先进后出 (LIFO) 原则，其中插入和删除的一端称为栈顶 (top)。我们可以把栈比喻成一个箱子，只能在箱子的开口处放入和取出物体，而且是后放入的物体，会被先取出来。
第 1 行一个整数 ,表示有 条关于 的操作，在进行任何操作之前， 是空的。接来的 行，每行 一个关于 的操作，格式和含义如下：
clear：把栈置空。
empty：判断栈是否为空。
pop： 栈顶元素出栈。
top ：获取栈顶元素的值。
对于 top 操作，输出一个整数，如果这个操作失败，则输出单词 error。
对于 pop 操作，如果这个操作失败，则输出单词 error。
这道题目是一道模拟题，只需要写出五种语句的函数即可。
只需让t(top)置为0即可。
该函数就是将该“栈”加上一个数，只需t自加1，再赋值即可。
首先要判断是否为空 (利用empty) 。
若“栈”为空，输出error；否则，输出队首元素。
首先要判断是否为空 (利用empty) 。
若“栈”为空，输出error；否则，t自减1。
stack的用法及功能
判断是否为空。即若栈s为空则返回true，否则返回false。
返回栈s中元素的个数。
返回栈s的栈顶元素的值。
在栈s顶处压入新元素 ， x x x为要压入的元素。
以上就是“寒假集训总结 (1.23~1.28)”的所有内容了，
由于作者过年干饭去了，时间紧促，本帖中可能有疏忽错误之处，请各位大佬不吝指正!
