【蓝桥杯集训3】二分专题（3 / 5）

目录

二分模板

1460. 我在哪？ - 二分答案 + 哈希表

1221. 四平方和 - 哈希表 / 二分

1、哈希表

2、二分 + 自定义排序

1227. 分巧克力 - 

113. 特殊排序 -  

---

二分模板

• l + r >> 1 —— 先 r = mid 后 l = mid+1 —— 寻找左边界 —— 找大于某个数的最小值
• l+r+1>>1 —— 先 l = mid 后 r = mid-1 —— 寻找右边界 —— 找小于某个数的最大值

活动 - AcWing 

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),t=sc.nextInt();int[] a=new int[n];for(int i=0;i<n;i++) a[i]=sc.nextInt();while(t-->0){int x=sc.nextInt();int l=0,r=n-1;while(l<r){int mid=l+r>>1;if(a[mid]>=x) r=mid;else l=mid+1;}if(a[r]!=x) {System.out.println(-1+" "+-1);continue;}System.out.print(r+" ");l=0;r=n-1;while(l<r){int mid=l+r+1>>1;if(a[mid]<=x) l=mid;else r=mid-1;}System.out.println(r);}}
}

1460. 我在哪？ - 二分答案 + 哈希表

1460. 我在哪？ - AcWing题库

题目：

约翰想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置.
最小的K值，意思是要找到最小长度为K的子串并且只出现过一次

思路：

二分答案K值

用哈希表存前面出现过的子串，如果后面长度为k的子串在哈希表存在过，说明后面的子串在前面出现过，说明该k值小，答案应该增大

最后二分出满足要求的最小k值

import java.util.*;class Main
{static String s="";public static boolean ck(int len,String s){int n=s.length();Set<String> st=new HashSet<>();for(int i=0;i+len-1<n;i++){String t=s.substring(i,i+len);if(st.contains(t)) return false; //如果后面存在前面出现过的st.add(t);}return true;}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();String s=sc.next();int l=1,r=n;while(l<r){int mid=l+r>>1;if(ck(mid,s)) r=mid;else l=mid+1;}System.out.print(l);}
}

 

1221. 四平方和 - 哈希表 / 二分

活动 - AcWing

题目：

思路：

a,b,c,d的枚举范围为，四重循环会tle

所以我们只能枚举两个数
因此我们需要用空间换时间
先将  存起来降低时间复杂度

1、哈希表

因为要按0≤a≤b≤c≤d顺序，存第一个表示法

所以对于cd组合，d从c开始枚举，将  对应的c和d存起来

因为cd是从小到大枚举的，所以如果后面再次出现相同的sum值，就跳过，只存第一次的

对于ab组合，b从a开始枚举，确定后，一定存在对应的

因为ab是从小到大枚举的，所以当出现对应的sum值时，直接输出，return

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();Map<Integer,int[]> mp=new HashMap<>();for(int c=0;c*c<=n;c++)for(int d=c;d*d+c*c<=n;d++){int t=d*d+c*c;if(!mp.containsKey(t)) mp.put(t,new int[] {c,d});}for(int a=0;a*a<=n;a++)for(int b=a;b*b+a*a<=n;b++){int x=n-a*a-b*b;int[] tp=mp.get(x);if(mp.containsKey(x)){System.out.print(a+" "+b+" "+tp[0]+" "+tp[1]);return;}}}
}

2、二分 + 自定义排序

对cd组合结果进行排序

在枚举ab组合时，二分满足条件的cd组合

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();List<int[]> list=new ArrayList<>();for(int c=0;c*c<=n;c++)for(int d=c;d*d+c*c<=n;d++){int t=d*d+c*c;list.add(new int[]{t,c,d});}list.sort(new Comparator<int[]>(){public int compare(int[] o1,int[] o2){if(o1[0]!=o2[0]) return o1[0]-o2[0]; //从大到小if(o1[1]!=o2[1]) return o1[1]-o2[1];return o1[2]-o2[2];}});    for(int a=0;a*a<=n;a++)for(int b=a;b*b+a*a<=n;b++){int x=n-a*a-b*b;int l=0,r=list.size()-1;while(l<r){int mid=l+r>>1;if(list.get(mid)[0]>=x) r=mid;else l=mid+1;}if(list.get(l)[0]==x){int c=list.get(l)[1];int d=list.get(l)[2];System.out.print(a+" "+b+" "+c+" "+d);return;}}}
}

1227. 分巧克力 - 

活动 - AcWing

题目：

思路：

 

113. 特殊排序 -  

活动 - AcWing

题目：

思路：