二分的基本思路就是从一个很大的范围用二分的思想筛选，判断是最大化还是最小化问题
二分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int find (int q) int l = 0 , r = n+1 ; while (l+1 <r) { int mid = l+r >> 1 ; if (a[mid]<=q){ l = mid; } else r = mid; } return l; } int find1 (int q) int l = 0 , r = n+1 ; while (l+1 <r) { int mid = l+r >> 1 ; if (a[mid] >= q){ r = mid; }else l = mid; } return r; }
我们来练习一下，求一个浮点数 (-10000 $\leqslant$ y $\leqslant$ 10000 )的三次方根
1 2 3 4 5 6 7 8 9 double find (double y) double l = -100 , r = 100 ; while (r-l>1e-5 ){ double mid = (l+r)/2 ; if (mid*mid*mid <= y) l = mid; else r = mid; } return l; }
题目1 输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a1,a_2,\dots,a {n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。
输入格式 第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。
第二行 $n$ 个整数，表示这些待查询的数字。
第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。
输出格式 输出一行，$m$ 个整数，以空格隔开，表示答案。
样例 #1 样例输入 #1 1 2 3 11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6
样例输出 #1 提示 数据保证，$1 \leq n \leq 10^6$，$0 \leq a_i,q \leq 10^9$，$1 \leq m \leq 10^5$
本题输入输出量较大，请使用较快的 IO 方式。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/stdc++.h> using namespace std;int a[1000005 ];int n,m;int find (int q) int l = 0 ,r = n+1 ; while (l+1 < r) { int mid = (l+r) / 2 ; if (a[mid]>=q) r =mid; else l = mid; } return a[r] == q ? r : -1 ; } int main () cin >> n >> m; for (int i = 1 ; i <=n ;i++){ cin >> a[i]; } for (int i =1 ;i <= m ; i++){ int p; cin >> p; cout << find (p) <<" " ; } system ("pause" ); return 0 ; }
题目2 有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。
提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。
输入格式 一行，$4$ 个实数 $a, b, c, d$。
输出格式 一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。
样例 #1 样例输入 #1 样例输出 #1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> using namespace std;double a,b,c,d;double fun (double x) return a*x*x*x + b*x*x+c*x+d; } double find (double l,double r) while (r-l>0.0001 ) { double mid = (l+r) /2 ; if (fun (mid)*fun (r) < 0 ) l = mid; else r = mid; } return l; } int main () cin >> a >> b >> c >>d; for (int i = -100 ; i< 100 ;i++){ double y1 = fun (i),y2 = fun (i+1 ); if (!y1) printf ("%.2f " ,1.0 *i); if (y1*y2 <0 ) printf ("%.2lf " ,find (i,i+1 )); } if (fun (100 ) == 0 ) cout << "100.00" ; system ("pause" ); return 0 ; }
处理的时候要记得是最大化还是最小化问题
题目3 木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均 为 $l$ 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。
木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。
输入格式 第一行是两个正整数 $n,k$，分别表示原木的数量，需要得到的小段的数量。
接下来 $n$ 行，每行一个正整数 $L_i$，表示一根原木的长度。
输出格式 仅一行，即 $l$ 的最大值。
如果连 $\text{1cm}$ 长的小段都切不出来，输出 0。
样例 #1 样例输入 #1 样例输出 #1 提示 数据规模与约定 对于 $100\%$ 的数据，有 $1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8(i\in[1,n])$。
这是一个最大化问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> typedef long long ll;using namespace std;ll a[100005 ]; ll n,k; bool deal (int x) int num = 0 ; for (int i = 1 ; i<=n ;i++){ num += a[i] / x; } return num >= k; } int fun () int l = 0 , r =1e8 +1 ; while (l+1 < r) { ll mid = (l + r)/2 ; if (deal (mid)) l = mid; else r = mid; } return l; } int main () cin >> n >> k; for (int i = 1 ; i <= n ;i ++){ cin >> a[i]; } cout << fun (); system ("pause" ); return 0 ; }
题目4 一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。
输入格式 第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。
接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$， 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式 一个整数，即最短跳跃距离的最大值。
样例 #1 样例输入 #1 样例输出 #1 提示 输入输出样例 1 说明 将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$（从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。
数据规模与约定 对于 $20\%$的数据，$0 \le M \le N \le 10$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;int L,n,m,a[500005 ];bool check (int x) int last = 0 , cnt = 0 ; for (int i=1 ; i<=n+1 ;i++){ if (a[i]-a[last]<x) cnt++; else last = i; } return cnt<= m; } int find () int l=0 ,r=1e9 ; while (l+1 <r) { int mid = l+r>>1 ; if (check (mid)) l = mid; else r = mid; } return l; } int main () cin >> L >> n >> m; for (int i=1 ; i<= n ; i++){ cin >> a[i]; } a[n+1 ] = L; cout << find (); system ("pause" ); return 0 ; }
llabs 函数用于long long 类型求绝对值，labs 用于 long 类型求绝对值
题目5 小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石，从 $1$ 到 $n$ 逐一编号，每个矿石都有自己的重量 $w_i$ 以及价值 $v_i$ 。检验矿产的流程是：
给定$ m$ 个区间 $[l_i,r_i]$；
选出一个参数 $W$；
对于一个区间 $[l_i,r_i]$，计算矿石在这个区间上的检验值 $y_i$：
其中 $j$ 为矿石编号。
这批矿产的检验结果 $y$ 为各个区间的检验值之和。即：$\sum\limits_{i=1}^m y_i$
若这批矿产的检验结果与所给标准值 $s$ 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 $W$ 的值，让检验结果尽可能的靠近标准值 $s$，即使得 $|s-y|$ 最小。请你帮忙求出这个最小值。
输入格式 第一行包含三个整数 $n,m,s$，分别表示矿石的个数、区间的个数和标准值。
接下来的 $n$ 行，每行两个整数，中间用空格隔开，第 $i+1$ 行表示 $i$ 号矿石的重量 $w_i$ 和价值 $v_i$。
接下来的 $m$ 行，表示区间，每行两个整数，中间用空格隔开，第 $i+n+1$ 行表示区间 $[l_i,r_i]$ 的两个端点 $l_i$ 和 $r_i$。注意：不同区间可能重合或相互重叠。
输出格式 一个整数，表示所求的最小值。
样例 #1 样例输入 #1 1 2 3 4 5 6 7 8 9 5 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3
样例输出 #1 提示 【输入输出样例说明】
当 $W$ 选 $4$ 的时候，三个区间上检验值分别为 $20,5 ,0$ ，这批矿产的检验结果为 $25$，此时与标准值 $S$ 相差最小为 $10$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <bits/stdc++.h> using namespace std;typedef long long ll;const int N=200010 ;int n,m,W[N],v[N],l[N],r[N];ll s,sn[N],sv[N],ans = 1e18 ; bool check (int w) memset (sn,0 ,sizeof (sn)); memset (sv,0 ,sizeof (sv)); for (int i=1 ; i<= n ; i++){ if (W[i]>=w) sn[i] = sn[i-1 ]+1 ,sv[i] = sv[i-1 ]+v[i]; else sn[i] = sn[i-1 ],sv[i] = sv[i-1 ]; } ll y = 0 ; for (int i = 1 ; i <= m ; i++){ y+=(sn[r[i]]-sn[l[i]-1 ])*(sv[r[i]]-sv[l[i]-1 ]); } ans = min (ans,llabs (y-s)); return y<=s; } ll find () { int l = 0 ,r = 1e6 +1 ; while (l+1 <r) { int mid = l +r >>1 ; if (check (mid)) r = mid; else l = mid; } return ans; } int main () cin >> n >> m>>s; for (int i = 1 ; i<=n ;i++){ cin >> W[i] >> v[i]; } for (int i=1 ; i<= m ; i++){ cin>>l[i]>>r[i]; } cout << find (); system ("pause" ); return 0 ; }
下面这个题目是干什么的？二分的思想可以运用到很多地方，找到合适的数字可以用到二分的思想，另外，前缀和的思想可以运用的到
题目6 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。
输入格式 第一行包含两个正整数 $n,m$，表示天数和订单的数量。
第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于租借的教室数量。
接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。
输出格式 如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。否则（订单无法完全满足）
输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改订单的申请人编号。
样例 #1 样例输入 #1 1 2 3 4 5 4 3 2 5 4 3 2 1 3 3 2 4 4 2 4
样例输出 #1 提示 【输入输出样例说明】
第 $1 $份订单满足后，$4 $天剩余的教室数分别为 $0,3,2,3$。第 $2$ 份订单要求第 $2 $天到第 $4$ 天每天提供$ 3 $个教室，而第 $3$ 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第$2$ 个申请人修改订单。
【数据范围】
对于10%的数据，有$1≤ n,m≤ 10$；
对于30%的数据，有$1≤ n,m≤1000$；
对于 70%的数据，有$1 ≤ n,m ≤ 10^5$；
对于 100%的数据，有$1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n$。
NOIP 2012 提高组 第二天 第二题
2022.2.20 新增一组 hack 数据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include <bits/stdc++.h> using namespace std;const int N = 1000010 ;int n,m;int r[N],d[N],s[N],t[N];long long num[N];bool check (int x) memset (num,0 ,sizeof num); for (int i = 1 ; i <= x ; i++){ num[s[i]]+=d[i]; num[t[i]+1 ] -= d[i]; } for (int i=1 ; i<=n ; i++){ num[i] += num[i-1 ]; if (num[i]>r[i]) return false ; } return true ; } int find () int l = 0 , r = m+1 ; while (l+1 <r) { int mid = l+r>>1 ; if (check (mid)) l = mid; else r = mid; } return l; } int main () cin >> n >> m; for (int i = 1 ; i <= n ;i++){ cin >> r[i]; } for (int i = 1 ; i<= m ;i++){ cin >> d[i] >> s[i] >> t[i]; } int ans= find (); if (ans == m){ cout << 0 ; } else { cout << -1 << endl << ans +1 ; } system ("pause" ); return 0 ; }
题目7 某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。
迷阵由 $n\times m$ 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 $n$ 行的 $m$ 个房间里有 $m$ 个机关，这些机关必须全部打开才可以进入大使馆。而第 $1$ 行的 $m$ 个房间有 $m$ 扇向外打开的门，是迷阵的入口。除了第 $1$ 行和第 $n$ 行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 $i$ 行第 $j$ 列 造成的伤害值为 $p_{i,j}$（第 $1$ 行和第 $n$ 行的 $p$ 值全部为 $0$）。
现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选 择任意多的人从任意的门进入，但必须到达第 $n$ 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。
输入格式 第一行有两个整数 $n,m$，表示迷阵的大小。
接下来 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 列的数表示 $p_{i,j}$。
输出格式 输出一个数，表示最小伤害代价。
样例 #1 样例输入 #1 样例输出 #1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <bits/stdc++.h> using namespace std;int n,m;int a[1005 ][1005 ];int vis[1005 ][1005 ];int dx[] = {1 ,-1 ,0 ,0 };int dy[] = {0 ,0 ,-1 ,1 };bool fun (int x,int y ,int p) if (x == n) return true ; vis[x][y] = 1 ; for (int i = 0 ; i <=3 ; i++){ int aa = x+dx[i],b = y + dy[i]; if (aa>=1 &&aa<=n&&b>=1 &&b<=m&&!vis[aa][b]&&a[aa][b]<=p){ if (fun (aa,b,p)) return true ; } } return false ; } int check () int l = 0 , r = 1001 ; while (l+1 <r) { int mid = l + r >>1 ; memset (vis,0 ,sizeof vis); if (fun (1 ,1 ,mid)) r = mid; else l = mid; } return r; } int main () cin >> n >> m; for (int i=1 ; i<=n ; i++){ for (int j = 1 ; j<= m ;j++){ cin >> a[i][j]; } } cout << check (); system ("pause" ); return 0 ; }
蓝桥题目
ac代码 这题不同于普通的单调的题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;typedef long long ll;int n;ll p[10005 ][2 ]; ll ans = 0x3f3f3f3f3f3f3f3f ; bool check (ll x) for (int i = 1 ; i <= n; i++) { if (p[i][0 ] / x != p[i][1 ]) return false ; } return true ; } int find () int l = 0 , r = ans+1 ; while (l+1 <r) { int mid = l + r >> 1 ; if (check (mid)) r=mid; else l=mid; } return r; } int main () cin >> n; for (int i = 1 ; i <= n; i++) { cin >> p[i][0 ] >> p[i][1 ]; ans = min (ans, p[i][0 ] / p[i][1 ]); } cout << find ()<<" " << ans; return 0 ; }
三分
落谷3382
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;const double eps = 1e-6 ;int n;double a[15 ];double f (double x) double s = 0 ; for (int i = n; i >= 0 ;i--) s = s * x + a[i]; return s; } int main () double l, r; cin >> n >> l >> r; for (int i = n; i >= 0 ; i--) cin >> a[i]; while (r-l>eps) { double k = (r - l) / 3.0 ; double mid1 = l + k, mid2 = r - k; if (f (mid1) > f (mid2)) r = mid2; else l = mid1; } printf ("%.5f" , l); return 0 ; }
与近似三等份不同的是
落谷 1883
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;const double eps = 1e-9 ;int t, n;int p[10005 ][3 ];double check (double x) double a = x * x * p[0 ][0 ] + x * p[0 ][1 ] + p[0 ][2 ]; for (int j =1 ; j < n; j++) { double ans = 0 ; ans = x*x*p[j][0 ]+x*p[j][1 ]+p[j][2 ]; a = max (a, ans); } return a; } int main () cin >> t; while (t--) { cin >> n; for (int i = 0 ; i < n; i++) { cin >> p[i][0 ] >> p[i][1 ] >> p[i][2 ]; } double l = 0 , r = 1000 ; while (r - l > eps) { double mid = (r-l) / 3 ; double mid1 = l+mid, mid2 = r - mid; if (check (mid1) > check (mid2)) l = mid1; else r = mid2; } printf ("%.4f\n" , check (l)); } return 0 ; }
倍增法 如果想达到一个数字 n ，可以利用 2 的指数次方作为跳板，可以快速达到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int n, m, result[200005 ];struct Soldier { int id, left, right; } soldiers[400005 ]; int compare (Soldier a, Soldier b) return a.left < b.left; } int go[400005 ][20 ];void preProcess () for (int i = 1 , p = i; i <= 2 * n; i++) { while (p <= 2 * n && soldiers[p].left <= soldiers[i].right) p++; int pos = p - 1 ; go[i][0 ] = pos; } for (int i = 1 ; i < 20 ; i++) { for (int j = 1 ; j <= 2 * n; j++) { go[j][i] = go[go[j][i - 1 ]][i - 1 ]; } } } void search (int k) int limit = soldiers[k].left + m; int ans = 1 ; int p = k; for (int i = 19 ; i >= 0 ; i--) { if (go[k][i] != 0 && soldiers[go[k][i]].right < limit) { ans += (1 << i); k = go[k][i]; } } result[soldiers[p].id] = ans + 1 ; } int main () cin >> n >> m; for (int i = 1 ; i <= n; i++) { cin >> soldiers[i].left >> soldiers[i].right; if (soldiers[i].right < soldiers[i].left) soldiers[i].right += m; soldiers[i].id = i; } sort (soldiers + 1 , soldiers + 1 + n, compare); for (int i = 1 ; i <= n; i++) { soldiers[i + n] = soldiers[i]; soldiers[i + n].left = soldiers[i].left + m; soldiers[i + n].right = soldiers[i].right + m; } preProcess (); for (int i = 1 ; i <= n; i++) search (i); for (int i = 1 ; i <= n; i++) cout << result[i] << " " ; return 0 ; }
ST 算法
那如何去查询呢？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;const int N = 5e4 + 2 ;int n, q;int dpmax[N][21 ],dpmin[N][21 ];int p[N];int LOg2[N];void init () LOg2[0 ] = -1 ; for (int i = 1 ; i <= N; i++) LOg2[i] = LOg2[i >> 1 ] + 1 ; for (int i = 1 ; i <= n; i++) { dpmax[i][0 ] = p[i]; dpmin[i][0 ] = p[i]; } int t = LOg2[n]; for (int k = 1 ; k <= t; k++) { for (int s = 1 ; s + (1 << k) <= n + 1 ; s++) { dpmax[s][k] = max (dpmax[s][k-1 ], dpmax[s + (1 << (k-1 ))][k - 1 ]); dpmin[s][k] = min (dpmin[s][k-1 ], dpmin[s + (1 << (k-1 ))][k - 1 ]); } } } int st_query (int l, int r) int k = LOg2[r - l + 1 ]; int x = max (dpmax[l][k], dpmax[r - (1 << k) + 1 ][k]); int y = min (dpmin[l][k], dpmin[r - (1 << k) + 1 ][k]); return x - y; } int main () cin >> n >> q; for (int i = 1 ; i <= n; i++) { cin >> p[i]; } init (); int l, r; for (int i = 1 ; i <= q; i++) { cin >> l >> r; cout << st_query (l, r) << endl; } return 0 ; }
差分
落谷3397
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int dp[1005 ][1005 ];int n, m;int main () cin >> n >> m; int x1, y1, x2, y2; for (int i = 1 ; i <= m; i++) { cin >> x1 >> y1 >> x2 >> y2; dp[x1][y1] += 1 ; dp[x2 + 1 ][y2 + 1 ] += 1 ; dp[x2 + 1 ][y1] -= 1 ; dp[x1][y2 + 1 ] -= 1 ; } for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { dp[i][j] += dp[i - 1 ][j] + dp[i][j - 1 ] - dp[i - 1 ][j - 1 ]; cout << dp[i][j] << " " ; } cout << endl; } return 0 ; }
落谷 3406
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int n, m;int a[100005 ];int p1, p2;int main () cin >> n >> m; if (m > 0 ) cin >> p1; for (int i = 2 ; i <= m; i++) { cin >> p2; if (p1 < p2) { a[p1]++, a[p2]--; } else { a[p2]++, a[p1]--; }p1 = p2; } int aa, b, c; long long ans = 0 ,sum = 0 ; for (int i = 1 ; i < n; i++) { sum += a[i]; cin >> aa >> b >> c; if (sum!=0 ) ans += min (aa * sum, b *sum + c); } if (m <= 1 ) ans = 0 ; cout << ans; return 0 ; }
落谷2280
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int n, m;int dp[5005 ][5005 ];int main () cin >> n >> m; int x, y, v; for (int i = 1 ; i <= n; i++) { cin >> x >> y >> v; dp[x + 1 ][y + 1 ] += v; } int ans = 0 ; for (int i = 1 ; i <= 5001 ; i++) { for (int j = 1 ; j <= 5001 ; j++) { dp[i][j] += dp[i - 1 ][j] + dp[i][j - 1 ] - dp[i - 1 ][j - 1 ]; } } for (int i = m; i <= 5001 ; i++) { for (int j = m; j <= 5001 ; j++) { int num = dp[i][j] - dp[i - m][j] - dp[i][j - m] + dp[i - m][j - m]; ans = max (ans, num); } } cout << ans; return 0 ; }
二维差分的主要思路就是如何构建二维差分的面积
要注意两种类型，就是一个位置的改变是影响一个区域还是后面一大片区域
落谷 3131
简单的前缀和会超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int n;int a[50005 ];int main () cin >> n; for (int i = 1 ; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1 ]; a[i] %= 7 ; } for (int len = n; len >= 1 ; len--) { for (int i = 1 , j = i + len - 1 ; j <= n; i++, j++) { int an = a[j] - a[i-1 ]; if (an % 7 ==0 ) { cout << len; return 0 ; } } } cout << 0 ; return 0 ; }
我们要改变思路了
若两个数相减 ( mod (mod 7=0)7=0) ，那么这两个数 mod mod 77 的余数一定相同！！（很好证明，自己有兴趣不妨去试试证明）
只要求出相同的一个余数第一次和最后一次之间的长度即是最长长度！ 但是我们不知道哪个余数最长，所以：
枚举 0 ~ 6 共 7 个余数各自的最长长度，再在他们 7 个里找最长的！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int n;int a[50005 ];int first[7 ], last[7 ];int main () cin >> n; for (int i = 1 ; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1 ]; a[i] %= 7 ; } for (int i = n; i >= 1 ; i--) { first[a[i]] = i; } first[0 ] = 0 ; for (int i = 1 ; i <= n; i++) { last[a[i]] = i; } int ans = 0 ; for (int i = 0 ; i < 7 ; i++) { ans = max (ans, last[i] - first[i]); } cout << ans; return 0 ; }
cf2000
遇到的困难，在不是 1 的时候没有更新面积，而且判断条件有问题，没注意是字符 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std;int n;int dp[100 ][100 ];int main () cin >> n; string s; for (int i = 1 ; i <= n; i++) { cin >> s; for (int j = 1 ; j <= n; j++) { dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] - dp[i - 1 ][j - 1 ] + (s[j - 1 ] == '1' ); } } for (int len = 1 ; len <= n; len++) { int cnt = 0 ; for (int i = len; i <= n; i++) { for (int j = len; j <= n; j++) { int a = dp[i][j] - dp[i - len][j] - dp[i][j - len] + dp[i - len][j - len]; if (a*2 == len*len) { cnt++; } } } cout << cnt << endl; } }
