文章目录

• • 1.连号区间数（枚举💡skill）
  • 2.递增三元组（❤️前缀和/二分❤️）
  • 3.特别数的和（模拟）
  • 4.回文日期（枚举/LocalDate👍）
  • 5.归并排序
  • 6.移动距离（模拟/new💡）
  • 7.日期问题
  • 8.航班时间(转换题意)

1.连号区间数（枚举💡skill）

思路：
小技巧：如果在区间[L,R]中，maxnn-minnR-L,则说明[L,R]区间的数是递增的。
很多时候都会用到
对于此题，我们只需要枚举l.r判断是否满足此关系式即可。如果满足那么这个区间的数排序后肯定是递增且连续的。

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 10010;static int[] a= new int[N];static int n = 0,ans = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}for(int i = 1; i <= n; i++) {int maxn = a[i];int minn = a[i];for(int j = i; j <= n; j++) {maxn = Math.max(maxn, a[j]);minn = Math.min(minn,a[j]);if(j - i == maxn - minn) {ans++;}}}out.println(ans);out.flush();}
}

2.递增三元组（❤️前缀和/二分❤️）

💡💡💡法1：前缀和
借助B当作中间数，查找A中有多少个比B小的，C中有多少个比B大的；
我们需要记住A和C中每个数字出现的次数，采用num_a，num_c表示每个数出现的次数。
借助临时数组s[]表示所有数出现次数的前缀和。sum_a[]表示A的前缀和，sum_c[]表示c的前缀和

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 100010;static int[] a= new int[N];static int[] b= new int[N];static int[] c= new int[N];static int[] num_a= new int[N];static int[] num_c= new int[N];static int[] sum_a= new int[N];static int[] sum_c= new int[N];static int[] s = new int[N];static int n = 0;static long ans = 0;public static void main(String[] args) throws Exception{input();for(int i = 1; i < N; i++) {s[i] = s[i - 1] + num_a[i];//a中1-i所有数出现的总数}for(int i = 1; i <= n; i++) {sum_a[i] = s[b[i] - 1]; //小于bi的数有多少个}Arrays.fill(s, 0);for(int i = 1; i < N; i++) {//注意此时的数据范围s[i] = s[i - 1] + num_c[i];//a中1-i所有数出现的总数}for(int i = 1; i <= n; i++) {sum_c[i] = s[N - 1] - s[b[i]]; //大于b[i]的数有多少个}for(int i = 1; i <= n;i++) {ans = ans + (long)sum_a[i] * sum_c[i];}out.println(ans);out.flush();}private static void input() throws Exception, Exception {n = Integer.parseInt(br.readLine());String[]aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]) + 1;num_a[a[i]]++;}String[]bb = br.readLine().split(" ");for(int i = 1; i <= n; i++) {b[i] = Integer.parseInt(bb[i - 1]) + 1;}String[]cc = br.readLine().split(" ");for(int i = 1; i <= n; i++) {c[i] = Integer.parseInt(cc[i - 1]) + 1;num_c[c[i]]++;}}
}

💡💡💡法2：二分
依旧是以B为分割点，将A和C数组排序，此时满足单调性，我们在A中找小于target的最后一个，在C中找大于target的第一个（后面的元素肯定都是大于target的）然后相乘即可。

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 100010;static int[] a= new int[N];static int[] b= new int[N];static int[] c= new int[N];static int[] num_a= new int[N];static int[] num_c= new int[N];static int[] sum_a= new int[N];static int[] sum_c= new int[N];static int[] s = new int[N];static int n = 0;static long ans = 0;public static void main(String[] args) throws Exception{input();Arrays.sort(a,1,1+n);Arrays.sort(c,1,1+n);for(int i = 1; i <= n; i++) {int target = b[i];int la = findLess(target);int lc = findMore(target);
//			System.out.println(la +" " +lc);ans = ans + (long)la*lc;}System.out.println(ans);}//找大于的第一个private static int findMore(int target) {int l = 1, r = n;int res = -1;while(l <= r) {int mid = (l + r) >> 1;if(c[mid] > target) {res = mid;r = mid - 1;}else {l = mid + 1;}}if(res == -1) {return 0;}else {return (n - res + 1);}}//找小于的最后一个private static int findLess(int target) {int l = 1, r = n;int res = -1;while(l <= r) {int mid = (l +r) >> 1;if(a[mid] < target) {res = mid;l = mid + 1;}else {r = mid - 1;}}if(res == -1) {return 0;}else {return res;}}private static void input() throws Exception, Exception {n = Integer.parseInt(br.readLine());String[]aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}String[]bb = br.readLine().split(" ");for(int i = 1; i <= n; i++) {b[i] = Integer.parseInt(bb[i - 1]);}String[]cc = br.readLine().split(" ");for(int i = 1; i <= n; i++) {c[i] = Integer.parseInt(cc[i - 1]);}}
}

3.特别数的和（模拟）

很简单，n很小直接取出n的每一位去判断即可。

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0;static long ans = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());for(int i = 1; i <= n; i++) {if(check(i)) {ans = ans + (long)i;}}System.out.println(ans);}private static boolean check(int x) {while(x != 0) {int t = x%10;if(t == 2 || t == 0 || t == 1 || t == 9) {return true;}x/=10;}return false;}
}

思路：直接记录每个数字出现的次数，在最大值和最小值之间出现2次的肯定是重号，出现0次的肯定是断号。

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0;static long ans = 0;static int minn = (int) (1e5 + 10),maxn = -1;static int[] count = new int[100010];public static void main(String[] args) throws Exception{int t = Integer.parseInt(br.readLine());while(t-- > 0) {//			Arrays.fill(count, 0);String[] aa = br.readLine().split(" ");for(int i = 0; i < aa.length; i++) {int num = Integer.parseInt(aa[i]);maxn = Math.max(maxn, num);minn = Math.min(minn,num);count[num]++;}}int c = 0,d = 0;for(int i = minn; i <= maxn; i++) {if(count[i] == 2) {c = i;}if(count[i] == 0) {d = i;}}out.println(d + " " + c);out.flush();}
}

4.回文日期（枚举/LocalDate👍）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.time.LocalDate;
import java.util.Arrays;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0;static long ans = 0;public static void main(String[] args) throws Exception{String str1 = br.readLine();int y1 = Integer.parseInt(str1.substring(0,4));int m1 = Integer.parseInt(str1.substring(4,6));int d1 = Integer.parseInt(str1.substring(6,8));String str2 = br.readLine();int y2 = Integer.parseInt(str2.substring(0,4));int m2 = Integer.parseInt(str2.substring(4,6));int d2 = Integer.parseInt(str2.substring(6,8));LocalDate t1= LocalDate.of(y1, m1, d1);//创建指定日期的LocalDateLocalDate t2= LocalDate.of(y2, m2, d2);while(!t1.isEqual(t2)) {String t = t1.toString();if(check(t)) {ans++;}t1 = t1.plusDays(1); //向后跳转1天}String t = t1.toString();//需要注意当两天重合的时候，需要判断一下if(check(t)) {ans++;}System.out.println(ans);}private static boolean check(String t) {//String类型可以保存前导0，如果转为数字再操作的话可能丢失前导0String[]x = t.split("-");String t1 = x[0] + x[1] + x[2];
//		System.out.println(t1);StringBuilder t2 = new StringBuilder(t1);t2.reverse(); String t3 = t2.toString();//必须采用String类型的变量来接收if(t1.equals(t3)) {return true;}return false;}
}

5.归并排序

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[]is1 = new int[N];static int[]is2 = new int[N];static int n = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {is1[i] = Integer.parseInt(aa[i - 1]);}mergesort(1,n);for(int i = 1; i <= n; i++) {System.out.print(is1[i] + " ");}}private static void mergesort(int l, int r) {if(l >= r)return;int mid = (l + r) /2 ;mergesort(l, mid);mergesort(mid + 1, r);merge(l,mid,r);}private static void merge(int l, int mid, int r) {int i = l,j = mid + 1, k = l;while(i <= mid && j <= r) {if(is1[i] < is1[j]) {is2[k++] = is1[i++];}else {is2[k++] = is1[j++];}}while(i <= mid) {is2[k++] = is1[i++];}while(j <= r) {is2[k++] = is1[j++];}for(i = l; i <= r; i++) {is1[i] = is2[i];}}}

6.移动距离（模拟/new💡）

思路：
两个楼之间的最短距离就是曼哈顿距离，很明显我们需要找出m和n的坐标，对宽度w取模我们可以得到行号，列号的话与所在行的奇偶有关，奇数行是正序，偶数行是逆序的（画个图理解一下）就可以找到

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,w = 0, m = 0;public static void main(String[] args) throws Exception{String[] wmn = br.readLine().split(" ");boolean rev = false;w = Integer.parseInt(wmn[0]);m = Integer.parseInt(wmn[1]);n = Integer.parseInt(wmn[2]);int fir[] = count(m);int sec[] = count(n);System.out.println(Math.abs(fir[0]-sec[0]) + Math.abs(fir[1] - sec[1]));}static int[] count(int x) {//temp[0]是行号，temp[1]是列号int []temp = new int[2];int mod = x % w; //列号if(x%w == 0){temp[0] = x/w;}else{temp[0] = x/w + 1;}int p = temp[0] % 2;//记录行号的奇偶if(p == 1){if(mod==0){temp[1] = w;}else{temp[1] = mod;}}else{if(mod == 0){temp[1] = 1;}else{temp[1] = w - mod + 1;}}return temp;}
}

7.日期问题

思路：现在给定范围内进行枚举，然后判断是否为合法日期，最后看是否与所给的数相匹配，我们枚举的时候就已经实现了按照升序排序。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};static int n = 0,w = 0, m = 0;static int a = 0, b = 0, c = 0;public static void main(String[] args) throws Exception{String[]d = br.readLine().split("/");a = Integer.parseInt(d[0]);b = Integer.parseInt(d[1]);c = Integer.parseInt(d[2]);for(int i = 19600101; i <= 20591231;i ++) {int year = i / 10000, month = i % 10000 / 100,day = i % 100;if(check(year,month,day)) {if(com(year%100,month,day)||com(month,day,year%100)||com(day,month,year%100)) {out.printf("%d-%02d-%02d\n",year,month,day);}}}out.flush();out.close();}private static boolean check(int year, int month, int day) {if(month == 0 || month > 12) {return false;}if(day == 0) {return false;}if(((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))){days[2] = 29;}else {days[2] = 28;}if(day > days[month]) {return false;}return true;}private static boolean com(int year, int month, int day) {if(year == a && month == b && day == c) {return true;}return false;}}

8.航班时间(转换题意)

思路：因为保证飞行时间不超过24小时，所以d一定是1位数。
本题的难点主要是转换题意，因为题意比较抽象，代码实现并不难（一般此时我们需要借助数学的思想去转换题意）

我们可以得出：
(1)去程起飞时间+飞行时间x+时差=去程降落时间；
(2)返程起飞时间+飞行时间x-时差=返程降落时间；
我们需要求的是飞行时间x（1）+（2）得到：
去程起飞时间+2*飞行时间x+返程起飞时间=去程降落时间+返程降落时间；
x=（(去程降落时间-去程起飞时间)+（返程降落时间-返程起飞时间））/2

下面直接根据公式进行计算就可以了。

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,w = 0, m = 0;static int a = 0, b = 0, c = 0;public static void main(String[] args) throws Exception{int t = Integer.parseInt(br.readLine());while(t-- > 0) {String[] go = br.readLine().split(" ");String[] back = br.readLine().split(" ");int d1 = 0,d2 = 0;String[]g1 = go[0].split(":");//去升的时间String[]b1 = go[1].split(":");//去降的时间String[]g2 = back[0].split(":");//回来升的时间String[]b2 = back[1].split(":");//回来降的时间if(go.length == 3) {d1 = go[2].charAt(2) - '0';}if(back.length == 3) {d2 = back[2].charAt(2) - '0';}int ans1 = get_seconds(b1,d1) - get_seconds(g1,0);int ans2 = get_seconds(b2,d2) - get_seconds(g2,0);int ans = (ans1 + ans2)/2;int hh = ans/3600;int mm = ans%3600/60;int ss = ans % 60;System.out.printf("%02d:%02d:%02d\n",hh,mm,ss);}}private static int get_seconds(String[] t, int d1) {int tol = 0;int h = Integer.parseInt(t[0]);int min = Integer.parseInt(t[1]);int sed = Integer.parseInt(t[2]);tol = d1*24*60*60 + h *60 * 60 + min*60 + sed;return tol;}}