整数二分步骤： 1.找一个区间[L，R]，使得答案一定在该区间中 2.找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。 3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间； 4.如果更新方式写的是R=Mid，则不用做任何处理；如果更新方式写的是L=Mid，则需要在计算Mid时加上1。 具体如下： 假设要在有序数组A找到最大的<= x的数： 我们发现把数组A分为<=x和>x的这两段： 假设要在有序数组A找到最小的<= x的数： 我们发现把数组A分为<x和>=x的这两段：
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1”。
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
1≤n≤100000 1≤q≤100001≤q≤10000 1≤k≤100001≤k≤10000
C++代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n, m; int q[N]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); for (int i = 0; i < m; i ++ ) { int x; scanf("%d", &x); // 二分x的左端点 int l = 0, r = n - 1; // 确定区间范围 while (l < r) { int mid = l + r >> 1; if (q[mid] >= x) r = mid; else l = mid + 1; } if (q[r] == x) { cout << r << ' '; // 二分x的右端点 r = n - 1; // 右端点一定在[左端点, n - 1] 之间 while (l < r) { int mid = l + r + 1 >> 1; // 因为写的是l = mid，所以需要补上1 if (q[mid] <= x) l = mid; else r = mid - 1; } cout << r << endl; } else cout << "-1 -1" << endl; } return 0; } IA=lambda:map(int,input().split()) n,q=IA() a=list(IA()) a.append(0) for _ in range(0,q): m=int(input()) l=0 r=n while l<r: mid=(l+r)>>1 if a[mid]>=m: r=mid else: l=mid+1 if a[r]!=m: print("-1 -1") continue else: print(r, end=" ") l=0 r=n-1 while l<r: mid=(l+r+1)>>1 if a[mid]<=m: l=mid else: r=mid-1 print(r)给定一个浮点数n，求它的三次方根。
共一行，包含一个浮点数n。
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
−10000≤n≤10000−10000≤n≤10000
机器人正在玩一个古老的基于DOS的游戏。
游戏中有N+1座建筑——从0到N编号，从左到右排列。
编号为0的建筑高度为0个单位，编号为 i 的建筑高度为H(i)个单位。
起初，机器人在编号为0的建筑处。
每一步，它跳到下一个（右边）建筑。
假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1个建筑。
如果H(k+1)>E，那么机器人就失去H(k+1)-E的能量值，否则它将得到E-H(k+1)的能量值。
游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？
第一行输入整数N。
第二行是N个空格分隔的整数，H(1),H(2),…,H(N)代表建筑物的高度。
输出一个整数，表示所需的最少单位的初始能量值。
1≤N,H(i)≤1051≤N,H(i)≤105,
有个坑，二分过程会爆int（对于C++），python直接大数无敌，但慢，优化一下更快。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; int h[N]; bool check(int e) { for (int i = 1; i <= n; i ++ ) { e = e * 2 - h[i]; if (e >= 1e5) return true; if (e < 0) return false; } return true; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); int l = 0, r = 1e5; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%d\n", r); return 0; } IA=lambda:map(int,input().split()) n=int(input()) a=list(IA()) def check(x): for i in range(0,n): if a[i]>x: x-=a[i]-x if x<0:return 0 else: x+=x-a[i] if x>100005: return 1 return 1 l=0 r=max(a)+1 while l<r: mid=(l+r)>>1 if check(mid)==1: r=mid else: l=mid+1 print(r)四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 44 个正整数的平方和。
如果把 00 包括进去，就正好可以表示为 44 个数的平方和。
比如：
5=02+02+12+225=02+02+12+22 7=12+12+12+227=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 44 个数排序：
0≤a≤b≤c≤d0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,da,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入一个正整数 NN。
输出4个非负整数，按从小到大排序，中间用空格分开。
0<N<5∗1060<N<5∗106
二分未过
n=int(input()) class Node: def __init__(self,val,c,d): self.val=val self.c=c self.d=d def __lt__(self,other): if self.val==other.val: if self.c==other.c: return self.d<=other.d return self.c<=other.c return self.val<=other.val summ=[] c=0 while c*c<=n: d=c while d*d+c*c<=n: node=Node(d*d+c*c,c,d) summ.append(node) d+=1 c+=1 summ.sort() flag=0 a=0 while a*a<=n: b=a while a*a+b*b<=n: l=0 r=len(summ)-1 while l<r: mid=l+r>>1 if summ[mid].val>=n-a*a-b*b: r=mid else: l=mid+1 if summ[r].val+a*a+b*b==n: print("{} {} {} {}".format(a,b,summ[r].c,summ[r].d)) flag=1 break b+=1 if flag==1: break a+=1字典过了
n=int(input()) class Node: def __init__(self,val,c,d): self.val=val self.c=c self.d=d def __lt__(self,other): if self.val==other.val: if self.c==other.c: return self.d<=other.d return self.c<=other.c return self.val<=other.val summ=[] c=0 dic={} while c*c<=n: d=c while d*d+c*c<=n: x=d*d+c*c if x not in dic: dic[x]=[c,d] else: if dic[x][0]>c: dic[x]=[c,d] elif dic[x][0]==c: if dic[x][1]>d: dic[x]=[c,d] d+=1 c+=1 summ.sort() flag=0 a=0 while a*a<=n: b=a while a*a+b*b<=n: x=n-a*a-b*b if x in dic: print("{} {} {} {}".format(a,b,dic[x][0],dic[x][1])) flag=1 break b+=1 if flag==1: break a+=1儿童节那天有 KK 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力，其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 NN 块巧克力中切出 KK 块巧克力分给小朋友们。
切出的巧克力需要满足：
形状是正方形，边长是整数大小相同例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
第一行包含两个整数 NN 和 KK。
以下 NN 行每行包含两个整数 HiHi 和 WiWi。
输入保证每位小朋友至少能获得一块 1×11×1 的巧克力。
输出切出的正方形巧克力最大可能的边长。
1≤N,K≤1051≤N,K≤105, 1≤Hi,Wi≤1051≤Hi,Wi≤105
