企业网站建设需要什么资料学校网站建设模板

当前位置： 首页 > news >正文

企业网站建设需要什么资料,学校网站建设模板,厦门市同安区建设局网站,如何注册视频号杨辉三角形#xff08;快速查找唯一值,mid型) //二分法解//流程#xff1a;最大列-起点行-2k–n之间究竟哪一行#xff08;二分排列组合#xff09;-找到行数就等差数列对应位置#includestdio.h #includestdlib.h//注意排列组合的规律是建立在…杨辉三角形快速查找唯一值,mid型) //二分法解//流程最大列-起点行-2k–n之间究竟哪一行二分排列组合-找到行数就等差数列对应位置#includestdio.h #includestdlib.h//注意排列组合的规律是建立在第0行和第0列的基础 long C(long a,long b,long n)//C排列组合算法 {long res1;//一开始要赋值为1for(long ia,j1;jb;i–,j)//一个循环就可以实现C排列组合{resres*i/j;if(resn){return res;}//放循环里判断优化算法//一旦这个res在循环中的结果已经有了超过n的就马上退出不要再//等它全部遍历完返回再判断}return res;}int main(int argc, char *argv[]){long n,k;scanf(%ld,n); // for(k0;;k)errfor(k16;k0;k–)//为什么正着输出不行//因为我们是计算第一次出现的数字//那就必须要在最后面的列开始找//一直往前面的列逐个寻找//你从正着遍历就是直接输出最近的也就是第1列//第一列必会出现这个数的答案因此直接输出了//就不是第一次出现//所以不可以不计算//k代表需要遍历列数//这是根据最大测评数据推出的,1e9//计算器难计算的就可以借助编程来计算//自己写一个排列组合的函数该题也用到了这个函数//代数看看最大只可能出现在哪即可//求出最大列数不可能在17列C17/34大于1e9//因此可以得知在[0,16]之间//k–能写成k肌肉记忆是吧?{long l2*k,rn;//l等于2k是对应行数//因为一开始从最大列开始算//也就只有2k以后的行才会有这么多的有效列//所以从这以后开始查找//l是需要遍历的行数,//这里等于2k仅仅只是满足最大情况//当最大情况不为所求时就用二分法//矫正行数这就是为什么二分法只分行数//列不变也是定一动一.//int mid(lr)/2;//这个要放里面因为每次二分都是不同位置的while(lr) //二分法//二分法可以是mid值作为想要输出的结果//也可以使用right和left作为想要的输出结果//具体不同题设判断如何用l,r还是mid//当结果不用l、r时我们就不需要考虑//l与r究竟谁赋值mid了。直接舍弃即可(求Mid)//因为我们要求的只有唯一值就是行数//所以可以直接使用mid//直接用mid就是固定的// rmid-1;// lmid1;//类似的模板//(因为既然mid值都不为所求,自然都舍弃)//l是左边界r是右边界(我们求行数所以左边界为l)//意思就是从l的范围开始找//而r是上限//所寻找的行永远小于等于n行所以可以设边界//最差的情况就是数字等于行数//即所找的数字在第n行第二位的情况//所以rn{long mid(lr)/2;//划分中点//我们的二分法是为了寻找所求数字的//所在的行和列而不是直接找到该数字if(C(mid,k,n)n)//mid是所寻找的行不是数字//中点恰好是要找的行//放在全局变量就不用上传这么多参数了{printf(%ld,(1mid)*mid/2k1);//这里是等差数列每一行的全部是//d1的等差123……//注意我们求的是数字数量之和不是大小之和//所以(a1an)n/2//这里的等差数列是把原来的第0列看成第一列了//这里的等差数列就没有第0列//因此求出来的mid行数就是上一行//恰好可以排等差数列,剩下的加上k1即可//k1是因为排列组合有第0列既然是在使用这个//规律的基础上就必须遵循第0列开始//而第0列-k列就是k1//注意过程的选取是等差数列的过程// 还是处在排列组合的过程return 0;}else if(C(mid,k,n)n)rmid-1;//mid太大就只可能在左边一堆//然后循环再分一次else//mid太小lmid1;}}return 0; } 递增三元组(求极限/多种情况最优最佳结果l、r型 #includebits/stdc.h//递增三元组using namespace std; int main() {int a[100000],b[100000],c[100000];int n;long long ans0;cinn;for(int i0;in;i)cina[i];for(int i0;in;i)cinb[i];for(int i0;in;i)cinc[i];sort(a,an);//直接写出首尾就ok了sort(c,cn);int left,right; for(int i0;in;i)//枚举b {//找出比b小的最大的a,比b大的最小的cleft0,rightn-1;while(leftright){int mid(leftright1)/2;if(b[i]a[mid])//当前a的值大于等于b我也不要了//a太大我就缩小//注意这个小于等于要放在一起因为都归为mid不可取的一边//如果只写那么等于在下面就无法把等于这种情况去除.rightmid-1;elseleftmid;//当前mid满足条件可取}int xright;left0,rightn-1; while(leftright) {int mid(leftright)/2;if(b[i]c[mid])//条件不满足题意mid值不要leftmid1;elserightmid;//符合,mid可取} int yright;if(a[x]b[i]b[i]c[y]) {// ans(x1)(n-y);errans(long long)(x1)*(n-y);//两个相乘是因为排列组合//定下1个b每一种的a都有n-y个c的情况.//一个数据错了这里相乘计算大数据会溢出//所以要扩大数据类型//但是给x,y修改类型竟然也能过我不知道为什么//但逻辑来讲还是改这里的数据类型比较严谨 }}coutans;return 0; } 总结 如果二分法输出的是l、r那么循环搜索的原理就是当lr时结束搜索 此时l与r的值都是一样的都能作为结果输出 循环条件为lr 等于时就停止循环了不要写lr不然会死循环 而mid作为结果输出时 我不关心l、r的结果 我要求的是mid,而lr时同样仍然还可以再求中间值 如果是这种情况也就是midlr 那么也要将这个结果赋值给mid要不然你的mid也是错的 因此求mid时条件为lr 求mid的二分的前提是找一个值,是相当于只是优化算法 加快了遍历速度就是每次都遍历一半其实完全可以用for循环暴力遍历 当前是唯一值线性的范围内只要这个mid符合条件我就马上退出循环了 不满足就继续分 这个是查找唯一的下标值 而求l、r是不同的这个二分相当于是求一个边界和极限 因为l、r可以不断移动所以是通过调整l、r的位置来确定唯一的值 当lr时就是那个划分边界的点此时的mid只是作为调位的一个工具 初始的时候l、r距离很大后来不断二分缩小他们的位置最后相等时 即确定了极限和边界位置. 求l、r的时候才真正体现了二分的优越性. mid更像是快速查找唯一值而l、r则似求一个满足当前条件的一个极限值 明显的特征就是l、r的情况有多个结果只是在多个结果中挑选出一个 最佳最优的情况也就是极限就要用l、r来收缩求最佳结果.