吴中网站建设,微信小程序网页制作,主机托管是指,开发工具箱一、2013年真题
1、世纪末的星期
使用日期类判断就行#xff0c;这里使用LocalDate#xff0c;也可以使用Calendar类 答案 2099
使用LocalDate
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
// 1:无需package
// 2: 类名必须Main, 不可修改p…一、2013年真题
1、世纪末的星期
使用日期类判断就行这里使用LocalDate也可以使用Calendar类 答案 2099
使用LocalDate
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {for(int i 20; ; i) {StringBuilder s new StringBuilder();s.append(i).append(99).append(-12-31);// 解析字符串为日期并且格式化DateTimeFormatter formatter DateTimeFormatter.ofPattern(yyyy-MM-dd);LocalDate date LocalDate.parse(s.toString(), formatter);// getDayOfWeek()返回大写英文星期表示if(date.getDayOfWeek().toString().equals(SUNDAY)) {System.out.println(i 99);break;}}}
}使用Calendar
import java.util.Scanner;
import java.util.Calendar;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {// getInstance方法返回一个Calendar对象其日历字段已使用当前日期和时间进行初始化Calendar cal Calendar.getInstance();for(int y 2099; y9999;y 100) {// Calendar类中的月份是从0开始编号一直到11的// 所以12月份的编号是11cal.set(y, 11, 31);// 星期天到星期六为一周编号1-7if(cal.get(Calendar.DAY_OF_WEEK)1) {System.out.println(y); break;}}}
}2、马虎的算式
使用暴力法遍历即可注意5个数字各不相同 答案142
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {int cnt 0;for(int a 1; a 9; a) {for(int b 1; b 9; b) {if(a ! b) {for(int c 1; c 9; c) {if(a ! c b ! c) {for(int d 1; d 9; d) {if(a ! d b ! d c ! d) {for(int e 1; e 9; e) {if(a ! e b ! e c ! e d ! e) {if((a*10 b)*(c*100d*10e) (a*100d*10b)*(c*10e))cnt;}}}}}}}}}System.out.println(cnt);}
}3、振兴中华
因为一共走7步横着走4步竖着3步所以根据组合知识得答案为 C(7,3) 35 使用递归编码如下
import java.util.Scanner;public class Main {public static void main(String[] args) {System.out.println(fun(0,0));}private static int fun(int x, int y) {// 横着走了4步或竖着走了3步一定会到达终点if(x 3 || y 4)return 1;else return fun(x1, y) fun(x, y1);}
}4、黄金连分数
使用BigInteger和BigDecimal 解析:
要将本题转换为斐波那契数列就是求两个很大的斐波那契数列相邻两项相除用BigDecimal计算结果使用BigDecimal的除法时若结果为无限小数则要指定运算的范围 即被除数.divid(除数,范围,BigDecimal_ROUND_HALF_DOWN);求小数点后的100位需要运算结果在101位及之前达到稳定即传值增大第101位的数字不在变化。“0.” 在截取字符串时占了两位.
import java.math.BigDecimal;
import java.math.BigInteger;public class Main {public static void main(String[] args) {fun();}private static void fun() {BigInteger a BigInteger.ONE;BigInteger b BigInteger.ONE;for(int i 3; i 500; i) {BigInteger t b;b a.add(b);a t;}BigDecimal divide new BigDecimal(a).divide(new BigDecimal(b), 100, BigDecimal.ROUND_HALF_EVEN);System.out.println(divide);}
}5、错误票据
使用数组记录次数
import java.io.InputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int[] arr new int[100005];int a 0, b 0;int max 0, min 0;// 这里必须n是为了处理行末可能的空格for(int i 0; i n; i) {// 因为每行数据个数不确定所以接受一整行再判断是否到达行末Scanner sc new Scanner(in.nextLine());while(sc.hasNext()) {int x sc.nextInt();if(arr[x] 1)b x; // 重复数字arr[x];min Math.min(min, x);max Math.max(max, x);}}for(int i min; i max; i) {if(arr[i] 0){a i;break;}}System.out.println(a b);}
}6、幸运数
题目描述 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成 。 首先从1开始写出自然数1,2,3,4,5,6,… 1 就是第一个幸运数。 我们从2这个数开始。把所有序号能被2整除的项删除变为 1 _ 3 _ 5 _ 7 _ 9 … 把它们缩紧重新记序为 1 3 5 7 9 … 。这时3为第2个幸运数然后把所有能被3整除的序号位置的数删去。注意是序号位置不是那个数本身能否被3整除!! 删除的应该是511, 17, … 此时7为第3个幸运数然后再删去序号位置能被7整除的(19,39,…) 最后剩下的序列类似 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, … 输入格式 输入两个正整数m n, 用空格分开 (m n 1000*1000) 输出格式 程序输出 位于m和n之间的幸运数的个数不包含m和n。 样例输入 30 69 样例输出 8
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int m in.nextInt();int n in.nextInt();int[] arr new int[n];for(int i 0; i n;i) {arr[i] i*21;}int l 1;while(l n arr[l] n) {int p l1;for(int i l 1; i n; i) {// 当不是倍数时向前移动if((i1) % arr[l] ! 0) {arr[p] arr[i];}}l;if(arr[l] n)break;}int ans 0;for(int i 0; i n;i) {if(arr[i] n)break;if(arr[i] m)ans;}System.out.println(ans);}
}7、带分数
全排列的应用
import java.util.Scanner;public class Main {static int N;static int ans 0;public static void main(String[] args) {Scanner in new Scanner(System.in);N in.nextInt();int[] arr {1,2,3,4,5,6,7,8,9};dfs(arr, 0);System.out.println(ans);//System.out.println(toInt(arr, 2, 5));}private static void dfs(int[] arr, int k) {if(k 9) {check(arr);return;}// 回溯法生成1-9的全排列for(int i k; i arr.length; i) {swap(arr, k, i);dfs(arr, k1);swap(arr, k, i); // 交换回去回溯}}private static void swap(int[] arr, int i, int j) {int t arr[i];arr[i] arr[j];arr[j] t;}// 枚举 / 的位置private static void check(int[] arr) {// 号前面最多7个数字for(int i 1; i 7; i) {int num1 toInt(arr, 0, i);if(num1 N)break;for(int j 1; j 8-i; j) {int num2 toInt(arr, i, j);int num3 toInt(arr, ij, 9-i-j);if(num2%num3 0 num1 num2/num3 N)ans;}}}// 转换为intprivate static int toInt(int[] arr, int pos, int len) {int n 0;int t 1;for(int i poslen-1; i pos; i--) {n arr[i]*t;t*10;}return n;}
}8、连号区间数
区间最大值-最小值区间间距说明区间连号
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int[] arr new int[n];for(int i 0; i n; i)arr[i] in.nextInt();int ans 0;for(int i 0; i n; i) {int max arr[i];int min arr[i];for(int j i; j n; j) {if(arr[j] min)min arr[j];if(arr[j] max)max arr[j];if(i j)ans;else {if(max-min j - i)ans;}}}System.out.println(ans);}
}二、2014年真题
1、地宫取宝
2、分糖果
package project2014;import java.util.Scanner;public class 分糖果 {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int[] arr new int[n];for(int i 0; i n; i) {arr[i] in.nextInt();}int ans 0;int len arr.length;while(!check(arr)) {for (int i 0; i len; i) {arr[i] / 2;}int t arr[0];for (int i 0; i len-1; i) {arr[i] arr[i1];}arr[len-1] t;for (int i 0; i len; i) {if((arr[i] 1) 1) {arr[i] ;ans;}}}System.out.println(ans);}private static boolean check(int[] arr) {for (int i 1; i arr.length; i) {if(arr[i] ! arr[0])return false;}return true;}
}3、矩阵翻硬币
涉及大整数运算使用BigInteger。
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);String m in.next();String n in.next();System.out.println(sqrt(m).multiply(sqrt(n)));}private static BigInteger sqrt(String s) {int len s.length();int len1 0;if((len 1) 0) {len1 len/2;}else {len1 len/21;}char[] arr new char[len1];Arrays.fill(arr, 0); // 初始化BigInteger target new BigInteger(s);for(int pos 0; pos len1; pos) {for(char c 1; c 9; c) {arr[pos] c;BigInteger num new BigInteger(String.valueOf(arr)).pow(2);if(num.compareTo(target) 1) {arr[pos] - 1;break;}}}return new BigInteger(String.valueOf(arr));}
}
4、扑克序列
全排列然后找出符合条件的最后用肉眼看哪个字典序最小
package project2014;import java.util.HashSet;
import java.util.Set;public class 扑克序列 {static char[] arr {A,A, 2,2,3,3,4,4};static SetString set new HashSetString();public static void main(String[] args) {dfs(0);set.forEach(System.out::println);}private static void dfs(int x) {if(x arr.length) {String s new String(arr);if(check(s))set.add(s); // 使用set可以去重}// 全排列模板for(int i x; i arr.length; i) {char t arr[x];arr[x] arr[i];arr[i] t;dfs(x1);// 恢复t arr[x];arr[x] arr[i];arr[i] t;}}private static boolean check(String s) {if(s.lastIndexOf(A) - s.indexOf(A) 2 s.lastIndexOf(2) - s.indexOf(2) 3 s.lastIndexOf(3) - s.indexOf(3) 4 s.lastIndexOf(4) - s.indexOf(4) 5)return true;else {return false;}}
}
5、奇怪的分式
枚举最大公约数
public class Main {public static void main(String[] args) {int ans 0;for(int a 1; a 9; a) {for(int b 1; b 9; b) {if(ab)continue;for(int c 1; c 9; c) {for(int d 1; d 9; d) {if(cd)continue;int x gcd(a*c, b*d);int y gcd(a*10c, b*10d);if(b*d/x (b*10d)/y a*c/x (a*10c)/y)ans;}}}}System.out.println(ans);}private static int gcd(int m, int n) {if(n 0)return m;else return gcd(n, m%n);}
}
6、猜字母 public class Main {public static void main(String[] args) {char[] arr new char[2014];int k 0;for(int i 1; i 106; i) {for(int j 0; j 19; j) {arr[k] (char)(aj);}}int len 2014;while(len 1) {int p 0;for(int i 1; i len; i2) {arr[p] arr[i];}len p;}System.out.println(arr[0]);}
}7、大衍数列
import java.util.*;
public class Main
{public static void main(String[] args){//大衍数列,主要用于解释中国传统文化中的太极衍生原理// 前几项0、2、4、8、12、18、24、32、40、50for(int i1; i20; i){if(i%20)System.out.print( i*i/2);elseSystem.out.print( (i*i-1)/2);}System.out.println();}
}三、2015年真题
1、立方变自身
枚举就行
public class Main {public static void main(String[] args) {int ans 0;for(int i 1; i 999; i) { // 枚举范围可以多试几个int x i*i*i;if(sum(x) i)ans;}System.out.println(ans);}private static int sum(int x) {int sum 0;while(x ! 0) {sum x%10;x / 10;}return sum;}
}2、三羊献瑞
全排列暴力查找
package project2014;public class 三羊献瑞 {static int[] arr {0,1,2,3,4,5,6,7,8,9};public static void main(String[] args) {dfs(0);}private static void dfs(int pos) {if(pos arr.length) {int s1 arr[0]*1000arr[1]*100arr[2]*10arr[3];int s2 arr[4]*1000arr[5]*100arr[6]*10arr[1];int s3 arr[4]*10000arr[5]*1000arr[2]*100arr[1]*10arr[7];if(s1s2s3) {System.out.println(s2);return;}}for(int i pos; i arr.length; i) {int t arr[pos];arr[pos] arr[i];arr[i] t;dfs(pos1);t arr[pos];arr[pos] arr[i];arr[i] t;}}
}3、方格填数
全排列
package project2015;public class 方格填数 {static int[] a {1,2,3,4,5,6,7,8,9,10};static int ans 0;public static void main(String[] args) {dfs(0);System.out.println(ans);}private static void dfs(int pos) {if(pos 10) {if(check())ans;}for(int i pos; i 10; i) {int t a[i];a[i] a[pos];a[pos] t;dfs(pos1);t a[i];a[i] a[pos];a[pos] t;}}private static boolean check() {int[][] arr new int[2][5];int k 0;for(int i 0; i 2; i) {for(int j 0; j 5; j) {arr[i][j] a[k];}}for(int i 0; i 2; i) {for(int j 0; j 5; j) {if((i 1 2) arr[i][j] arr[i1][j] || (j1 5) arr[i][j] arr[i][j1])return false;}}return true;}
}
4、饮料换购
自己在草稿纸上算一遍就知道过程
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int ans n;while(n 3) {int t n / 3;n t n%3;ans t;}System.out.println(ans);}
}
5、九数组分数
全排列找到符合的排列
import java.util.*;public class Main
{public static void test(int[] x){int a x[0]*1000 x[1]*100 x[2]*10 x[3];int b x[4]*10000 x[5]*1000 x[6]*100 x[7]*10 x[8];if(a*3b) System.out.println(a / b);} public static void f(int[] x, int k){if(kx.length){test(x);return;}for(int ik; ix.length; i){int tx[k]; x[k]x[i]; x[i]t;f(x,k1);tx[k]; x[k]x[i]; x[i]t;}}public static void main(String[] args){int[] x {1,2,3,4,5,6,7,8,9}; f(x,0);}
}四、2016年真题
1、凑算式
使用DFS生成全排列然后检查是否满足等式就行。注意两个分数通分后再计算
package project2016;public class 凑算式 {static int[] arr {1,2,3,4,5,6,7,8,9};static int ans 0;public static void main(String[] args) {dfs(0);System.out.println(ans);}private static void dfs(int pos) {if(pos 9) {if(check())ans;}for(int i pos; i 9; i) {int t arr[i];arr[i] arr[pos];arr[pos] t;dfs(pos1);t arr[i];arr[i] arr[pos];arr[pos] t;}}private static boolean check() {if(arr[1] 0)return false;int x arr[6]*100arr[7]*10arr[8];if(x 0)return false;int y arr[3]*100arr[4]*10arr[5];int fenzi arr[2]*xarr[1]*y;int fenmu arr[1]*x;if(fenzi % fenmu 0 arr[0] fenzi / fenmu 10)return true;else {return false;}}
}
2、方格填数 全排列然后使用最笨的办法–逐个位置进行判断
package project2016;public class 方格填数 {static int[] a {0,1,2,3,4,5,6,7,8,9};static int ans 0;public static void main(String[] args) {dfs(0);System.out.println(ans);}private static void dfs(int pos) {if(pos 10) {if(check())ans;}for(int i pos; i 10; i) {int t a[i];a[i] a[pos];a[pos] t;dfs(pos1);t a[i];a[i] a[pos];a[pos] t;}}private static boolean check() {if(abs(a[0] - a[1]) 1 || abs(a[0] - a[3]) 1 || abs(a[0] - a[4]) 1 || abs(a[0] - a[5]) 1)return false;if(abs(a[1] - a[2]) 1 || abs(a[1] - a[4]) 1 || abs(a[1] - a[5]) 1 || abs(a[1] - a[6]) 1)return false;if(abs(a[2] - a[5]) 1 || abs(a[2] - a[6]) 1 )return false;if(abs(a[3] - a[4]) 1 || abs(a[3] - a[7]) 1 || abs(a[3] - a[8]) 1)return false;if(abs(a[4] - a[5]) 1 || abs(a[4] - a[7]) 1 || abs(a[4] - a[8]) 1 || abs(a[4] - a[9]) 1)return false;if(abs(a[5] - a[6]) 1 || abs(a[5] - a[8]) 1 || abs(a[5] - a[9]) 1 )return false;if(abs(a[6] - a[9]) 1)return false;if(abs(a[7] - a[8]) 1)return false;if(abs(a[8] - a[9]) 1)return false;return true;}private static int abs(int x) {return Math.abs(x);}
}
3、剪邮票
这是一个比较难的题目 如果直接使用DFS深搜则带有T字形的结果无法得出因为DFS无法兼顾两个方向。 正确的解法是使用全排列随机选取5个格子使用DFS判断他们是否连通即判断3行4列的矩阵中是否只有一个连通快如是则这个排列符合题意在生成全排列时需要使用vis数组去重因为待排列数组有重复的元素。
public class Main {static int[] a {1,1,1,1,1,0,0,0,0,0,0,0};static int ans 0;static boolean[] vis new boolean[12];public static void main(String[] args) {int[] path new int[12];dfs(0, path);System.out.println(ans);}private static void dfs(int pos, int path[]) {if(pos 12) {if(check(path))ans;}for(int i 0; i 12; i) {if(i 0 a[i] a[i-1] !vis[i-1])continue; // 相同元素优先使用前面一个if(!vis[i]) {vis[i] true;path[pos] a[i];dfs(pos1, path);vis[i] false; // 回溯}}}private static boolean check(int[] path) {int[][] x new int[3][4];for(int i 0; i 3; i) {for(int j 0; j 4; j) {if(path[i*4j] 1)x[i][j] 1;else {x[i][j] 0;}}}int cnt 0; // 联通块数目for(int i 0; i 3; i) {for(int j 0; j 4; j) {if(x[i][j] 1) {fun(x, i, j);cnt;}}}return cnt 1; // 只有一个连通快}private static void fun(int[][] x ,int i, int j) {x[i][j] 0; // 防止回退// 尝试周围的路径if(i - 1 0 x[i-1][j] 1)fun(x, i-1,j);if(i 1 3 x[i1][j] 1)fun(x, i1,j);if(j - 1 0 x[i][j-1] 1)fun(x, i,j-1);if(j 1 4 x[i][j1] 1)fun(x, i,j1);}
}
4、生日蜡烛
等差数列的应用 公式 ana1(n-1)d 前n项和公式 Snna1n(n-1)d/2n(a1an)/2
public class Main {public static void main(String[] args) {for(int i 2;; i){ // 从2开始不然从1开始会得到236不合理答案int t i*(i-1)/2;if((236-t)%i0){System.out.println((236-t)/i);break;}}}
}5、四平方和
枚举借助哈希表将4层循环降为2层同时通过判断来缩小枚举范围
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();MapInteger, Integer map new HashMap();for(int c 0; c*c n/2; c) {for(int d c; c*c d*d n; d) {int x c*c d*d;if(!map.containsKey(x))map.put(x, c);}}for(int a 0; a*a n/4; a) {for(int b a; a*a b*b n/2; b) {int x a*a b*b;if(map.containsKey(n-x)) {int c map.get(n-x);int d (int)Math.sqrt(n - x - c*c);System.out.printf(%d %d %d %d, a,b,c,d);return;}}}}
}
6、煤球数目
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);//在此输入您的代码...int sum 1, x 1;for(int i 2; i 100; i){x i;sumx;}System.out.println(sum);scan.close();}
}7、抽签
import java.util.*;
public class Main
{public static void f(int[] a, int k, int n, String s){if(ka.length){ if(n0) System.out.println(s);return;}String s2 s;for(int i0; ia[k]; i){f(a,k1,n-i,s2);s2 (char)(kA);}}public static void main(String[] args){int[] a {4,2,2,1,1,3};f(a,0,5,);}
}
五、2017年真题
1、K倍区间
一维前缀和数学优化。 同余定理 如果ab除以c的余数相同就称ab对于除数c来说是同余的且有a与b的差能被c整除abc均为自然数 例如716除以3的余数相同都为1就称716对于除数3来说是同余的且7与16的差能被3整除。 将所有的前缀和sum[i]全部模上K统计所有相同余数的个数。 根据上面的介绍我们知道假设有m个前缀和满足除以K的余数相同那么任意两个前缀和的差都能被K整除所以K倍区间的个数就是即m*(m-1)/2个
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int k in.nextInt();// 使用long 因为 a[i]*(a[i]-1)可能int溢出这是由测试数据得出的比赛时尽量使用longlong[] a new long[k]; int sum 0;for(int i 1; i n; i) {sum in.nextInt();a[sum%k];sum % k;}long ans a[0];for(int i 0; i k; i) {ans (a[i]*(a[i]-1))/2;}System.out.println(ans);}
}2、包子凑数
3、承压计算
关键点在于怎么处理可以使显示的数字很大同时要处理除2问题如果直接每一个数除2会导致小数问题而且不知道最终值与原本计算值的关系。解决办法是每一个数都乘上一个较大值而且这个值是2的整数倍这样除2就不会有小数了而且大值之间还比较容易看出关系。
package project2017;import java.util.Arrays;
import java.util.Scanner;public class 承压计算 {public static void main(String[] args) {Scanner in new Scanner(System.in);long[][] a new long[30][30];long factor 1;// 左移30位得到2^30for(int i 1; i 30; i)factor 1;//System.out.println(factor);for(int i 0; i 29; i) {for(int j 0; j i; j) {a[i][j] in.nextInt()*factor;}}for(int i 0; i 29; i) {for(int j 0; j i; j) {long half a[i][j] / 2;a[i1][j] half;a[i1][j1] half;}}Arrays.sort(a[29]); // 排序得到最大最小System.out.println(a[29][0]);System.out.println(a[29][29] / (a[29][0]/2086458231));}
}4、分巧克力
使用二分法 考虑数据 3 1 10 10 5 5 2 2 正确答案是10枚举边长范围应该是[1, 所有边长最大值]
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int k in.nextInt();int[] h new int[n];int[] w new int[n];int max 0;for(int i 0; i n; i) {h[i] in.nextInt();w[i] in.nextInt();max Math.max(max, Math.max(h[i], w[i]));}in.close();int ans 1;int l 1;int r max;while(l r) {int mid l ((r-l)1); // 先计算右移用括号包裹或者 (lr)1int cnt 0;for(int i 0; i n; i) {cnt (h[i]/mid)*(w[i]/mid);}if(cnt k) { // 还能增大边长ans mid;l mid1;}else {r mid-1;}}System.out.println(ans);}
}5、取位数
import java.util.*;
public class Main
{
// 求数字x的总位数static int len(int x){if(x10) return 1;return len(x/10)1;}// 取x的第k位数字static int f(int x, int k){if(len(x)-k0) return x%10;return f(x/10, k); //填空}public static void main(String[] args){int x 23513;//System.out.println(len(x));System.out.println(f(x,3));System.out.println(f(893275,2));}
}6、日期问题
使用TreeSet排序和去重
import java.util.TreeSet;
import java.util.Scanner;
import java.util.Set;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);String s in.next(); // 02/03/04char[] arr s.toCharArray();int a,b,c;a (arr[0] - 0)*10(arr[1] - 0);b (arr[3] - 0)*10(arr[4] - 0);c (arr[6] - 0)*10(arr[7] - 0);// 只能是下面三种排列String s1 fun(a,b,c);String s2 fun(c,a,b);String s3 fun(c,b,a);SetString set new TreeSet(); // 去重和排序if(!s1.equals())set.add(s1);if(!s2.equals())set.add(s2);if(!s3.equals())set.add(s3);set.forEach(System.out::println);}private static String fun(int a, int b, int c) {if(a 0 a 59)a 2000;else if(a 60 a 99)a 1900;if(b 1 || b 12)return ;if(c 1 || c 31)return ;boolean leap isLeap(a);switch (b) {case 2:if(leap) {if(c 29)return ;}else {if(c 28)return ;}break;case 4:if(c 30)return ;break;case 6:if(c 30)return ;break;case 9:if(c 30)return ;break;case 11:if(c 30)return ;break;default:break;}// 不足位补0String bb b 10 ? 0b : b;String cc c 10 ? 0c : c;return a-bb-cc;}private static boolean isLeap(int y) {return (y%4 0 y%100 ! 0) || y%400 0;}
}7、纸牌三角形
全排列
public class Main {static int[] a {1,2,3,4,5,6,7,8,9};static int ans 0;public static void main(String[] args) {dfs(0);// 因为考虑对称、旋转所以有6个是重复的System.out.println(ans/6);}private static void dfs(int pos) {if(pos 9) {// 给每一个位置编号int x a[0]a[1]a[3]a[5];int y a[0]a[2]a[4]a[8];int z a[5]a[6]a[7]a[8];if(x y y z) {ans;}}for(int i pos; i 9; i) {int t a[i];a[i] a[pos];a[pos] t;dfs(pos1);t a[i];a[i] a[pos];a[pos] t;}}
}8、最大公共子串 import java.util.Scanner;
public class Main
{static int f(String s1, String s2){char[] c1 s1.toCharArray();char[] c2 s2.toCharArray();int[][] a new int[c1.length1][c2.length1];int max 0;for(int i1; ia.length; i){for(int j1; ja[i].length; j){if(c1[i-1]c2[j-1]) {a[i][j] a[i-1][j-1]1; if(a[i][j] max) max a[i][j];}}}return max;}public static void main(String[] args){int n f(abcdkkk, baabcdadabc);System.out.println(n);System.out.println(f(aaakkkabababa, baabababcdadabc));System.out.println(f(abccbaacbcca, ccccbbbbbaaaa));System.out.println(f(abcd, xyz));System.out.println(f(ab, ab));}
}9、杨辉三角形
import java.util.Scanner;
public class Main
{// 杨辉三角形的第row行第col列static long f(int row, int col){if(row2) return 1;if(col0) return 1;if(colrow) return 1;long[] a new long[row1];a[0]1;a[1]1;int p 2;while(prow){a[p] 1;for(int q p-1; q 1; q--) a[q] a[q] a[q-1]; // 关键p;}return a[col];}public static void main(String[] args){System.out.println(f(6,2));System.out.println(f(6,3));System.out.println(f(40,20));}
}六、2018年真题
1、测试次数
动态规划
public class Main {static int n 1000;public static void main(String[] args) {int[] f1 new int[n1]; // 只有1部手机时的测试次数int[] f2 new int[n1];int[] f3 new int[n1];// 只有1部手机时最坏运气就是在顶层才测出for(int i 1; i n; i) {f1[i] i;}// 有2部手机时最佳策略就是判断在哪一层扔下手机测试次数最少最坏运气就是在该层扔下摔坏和没摔坏的次数最大值for(int i 1; i n; i) { // 共i层int cnt Integer.MAX_VALUE;// 在j层扔下for(int j 1; j i; j) {// 没摔坏则还有2部手机去更高的层测试即还有i-j层要测试// 摔坏 还有1部手机去更低层测试即还有j-1层要测试int x 1 Math.max(f2[i-j], f1[j-1]);// 最佳策略先从哪一层扔下总次数最少cnt Math.min(cnt, x);}f2[i] cnt;}// 有3部手机同理for(int i 1; i n; i) {int cnt Integer.MAX_VALUE;for(int j 1; j i; j) {int x 1 Math.max(f3[i-j], f2[j-1]);cnt Math.min(cnt, x);}f3[i] cnt;}System.out.println(f3[1000]);}
}2、递增三元组
先排序因为n的范围为10^5所以计算乘法时要转成long类型否则会溢出
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int[] a new int[n];int[] b new int[n];int[] c new int[n];for(int i 0; i n; i)a[i] in.nextInt();for(int i 0; i n; i)b[i] in.nextInt();for(int i 0; i n; i)c[i] in.nextInt();Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);long ans 0;int p 0, q 0;// 对b数组中的每一个元素统计a数组中小于该元素的元素个数p统计c数组中大于该元素的元素个数n-q则三元组数目为二者之乘积for(int i 0; i n; i) {while(p n a[p] b[i])p;while(q n c[q] b[i])q;ans 1L*p*(n-q); // 使用long类型}System.out.println(ans);}
}3、方格计数
方格是否在圆内 等价于 方格的右上顶点是否在圆内 需要使用long类型因为 50000*50000 2.5 * 10^9 int 最大值
public class Main {public static void main(String[] args) {long ans 0;long r 50000;for(long i 1; i r; i){ans (long)Math.sqrt(r*r - i*i);}System.out.println(ans*4);}
}4、复数幂
就是BigInteger的使用 不知道怎么提交
package project2018;import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.math.BigInteger;public class 复数幂 {public static void main(String[] args) throws Exception {BigInteger two BigInteger.valueOf(2);BigInteger three BigInteger.valueOf(3);BigInteger a BigInteger.valueOf(2);BigInteger b BigInteger.valueOf(3);BigInteger aa null;BigInteger bb null;for (int i 0; i 123455; i) {aa a.multiply(two).subtract(b.multiply(three));// a*2-(b*3)bb a.multiply(three).add(b.multiply(two));a aa;b bb;}//System.setOut(new PrintStream(new File(C:\\Users\\zzps\\Downloads\\1.txt)));System.out.print(aa);System.out.print((bb.compareTo(BigInteger.ZERO) 0 ? - : ) bb i);}}
5、螺旋折线
找规律曼哈顿距离
曼哈顿距离 abs(x1-x2)abs(y1-y2) 如图在 yx x0 部分顶点的距离为4,16,364kk k为层数
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);long x scan.nextLong();long y scan.nextLong();long k Math.max(Math.abs(x), Math.abs(y));long s 4*k*k; // 基准点的距离// 计算曼哈顿距离long m Math.abs(x-k) Math.abs(y-k);if(x y){// 在基准点左侧距离比其小System.out.println(s - m);}else{System.out.println(s m);}scan.close();}
}6、全球变暖
使用DFS
import java.util.Scanner;public class Main {
// 定义四个方向static int[][] dir {{1,0},{-1,0},{0,-1},{0,1}};static char[][] a new char[1005][1005];// 标记是否访问过static boolean[][] vis new boolean[1005][1005];static boolean flag false;public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();in.nextLine(); // 读取换行符for(int i 0; i n; i) {// 这样读取一整行a[i] in.nextLine().toCharArray();}int ans 0;for(int i 0; i n; i) {for(int j 0; j n; j) {if(a[i][j] # !vis[i][j]) {flag false;dfs(i, j);if(!flag)ans; // 记录不是高地的数量}}}System.out.println(ans);}private static void dfs(int i, int j) {vis[i][j] true;// 周边都是陆地这是一个高地不会被淹没if(a[i1][j] # a[i-1][j] # a[i][j1] # a[i][j-1] #)flag true;for(int k 0; k 4; k) {int dx i dir[k][0];int dy j dir[k][1];if(a[dx][dy] # !vis[dx][dy])dfs(dx, dy);}}
}7、日志统计
七、2019年真题
1、不同子串
使用HashSet去重使用String的substring取出子串
import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;
public class Main {public static void main(String[] args) {String s 0100110001010001;SetString set new HashSet();for(int i 0; i s.length()-1; i){for(int j i1; j s.length()1; j){ // j要多取一位这样可以取到最后一位字符String str s.substring(i,j);set.add(str);}}System.out.println(set.size());}
}2、数列求值
动态规划可以使用4个变量代替dp数组的更迭
import java.util.Scanner;public class Main {public static void main(String[] args) {int f1 1;int f2 1;int f3 1;int f4 0;for(int i 1; i 20190321; i){f4 (f1f2f3)%10000;// 防止溢出 f1 f2;f2 f3;f3 f4;}System.out.println(f4);}
}3、数的分解
package project2019;public class 数的分解 {public static void main(String[] args) {int ans 0;for(int i 1; i 2019; i) {if(check(i))continue;for(int j i1; j 2019; j) {if(check(j))continue;for(int k j1; k 2019; k) {if(check(k))continue;if(i j k 2019) {ans;System.out.println(i j k);}}}}System.out.println(ans);}private static boolean check(int n) {while(n 0) {int t n%10;if(t 2 || t 4)return true;n / 10;}return false;}
}4、迷宫
使用BFS广度优先搜索 注意四个方向需要和DLRU匹配同时pre数组记录的路径是逆向的所以使用递归打印比较好。
package project2019;import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class 迷宫 {static int[][] dir {{1,0},{0,-1},{0,1},{-1,0}}; // 方向增量static char[][] mat new char[32][52]; // 迷宫地图static boolean[][] vis new boolean[32][52]; // 标记是否访问过static char[] arr {D, L, R, U};static char[][] pre new char[32][52]; // 记录路径public static void main(String[] args) {Scanner in new Scanner(System.in);for(int i 0; i 30; i) {mat[i] in.nextLine().toCharArray();}bfs();}private static void bfs() {Node s new Node (0,0);QueueNode q new LinkedList(); // 链表实现队列增删快q.offer(s); // 起点入队vis[0][0] true; // 标记起点已经被访问过while(!q.isEmpty()) {// 取出队头元素poll方法同时会删除该元素Node e q.poll();if(e.x 29 e.y 49) {// 到达终点print(29, 49);return;}for(int i 0; i 4; i) {int x e.x dir[i][0];int y e.y dir[i][1];if(x 0 x 30 y 0 y 50 !vis[x][y] mat[x][y] 0) {Node n new Node(x, y);q.offer(n);vis[x][y] true;pre[x][y] arr[i];}}}}private static void print(int x ,int y) {if(x 0 y 0)return;if(pre[x][y] D)print(x-1, y);if(pre[x][y] L)print(x, y1);if(pre[x][y] R)print(x, y-1);if(pre[x][y] U)print(x1, y);System.out.print(pre[x][y]);}static class Node{int x;int y;public Node(int x, int y) {this.x x;this.y y;}}
}5、特别数的和
暴力即可
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();long sum 0;for(int i 1; i n; i) {if(check(i))sum i;}System.out.println(sum);}private static boolean check(int n) {while(n 0) {int t n % 10;if(t 2 || t 0 || t 1 || t 9)return true;n / 10;}return false;}
}6、外卖店优先级
按[id,ts]进行统计
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int sum 0;int n, m, t, x, y;n sc.nextInt();m sc.nextInt();t sc.nextInt();int arr[][] new int[n 1][t 1];int num[] new int[n 1];boolean f[] new boolean[n 1];while (m 0) {x sc.nextInt();y sc.nextInt();arr[y][x];m--;}for (int i 1; i n; i) {for (int j 1; j t; j) {if (arr[i][j] ! 0) {num[i] 2*arr[i][j];} else{if (num[i] 0) num[i]--;}if (num[i] 5) {f[i] true;}if (num[i] 3) {f[i] false;}}}for (int i 1; i n; i) {if (f[i] true) {sum;}}System.out.println(sum);sc.close();}
}第八题人物相关性分析 第九题后缀表达式
九、2021年真题
1、杨辉三角形
下面代码能通过40%的数据 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);long n in.nextInt();boolean f true;for(int i 0; f true; i) {for(int j 0; j i; j) {long x fun(i, j);if(x n) {System.out.println(i*(i1)/2j1);f false;break;}}}}private static long fun(int row, int col) {if(row 2)return 1;if(col 0 || col row)return 1;long[] a new long[row1];a[0] 1;a[1] 1;int p 2;while(p row) {a[p] 1;for(int q p-1; q 1; q--)a[q] a[q] a[q-1];p;}return a[col];}
}
