A、奇数倍数
本题总分：5 分
问题描述
请你找到最小的整数 X 同时满足：
X 是 2019 的整倍数
X 的每一位数字都是奇数
package action; public class demo { public static void main(String[] args) { a: for (int i = 2019, n = 2019; true; n = i += 2019) { do { if ((n & 1) == 0) continue a; } while ((n /= 10) > 0); System.out.println(i); break; } } }
B、递增序列
本题总分：5 分
问题描述
对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。
例如，如下矩阵中
LANN
QIAO
有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 个递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看是不同的顺序。
对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
package action; import java.io.BufferedReader; public class demo { static String str = "VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG" + "SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF" + "ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA" + "BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL" + "YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH" + "ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU" + "XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR" + "ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG" + "MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA" + "VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF" + "GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC" + "EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK" + "PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW" + "CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP" + "RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS" + "PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR" + "JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL" + "YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP" + "HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN" + "DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF" + "LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW" + "CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ" + "IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI" + "ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB" + "HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP" + "FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS" + "VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ" + "BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR" + "RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY" + "ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX"; static char[][] c = new char[30][50]; static int count = 0; public static void main(String[] args) { for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[i].length; j++) { c[i][j] = str.charAt(i * c[i].length + j); } } for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[i].length; j++) { check(i, j); } } System.out.println(count); } public static void check(int i, int j) { // 右 for (int k = 1; k < c[i].length - j; k++) { if (j + k < c[i].length && c[i][j] < c[i][j + k]) { count++; } } // 下 for (int k = 1; k < c.length - i; k++) { if (i + k < c.length && c[i][j] < c[i + k][j]) { count++; } } // 右下角 for (int k = 1; k < c.length - i; k++) { if (i + k < c.length && j + k < c[i].length && c[i][j] < c[i + k][j + k]) { count++; } } // 右上角 for (int k = 1; k < c.length; k++) { if (i - k >= 0 && j + k < c[i].length && c[i][j] < c[i - k][j + k]) { count++; } } // 左下角 for (int k = 1; k < c.length; k++) { if (i + k < c.length && j - k >= 0 && c[i][j] < c[i + k][j - k]) { count++; } } } }
这种题没啥犹豫的，暴力吧。
C、平方拆分
本题总分：10 分
问题描述
将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 13^2 + 25^2 + 35^2 = 2019 与 13^2 + 35^2 +25^2 = 2019 视为同一种方法(^代表平方)。
package action; public class demo { static int count = 0; public static void main(String[] args) { dfs(2019, -1); System.out.println(count); } public static void dfs(int num, int start) { if (num < 0) { return; } if (num == 0) { count++; } else { for (int i = start + 1, high = (int) Math.sqrt(num); i <= high; i++) dfs(num - i * i, i); } } }package action; public class demo { static int count = 0; public static void main(String[] args) { dfs(2019, -1); System.out.println(count); } public static void dfs(int num, int start) { if (num < 0) { return; } if (num == 0) { count++; } else { for (int i = start + 1, high = (int) Math.sqrt(num); i <= high; i++) dfs(num - i * i, i); } } }
D、切割(挺过分的题)
本题总分：10 分
问题描述
在 4 × 4 的方格矩阵中画一条直线。则直线穿过的方格集合有多少种不同的可能？这个里直线穿过一个方格当且仅当直线将该方格分割成面积都大于 0 的两部分。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action; import java.util.HashSet; import java.util.Set; public class demo { final static int range = 100; static Set<Integer> st = new HashSet<Integer>(); public static void main(String[] args) { // 枚举直线标准方程 ax + by + c = 0的三个参数 for (int a = -range; a <= range; a++) { for (int b = -range; b <= range; b++) { for (int c = -range; c <= range; c++) { int status = 0; // 遍历16个格子 for (int x = 1; x <= 4; x++) { for (int y = 1; y <= 4; y++) { int pos = 0, neg = 0;// 记录正负个数 if (a * x + b * y + c > 0) pos++; if (a * x + b * y + c < 0) neg++; if (a * (x - 1) + b * (y - 1) + c > 0) pos++; if (a * (x - 1) + b * (y - 1) + c < 0) neg++; if (a * x + b * (y - 1) + c > 0) pos++; if (a * x + b * (y - 1) + c < 0) neg++; if (a * (x - 1) + b * y + c > 0) pos++; if (a * (x - 1) + b * y + c < 0) neg++; // 将上色的点集压缩成二进制的整数 status <<= 1; if (pos * neg > 0) status += 1;// 有正有负说明当前格子被直线穿过 } } st.add(status);// 记录当前点集 } } } System.out.println(st.size()); } }
E、序列求和
本题总分：15 分
问题描述
学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 St 。
例如 S1 = 1, S2 = 2, S3 = 4, S4 = 6，· · · 。
现在小明想知道，前 60 个 Si 的和是多少？即 S1 + S2 + · · · + S60 是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action; import java.util.Collections; import java.util.List; import java.util.Vector; import static java.lang.Math.min; import static java.lang.Math.pow; public class demo { static List<Integer> prim = new Vector<>(); public static void main(String[] args) { initPrime(); long sum = 0; for (int i = 1; i <= 60; i++) { sum += dfs(resolve(i)); } System.out.println(sum); } private static long dfs(List<Integer> vv) { long ans = cal(vv); if (vv.size() == 1) return cal(vv); for (int i = 0; i < vv.size() - 1; i++) { for (int j = i + 1; j < vv.size(); j++) { List<Integer> vvv = new Vector<>(vv.size() - 1); for (int k = 0; k < vv.size(); k++) { if (k != i && k != j) vvv.add(vv.get(k)); } Integer value_i = vv.get(i); Integer value_j = vv.get(j); vvv.add(value_i * value_j); ans = min(ans, dfs(vvv)); } } return ans; } private static long cal(List<Integer> vv) { Collections.sort(vv); long ans = 1; int j = 0; for (int i = vv.size() - 1; i >= 0; i--) { ans *= pow(prim.get(j++), vv.get(i) - 1); } return ans; } private static List<Integer> resolve(int now) { List<Integer> vv = new Vector<>(); // 因子分解，存储在vv中 for (int j = 2; j * j <= now; j++) { while (now % j == 0) { vv.add(j); now /= j; } } if (now > 1) vv.add(now); if (vv.size() == 1) vv.add(1); return vv; } private static void initPrime() { for (int i = 2; i <= 1e5; i++) { boolean ok = true; for (int j = 2; j * j <= i; j++) { if (i % j == 0) { ok = false; break; } } if (ok) prim.add(i); } } }
看到有人说结果是：【101449】，但是我能确定【292809912969717649】绝对是给分了的。
