本文共 13631 字，大约阅读时间需要 45 分钟。
package Contest_2013;import java.util.Calendar;/** * * 曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。 * * 还有人称今后的某个世纪末的12月31日，如果是星期一则会.... * * 有趣的是，任何一个世纪末的年份的12月31日都不可能是星期一!! * * 于是，“谣言制造商”又修改为星期日...... * * 1999年的12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年（即xx99年）的12月31日正好是星期天（即星期日）？ * * 请回答该年份（只写这个4位整数，不要写12月31等多余信息） * * @author Admin * */public class 世纪末的星期 { public static void main(String[] args) { // 需要一个日历，累加至世纪末年，检查是否为星期日。 Calendar calendar = Calendar.getInstance(); // 设置为1999-12-31，月份从0开始 calendar.set(1999, 11, 31); // 累加100年并进行判断 while (calendar.get(Calendar.DAY_OF_WEEK) != Calendar.SUNDAY) { calendar.add(Calendar.YEAR, 100); } // 输出符合符合条件的日期 System.out.println(calendar.getTime()); // 答案为：2299 } /** * 获取下个月的倒数第3天 */ private static void function() { Calendar calendar = Calendar.getInstance(); // 将时间设置为下下个月的第一天 calendar.add(Calendar.MONTH, 2); calendar.set(Calendar.DAY_OF_MONTH, 1); // 然后将时间倒退三天 calendar.add(Calendar.DATE, -3); System.out.println(calendar.getTime()); }} package Contest_2013;/** * * 标题: 马虎的算式 * * * 小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。 * * 有一次，老师出的题目是：36 x 495 = ? * * 他却给抄成了：396 x 45 = ? * * 但结果却很戏剧性，他的答案竟然是对的！！ * * 因为 36 * 495 = 396 * 45 = 17820 * * 类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54 * * 假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0） * * 能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？ * * 请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。 * * 满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。 * * 答案直接通过浏览器提交。 注意：只提交一个表示最终统计种类数的数字，不要提交解答过程或其它多余的内容。 * * @author Admin * */public class 马虎的算式 { static int count = 0; static int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; static int[] comb = new int[5]; static int[] visit = new int[10]; public static void main(String[] args) { // 搜索：ab * cde = adb * ce dfs(0); System.out.println(count); } // 组合abcde，然后检查是否符合条件 private static void dfs(int depth) { if (depth == 5) { if (isOk()) { count++; } return; } // 从data中抓取元素，到comb for (int i = 0; i < data.length; i++) { int val = data[i]; if (visit[val] == 0) { // 检查val是否被抓取过 comb[depth] = val; visit[val] = 1; dfs(depth + 1); visit[val] = 0;// go back } } } // ab * cde = adb * ce private static boolean isOk() { // TODO Auto-generated method stub int a = comb[0]; int b = comb[1]; int c = comb[2]; int d = comb[3]; int e = comb[4]; int ab = a * 10 + b; int cde = c * 100 + d * 10 + e; int adb = a * 100 + d * 10 + b; int ce = c * 10 + e; int num1 = ab * cde; int num2 = adb * ce; if (num1 == num2) { // System.out.println(ab + " " + cde + " " + adb + " " + ce); return true; } return false; }} package Contest_2013;public class 振兴中华 { static int count = 0; static String maze[][] = { { "从", "我", "做", "起", "振" }, { "我", "做", "起", "振", "兴" }, { "做", "起", "振", "兴", "中" }, { "起", "振", "兴", "中", "华" } }; static String comb[] = new String[7]; static int visit[][] = new int[4][5]; // 方向数组，四个方向 static int dx[] = { -1, 1, 0, 0 }; static int dy[] = { 0, 0, -1, 1 }; public static void main(String[] args) { // TODO Auto-generated method stub dfs(0, 0, 0);// 注意一开始已经站在 从 字的上面了 System.out.println(count); } private static void dfs(int depth, int x, int y) { if (depth == 7) { if (isOk()) { count++; } return; } // 向四个方向走 for (int i = 0; i < dx.length; i++) { int newX = x + dx[i]; int newY = y + dy[i]; if (check(newX, newY)) { // 检查newX，newY是否可以走 visit[newX][newY] = 1; comb[depth] = maze[newX][newY]; dfs(depth + 1, newX, newY); visit[newX][newY] = 0;// go back } } } // 检查新的坐标是否可以走 private static boolean check(int newX, int newY) { // 检查是否越界 if (newX < 0 || newX >= maze.length || newY < 0 || newY >= maze[newX].length) return false; // 检查是否重复访问 if (visit[newX][newY] == 1) return false; return true; } // 检查该路线是否符合条件 private static boolean isOk() { StringBuilder str = new StringBuilder(); for (int i = 0; i < comb.length; i++) { str.append(comb[i]); } // System.out.println(str.toString()); if (str.toString().equals("我做起振兴中华")) return true; return false; }} package Contest_2013;public class 振兴中华优化 { static int count = 0; static int maze[][] = new int[4][5]; static int dx[] = { 1, 0 }; static int dy[] = { 0, 1 }; public static void main(String[] args) { // TODO Auto-generated method stub // 统计从0，0开始向右或者向下走7步，有多少种走法 dfs(0, 0, 0); System.out.println(count); } private static void dfs(int depth, int x, int y) { if (depth == 7) { count++; return; } // 向右或者向下走 for (int i = 0; i < dx.length; i++) { int newX = x + dx[i]; int newY = y + dy[i]; // 检查越界 if (newX < 0 || newX >= maze.length || newY < 0 || newY >= maze[x].length) continue; System.out.println(newX + " " + newY); dfs(depth + 1, newX, newY); } }} package 真题2013;public class 振兴中华 { static int count = 0; public static void main(String[] args) { count = f(4, 3); System.out.println(count); } // 返回到达(x, y)的路线数 private static int f(int x, int y) { if (x == 0 || y == 0) { return 1; } return f(x - 1, y) + f(x, y - 1); }} package Contest_2013;import java.math.BigDecimal;import java.math.RoundingMode;//0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375public class 黄金连分数 { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(function(300));// 手动判断出大概在300次连分后，小数点后100位不再变化 } // depth 为指定的连分次数 private static BigDecimal function(int depth) { if (depth == 0) { return new BigDecimal(0.61803); } return new BigDecimal(1.0).divide(new BigDecimal(1.0).add(function(depth - 1)), 100, RoundingMode.HALF_UP); }} 使用链表的话应该是比较好操作的了
package Contest_2013;import java.util.ArrayList;import java.util.Scanner;public class 幸运数 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int m = sc.nextInt(); int n = sc.nextInt(); int count = 0; // 处理第一个幸运数字1 // 在区间(1,n)中去除能够被2整除的数字 // 等价于保留奇数 ArrayList list = new ArrayList<>(); for (int i = 2; 2 * i - 1 < n; i++) { list.add(2 * i - 1); } // 在链表中依次选择数字，进行相应的逻辑操作(注意链表首为序号2的位置) // 逻辑操作：把所有能被当前所选择数字整除的序号位置去掉 for (int i = 0; i < list.size(); i++) { int num = list.get(i); ArrayList tempList = new ArrayList<>(); for (int j = 0; j < list.size(); j++) { int index = j + 2; if (index % num != 0) tempList.add(list.get(j)); } list = tempList; } // 统计count for (Integer integer : list) { if (integer > m) count++; } System.out.println(count); } }} 学了网上奇奇怪怪的做法
package Contest_2013;import java.util.Scanner;public class 幸运数不使用链表 { static int n; static int m; static int[] arr; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { m = sc.nextInt(); n = sc.nextInt(); arr = new int[n + 1]; // 预处理：去除偶数，等价于得到奇数 for (int i = 1; 2 * i - 1 < n; i++) { arr[i] = 2 * i - 1; } // 预处理结束 function(2); // 统计 int ans = count(); System.out.println(ans); } } private static int count() { int count = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == 0) break; if (arr[i] > m) count++; } return count; } // 选择数组的arr[index]，向后去除能够被其整除的位置 private static void function(int index) { while (true) { if (arr[index] == 0) break; int replace = index + 1; for (int i = index + 1; i <= n; i++) { if (i % arr[index] != 0) { // 需要保留的数字arr[i] arr[replace] = arr[i]; replace++; } } index++; } }} 思路：DFS全排列，然后暴力判断，要剪枝。
package Contest_2013;import java.util.Scanner;/** * 100 可以表示为带分数的形式：100 = 3 + 69258 / 714 * * 还可以表示为：100 = 82 + 3546 / 197 * * 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。 * * 类似这样的带分数，100 有 11 种表示法。 * * 题目要求： 从标准输入读入一个正整数N (N<1000*1000) 程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。 * 注意：不要求输出每个表示，只统计有多少表示法！ * */public class 带分数 { static int n; static int count; static int visit[]; static int comb[]; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { n = sc.nextInt(); count = 0; comb = new int[9]; visit = new int[10]; // long begin = System.currentTimeMillis(); // dfs全排列，然后暴力判断 dfs(0); System.out.println(count); // long end = System.currentTimeMillis(); // System.out.println(end - begin); } } // 暴力全排列 private static void dfs(int depth) { if (depth == 9) { check(); return; } // 从1·9中，抓取放入 for (int i = 1; i <= 9; i++) { if (visit[i] == 0) { comb[depth] = i; visit[i] = 1; dfs(depth + 1); visit[i] = 0;// go back } } } // 暴力检测，多次剪枝 // 感觉剪头两个，应该就够了 private static void check() { // n = a+b/c int a; int b; int c; // [0,i]-->a for (int i = 0; i <= 6; i++) { a = 0; for (int j = 0; j <= i; j++) { a = 10 * a + comb[j]; } if (a >= n)// 剪枝：不可能再使得灯饰n = a + b/c成立 break; // [i+1,j]-->b for (int j = i + 1; j < comb.length - 1; j++) { if (j - (i + 1) + 1 < comb.length - 1 - (j + 1) + 1)// 剪枝：分子长度小于分母长度 continue; b = 0; for (int k = i + 1; k <= j; k++) { b = 10 * b + comb[k]; } if (b <= n - a)// 剪枝 continue; // [j+1,len-1]-->c c = 0; for (int k = j + 1; k < comb.length; k++) { c = 10 * c + comb[k]; } if (n == a + b * 1.0 / c) { // System.out.println("a:" + a + " b:" + b + " c:" + c); count++; break;// 剪枝 } else if (a + b * 1.0 / c > n)// 剪枝 break; } } }} 思路：简单暴力一下即可
package Contest_2013;/** * 小明这些天一直在思考这样一个奇怪而有趣的问题： 在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是： 如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。 当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。输入格式：第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。输出格式：输出一个整数，表示不同连号区间的数目。暴力得分40 */import java.util.Scanner;public class 连号区间 { static int[] data; static int count; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); data = new int[n + 1]; for (int i = 1; i < data.length; i++) { data[i] = sc.nextInt(); } for (int left = 1; left < data.length; left++) { for (int right = left; right < data.length; right++) { int[] visit = new int[50000 + 5]; int max = data[left]; int min = data[left]; for (int i = left; i <= right; i++) { visit[data[i]] = 1; if (data[i] > max) max = data[i]; if (data[i] < min) min = data[i]; } boolean flag = true; for (int i = min; i <= max; i++) { if (visit[i] == 0) { flag = false; break; } } if (flag) count++; } } System.out.println(count); } }} 在40分做法基础上改了几行而已
package Contest_2013;import java.util.HashMap;/** * 小明这些天一直在思考这样一个奇怪而有趣的问题： 在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是： 如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。 当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。输入格式：第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。输出格式：输出一个整数，表示不同连号区间的数目。暴力得分80 */import java.util.Scanner;public class 连号区间_改进暴力 { static int[] data; static int count; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); data = new int[n + 1]; for (int i = 1; i < data.length; i++) { data[i] = sc.nextInt(); } for (int left = 1; left < data.length; left++) { HashMap visit = new HashMap ();// 减少内存占用 int max = data[left]; int min = data[left]; for (int right = left; right < data.length; right++) { // for (int i = left; i <= right; i++) { // visit[data[right]] = 1; visit.put(data[right], 1); if (data[right] > max) max = data[right]; if (data[right] < min) min = data[right]; // } boolean flag = true; for (int i = min; i <= max; i++) { // 检查区间是否完整 if (visit.get(i) == null) { flag = false; break; } } if (flag) count++; } } System.out.println(count); } }} 通过连号区间的性质，来判断当前的区间是否为连号区间。
有点难想到。package Contest_2013;import java.util.HashMap;/** * 小明这些天一直在思考这样一个奇怪而有趣的问题： 在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是： 如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。 当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。输入格式：第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。输出格式：输出一个整数，表示不同连号区间的数目。 */import java.util.Scanner;public class 连号区间_AC { static int[] data; static int count; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); data = new int[n + 1]; for (int i = 1; i < data.length; i++) { data[i] = sc.nextInt(); } for (int left = 1; left < data.length; left++) { int max = data[left]; int min = data[left]; for (int right = left; right < data.length; right++) { if (data[right] > max) max = data[right]; if (data[right] < min) min = data[right]; if (max - min == right - left)// 检查连号区间的性质是否成立 count++; } } System.out.println(count); } }} 转载地址：http://jbamf.baihongyu.com/