int l=0,r=100,ans=0; while(l<=r){ mid=(l+r)/2; if (check(mid)) { l=mid+1;ans = mid; } else r=mid-1; //注意+1，-1否则死循环 }

索引： （一）树状数组： a代表原始数组，c代表树状数组，n很重要！！！！ （1）在多种情况下，树状数组要初始化：void init(); （2）求最低位：int lowbit(int x); （3）单点更新：void update(int x,int y); （4）前x项求和：int getsum(int x); （二）线段树 a代表原始数组，segtree代表线段树结构体 （1）建线段树，相当于初始化：void build(int l,int r,int rt); （2）单点更新：void update(int L,int C,int l,int r,int rt); （3）区间求和：i...

索引：double Dot(Vector,Vector) -> 求两个点的点积，点积可用于判断一个点是否在一个线段的范围内，+不在，-在double length(Vector) -> 利用点积求向量的长度double Angle(Vector,Vector) -> 利用点积和长度以及余弦定理求两个向量之间的夹角double Cross(Vector,Vector) -> 求两个向量之间的叉积，叉积为0，两条直线平行Vector Rotate(Vector,double) -> 向量旋转Point GetLineIntersection(Point,Vec...

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <map> #include <stack> using namespace std; typedef long long ll; struct sss { int val; //原来的数值 i...

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <s...

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include ...

Tarjan算法是求 有向图 中 强连通分量 的算法 知识点：（1）有向图：由有向边构成的图（这是Tarjan算法的前提和条件）（2）强连通：如果两个顶点可以互相通达，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，则称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量 Tarjan算法：Tarjan算法是用来求强连通分量的，它是一种基于DFS的算法，每个强连通分量为搜索树中的一棵子树。并且运用了数据结构栈。 引入两个非常重要的数组： (1)dfn[]:时间戳（被搜到的次数），一旦某个点被DFS后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以经常根据dfn的值来...

设a为原二维数组、c为二维前缀和、b为二维差分 1.（x1,y1)-(x2,y2)的查询用二维前缀和 二维前缀和的构造：c[i][j] = c[i-1][j] + c[i][j-1] - c[i-1][j-1] + a[i][j] （x1,y1)-(x2,y2)的查询：结果 = c[x2][y2] + c[x1][y1] - c[x1][y2] - c[x2][y1] 2.（x1,y1)-(x2,y2)范围内的值++，用二维差分 二维差分数组的构建：b[i][j] = a[i][j] + a[i-1][j-1] - a[i][j-1] - a[i-1][j] 二维差分数组的更新：（x1,y1...

我们用map[i][j]记录每一格的值、用DP[i][j]表示（1，1）这个点与（i,j）这个点两个点分别为左上角和右下角所组成的矩阵内的数的和。 转移方程：DP[i][j]=DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + map[i][j] DP[i][j]可以由DP[i-1][j]、DP[i][j-1]两块构成,注意：1.有一块矩阵重复了，我们要减掉这一块-> DP[i-1][j-1]2.有一小块没有加上，也就是map[i][j]这一个点，所以我们要再加上map[i][j]这一格的数. 那么如何计算以(x1,y1)为左上角，以(x2,y2)为右上角的...

差分和前缀和互为逆运算，即差分数组的前缀和数组为原数组，前缀和数组的差分数组为原数组。两者都利用了容斥原理，这一点在二维平面（或二维数组）中体现的更加明显。 一维差分 定义：差分就是将数列中的每一项分别与前一项数做差。 例子：一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3 性质：1.差分数组求前缀和可以得到原序列2.将愿序列区间[L,R]中的元素全部+1，可以转化操作为差分数组L处+1，R+1处-1.3.按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同。 二维差分 其实二维差分和一维差分一样，就是更新时一维是更新两个点，二...

我是用DFS做的这道题，里面有很多细节记录一下。 试题链接：https://ac.nowcoder.com/acm/contest/7501/I #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include...

从1～n中随机选择数输出（可以什么也不输出），请输出所有的可能，每种可能占一行。（n最大值是16） 思路：一共有2^n种可能，可以用二进制解决。 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include...

set牛逼，简单记录一下set的find函数，因为set是红黑树维护的，且set里面的元素是按照从小到大排序的，所以set的find函数比vector的find函数省很多时间复杂度。 vector的find函数还要用到迭代器，而set可以直接.find()就可以了（更加方便），里面不写范围，固定是一整个set范围。 例子： if(s.find(想要查找的元素)==s.end()) { s.insert(想要查找的元素); }

A - Multiple of 9 C - Walk on Multiplication Table * E - Maximal Value * A、C 、E题为上次比赛原题，所以只做出三道题来的可以好好想想。 B - Where is the Marble?题意：给你n个数字，再给你m次查询，每次查询一个数字，问你这个数字在所有数字中排第几，如果不存在，输出这个数not found。 思路：这道题我用到了lower_bound()，有三个参数，前两个数查询的区间，第三个参数是要查询的数字x。返回的是大于等于x的地址，如果不存在，则返回最后的区间。如果想要详细了解lower_bound()可以...