题目理解题目n 条线段m 个查询区间[L,R]。 如果某条线段至少一半长度落在查询区间[L,R]里面就代表这条线段被框住。求每个查询能框住多少条线段。证明 线段中点落在查询区间[L,R]说明中点被包住那么至少有半段线段在区间内 反过来如果线段有至少一半长度被查询区间包住那么中点一定落在查询区间内。 问题转化 把 n 条线段的中点全部拿出来排序。 对于每次查询[L,R]求排序后的中点数组里有多少个数落在区间[L,R]之间。 也就是二分查找找左边界≥L 的第一个位置、右边界≤R 最后一个位置个数 右 - 左 1题目0抓娃娃 - 蓝桥云课 (lanqiao.cn)因为这个限制所以不用担心线段比区间长线段一定比区间短的话想要判断是否线段的二分之一及以上在区间内则可以转化为线段中点是否在区间内的问题如果没有那个限制那么就无法这么考虑了因为即使中点在区间内也保证不了二分之一及以上在区间内最新题解#include bits/stdc.h #define int long long #define endl \n using namespace std; int n,m; // xian数组存储每条线段的中点可能是小数所以double // qu[m][0]是查询Lqu[m][1]查询R double xian[100005],qu[100005][2]; void solve(){ cinnm; for(int i1;in;i)// 下标从1开始方便二分边界处理因为二分要开区间 { int l,r; cinlr; // 计算中点必须除以2.0得到浮点数不能整数右移 1 // 如果写 (lr)/2 整数除法会丢失小数中点算错 xian[i](lr)/2.0; } // 对中点数组排序二分的前提xian[1]~xian[n] // 一定要1因为二分要开区间所以首地址和最后一个地址不存东西 sort(xian1,xian1n);// sort接收首地址、尾后地址 // 读入m个查询区间 for(int i0;im;i){ cinqu[i][0]qu[i][1]; } // 依次处理每个查询 for(int i0;im;i){ double L qu[i][0]; double R qu[i][1]; // 二分1找第一个 L 的中点位置 l // 最小化答案r始终走在可行区域 int l10,r1n1; // 二分区间 [0, n1)虚拟哨兵边界开区间 while(l11r1){ int midl1r11; // 等价 (l1r1)/2 if(xian[mid]L) r1mid; else l1mid; } int l r1; // l是满足中点L的最左下标 // 二分2找最后一个 R 的中点位置 r // 最大化答案l始终走在可行区域 l10,r1n1; while(l11r1){ int midl1r11; if(xian[mid]R) l1mid; else r1mid; } int r l1; // r是满足中点R的最右下标 // 数量r-l1 coutr-l1endl; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }曾经题解#include bits/stdc.h #define int long long #define endl \n using namespace std; //区间包含线段的问题转化为区间包含点的问题 int n,m; void solve(){ cinnm; //线段的中点,注意要double类型因为计算中点可能有小数 vectordouble x(n); //区间的两个端点 vectorpairint,int y(m); for(int i0;in;i){ double a,b; cinab; x[i](ab)/2; } for(int i0;im;i){ //pair类型的第一个值和第二个值的获取方式 ciny[i].firsty[i].second; } //排序因为要二分二分必须要排序 sort(x.begin(),x.end()); //遍历每个区间 for(int i0;im;i){ //当前区间的两个端点 int Ly[i].first,Ry[i].second; //二分找出 符合条件(线段中点在区间内)的线段中点区间的左界限 int l10,r1n-1; while(l1r1){ int mid(l1r1)1; if(x[mid]L){ l1mid1; }else{ r1mid; } } //二分找出 符合条件(线段中点在区间内)的线段中点区间的右界限 int l20,r2n-1; while(l2r2){ int mid(l2r21)1; if(x[mid]R){ l2mid; }else{ r2mid-1; } } //要判断一下因为有可能该区间内一条符合的线段都没有 if(x[l1]Lx[l2]R){ coutl2-l11endl; }else{ cout0endl; } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }笔记重点坑点总结考试必看中点不能用整数计算(lr)/2整数除法会舍去小数。必须写(lr)/2.0得到 double 浮点数。 例 l1,r2中点是 1.5整数除法得到 1直接出错。二分写法采用「开区间二分」l10r1n1哨兵边界数组下标从 1~n0 和 n1 是虚拟位置防止越界。第一个二分找第一个 ≥ L的元素左边界 lower_bound第二个二分找最后一个 ≤ R的元素右边界 upper_bound 变形也可以直接用 STL 自带二分函数简化代码不用手写二分auto left lower_bound(xian1,xian1n, L); auto right upper_bound(xian1,xian1n, R); int ans right-left;手写二分用来练习二分原理比赛推荐 STL代码短不容易写错。STL 简化版本对比参考更短#include bits/stdc.h #define int long long #define endl \n using namespace std; const int N1e510; double mid[N]; void solve(){ int n,m; cinnm; for(int i1;in;i){ int l,r; cinlr; mid[i](lr)/2.0; } sort(mid1,mid1n); while(m--){ int L,R; cinLR; // lower_bound第一个 L auto lp lower_bound(mid1,mid1n, L); // upper_bound第一个 R auto rp upper_bound(mid1,mid1n, R); cout rp-lp \n; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0); solve(); return 0; }
题目理解题目n 条线段m 个查询区间[L,R]。 如果某条线段至少一半长度落在查询区间[L,R]里面就代表这条线段被框住。求每个查询能框住多少条线段。证明 线段中点落在查询区间[L,R]说明中点被包住那么至少有半段线段在区间内 反过来如果线段有至少一半长度被查询区间包住那么中点一定落在查询区间内。 问题转化 把 n 条线段的中点全部拿出来排序。 对于每次查询[L,R]求排序后的中点数组里有多少个数落在区间[L,R]之间。 也就是二分查找找左边界≥L 的第一个位置、右边界≤R 最后一个位置个数 右 - 左 1题目0抓娃娃 - 蓝桥云课 (lanqiao.cn)因为这个限制所以不用担心线段比区间长线段一定比区间短的话想要判断是否线段的二分之一及以上在区间内则可以转化为线段中点是否在区间内的问题如果没有那个限制那么就无法这么考虑了因为即使中点在区间内也保证不了二分之一及以上在区间内最新题解#include bits/stdc.h #define int long long #define endl \n using namespace std; int n,m; // xian数组存储每条线段的中点可能是小数所以double // qu[m][0]是查询Lqu[m][1]查询R double xian[100005],qu[100005][2]; void solve(){ cinnm; for(int i1;in;i)// 下标从1开始方便二分边界处理因为二分要开区间 { int l,r; cinlr; // 计算中点必须除以2.0得到浮点数不能整数右移 1 // 如果写 (lr)/2 整数除法会丢失小数中点算错 xian[i](lr)/2.0; } // 对中点数组排序二分的前提xian[1]~xian[n] // 一定要1因为二分要开区间所以首地址和最后一个地址不存东西 sort(xian1,xian1n);// sort接收首地址、尾后地址 // 读入m个查询区间 for(int i0;im;i){ cinqu[i][0]qu[i][1]; } // 依次处理每个查询 for(int i0;im;i){ double L qu[i][0]; double R qu[i][1]; // 二分1找第一个 L 的中点位置 l // 最小化答案r始终走在可行区域 int l10,r1n1; // 二分区间 [0, n1)虚拟哨兵边界开区间 while(l11r1){ int midl1r11; // 等价 (l1r1)/2 if(xian[mid]L) r1mid; else l1mid; } int l r1; // l是满足中点L的最左下标 // 二分2找最后一个 R 的中点位置 r // 最大化答案l始终走在可行区域 l10,r1n1; while(l11r1){ int midl1r11; if(xian[mid]R) l1mid; else r1mid; } int r l1; // r是满足中点R的最右下标 // 数量r-l1 coutr-l1endl; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }曾经题解#include bits/stdc.h #define int long long #define endl \n using namespace std; //区间包含线段的问题转化为区间包含点的问题 int n,m; void solve(){ cinnm; //线段的中点,注意要double类型因为计算中点可能有小数 vectordouble x(n); //区间的两个端点 vectorpairint,int y(m); for(int i0;in;i){ double a,b; cinab; x[i](ab)/2; } for(int i0;im;i){ //pair类型的第一个值和第二个值的获取方式 ciny[i].firsty[i].second; } //排序因为要二分二分必须要排序 sort(x.begin(),x.end()); //遍历每个区间 for(int i0;im;i){ //当前区间的两个端点 int Ly[i].first,Ry[i].second; //二分找出 符合条件(线段中点在区间内)的线段中点区间的左界限 int l10,r1n-1; while(l1r1){ int mid(l1r1)1; if(x[mid]L){ l1mid1; }else{ r1mid; } } //二分找出 符合条件(线段中点在区间内)的线段中点区间的右界限 int l20,r2n-1; while(l2r2){ int mid(l2r21)1; if(x[mid]R){ l2mid; }else{ r2mid-1; } } //要判断一下因为有可能该区间内一条符合的线段都没有 if(x[l1]Lx[l2]R){ coutl2-l11endl; }else{ cout0endl; } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }笔记重点坑点总结考试必看中点不能用整数计算(lr)/2整数除法会舍去小数。必须写(lr)/2.0得到 double 浮点数。 例 l1,r2中点是 1.5整数除法得到 1直接出错。二分写法采用「开区间二分」l10r1n1哨兵边界数组下标从 1~n0 和 n1 是虚拟位置防止越界。第一个二分找第一个 ≥ L的元素左边界 lower_bound第二个二分找最后一个 ≤ R的元素右边界 upper_bound 变形也可以直接用 STL 自带二分函数简化代码不用手写二分auto left lower_bound(xian1,xian1n, L); auto right upper_bound(xian1,xian1n, R); int ans right-left;手写二分用来练习二分原理比赛推荐 STL代码短不容易写错。STL 简化版本对比参考更短#include bits/stdc.h #define int long long #define endl \n using namespace std; const int N1e510; double mid[N]; void solve(){ int n,m; cinnm; for(int i1;in;i){ int l,r; cinlr; mid[i](lr)/2.0; } sort(mid1,mid1n); while(m--){ int L,R; cinLR; // lower_bound第一个 L auto lp lower_bound(mid1,mid1n, L); // upper_bound第一个 R auto rp upper_bound(mid1,mid1n, R); cout rp-lp \n; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0); solve(); return 0; }
