第八届蓝桥杯省赛JavaC组真题——详细答案对照(完整版)
目录
A、外星日历
某星系深处发现了文明遗迹。
他们的计数也是用十进制。
他们的文明也有日历。日历只有天数，没有年、月的概念。
有趣的是，他们也使用了类似“星期”的概念，
只不过他们的一个星期包含了9天，
为了方便，这里分别记为: A,B,C....H,I从一些资料上看到，
他们的23日是星期E
他们的190日是星期A
他们的343251日是星期I令人兴奋的是，他们居然也预见了“世界末日”的那天，
当然是一个很大很大的数字
651764141421415346185请你计算一下，这遥远的一天是该文明的星期几？
你需要提交的是一个大写字母，表示该文明的星期几，
不要填写任何多余的内容。
题解：
package action;
import java.math.BigInteger;
public class demo {
public static void main(String[] args) {
BigInteger x = new BigInteger("651764141421415346185");
BigInteger y = x.mod(new BigInteger("9"));
int z = y.intValue();
System.out.println((char)('A'+z-1));
}
}
B、兴趣小组
为丰富同学们的业余文化生活，某高校学生会创办了3个兴趣小组
（以下称A组，B组，C组）。
每个小组的学生名单分别在【A.txt】,【B.txt】和【C.txt】中。
每个文件中存储的是学生的学号。由于工作需要，我们现在想知道：
既参加了A组，又参加了B组，但是没有参加C组的同学一共有多少人？请你统计该数字并通过浏览器提交答案。
注意：答案是一个整数，不要提交任何多余的内容。
题解：
package action;
public class demo {
public static void main(String[] args) {
int[] a = { 12894792, 92774113, 59529208, 22962224, 2991600, 83340521, 87365045, 40818286, 16400628, 39475245,
55933381, 76940287, 61366748, 95631228, 17102313, 50682833, 61562613, 87002524, 83062019, 51743442,
61977890, 32010762, 69680621, 87179571, 81761697, 32364296, 7833271, 36198035, 26588918, 84046668,
43059468, 73191775, 56794101, 454780, 11141030, 10008994, 35072237, 44945158, 53959980, 75758119,
18560273, 35801494, 42102550, 22496415, 3981786, 34593672, 13074905, 07733442, 42374678, 23452507,
98586743, 30771281, 17703080, 52123562, 5898131, 56698981, 90758589, 18238802, 18217979, 4511837,
75682969, 31135682, 55379006, 42224598, 98263070, 40228312, 28924663, 11580163, 25686441, 45944028,
96731602, 53675990, 3854194, 14858183, 16866794, 40677007, 73141512, 32317341, 56641725, 43123040,
15201174, 62389950, 72887083, 76860787, 61046319, 6923746, 17874548, 46028629, 10577743, 48747364,
5328780, 59855415, 60965266, 20592606, 14471207, 70896866, 46938647, 33575820, 53426294, 56093931,
51326542, 94050481, 80114017, 33010503, 72971538, 22407422, 17305672, 78974338, 93209260, 83461794,
41247821, 26118061, 10657376, 42198057, 15338224, 50284714, 32232841, 26716521, 76048344, 23676625,
62897700, 69296551, 59653393, 38704390, 48481614, 69782897, 26850668, 37471053, 88720989, 51010849,
94951571, 60024611, 29808329, 70377786, 13899299, 9683688, 58218284, 46792829, 97221709, 45286643,
48158629, 57367208, 26903401, 76900414, 87927040, 9926730, 1508757, 15101101, 62491840, 43802529 };
int[] b = { 44894050, 34662733, 44141729, 92774113, 99208727, 91919833, 23727681, 10003409, 55933381, 54443275,
13584702, 96523685, 50682833, 61562613, 62380975, 20311684, 93200452, 23101945, 42192880, 28992561,
18460278, 19186537, 58465301, 01111066, 62680429, 23721241, 20277631, 91708977, 57514737, 3981786,
81541612, 07346443, 93154608, 19709455, 37446968, 17703080, 72378958, 66200696, 30610382, 89586343,
33152171, 67040930, 35696683, 63242065, 99948221, 96233367, 52593493, 98263070, 1418023, 74816705,
89375940, 58405334, 96731602, 84089545, 16866794, 94737626, 01673442, 70548494, 13638168, 8163691,
11106566, 64375392, 40267902, 897705, 56447313, 54532235, 94738425, 66642634, 83219544, 40546096,
66924991, 20592606, 96037590, 73434467, 70896866, 91025618, 57892091, 8487641, 32500082, 84412833,
23311447, 38380409, 79957822, 72971538, 69645784, 91863314, 73099909, 93209260, 83461794, 81378487,
30423273, 22233715, 32232841, 26716521, 03511221, 29196547, 58263562, 56233305, 52547525, 55812835,
87253244, 52484232, 80837360, 94098464, 52028151, 53267501, 66381929, 84381316, 59788467, 9683688,
67082008, 71605255, 80654064, 21434307, 45286643, 76556656, 82465821, 57367208, 79218980, 48460468,
59170479, 46046391, 43043164, 96544490, 83340521, 70837892, 18926791, 40818286, 28936302, 11489524,
51031183, 73860337, 13241219, 9025448, 10718828, 76360986, 26031606, 76558053, 97726139, 46473415,
48406387, 23625539, 86756012, 35164187, 49161302, 78082834, 35072237, 8602486, 29815841, 56562216,
77684187, 81751704, 20160464, 50407962, 27786415, 19893526, 934129, 37759498, 52636463, 25666982,
43262852, 38393436, 2581136, 29323250, 56950657, 5898131, 95286262, 75574581, 54057961, 6703896,
90758589, 57782642, 34492535, 41919697, 6395464, 10993500, 81212949, 34017532, 69569396, 99009936,
57129610, 67401593, 71044018, 62076698, 29533873, 71936325, 86874388, 26545032, 35695544, 30433724,
53127345, 72887083, 25390873, 63711546, 6923746, 27783723, 33199575, 35929698, 16491251, 18276792,
62744775, 92096155, 06336570, 56141974, 73007273, 31416832, 00171057, 64176982, 46938647, 58460388,
69972026, 73724304, 27435484, 51568616, 15531822, 47788699, 11818851, 41594694, 83561325, 43107163,
56965375, 10557343, 26118061, 74650126, 90076467, 10657376, 49901436, 03425162, 61164599, 15797769,
5427896, 14444084, 36795868, 18079449, 59653393, 72942548, 06763077, 33895610, 94892653, 12085268,
65174140, 79567366, 23020126, 74290047, 13498869, 21696323, 27724594, 54941003, 38229841, 7050068 };
int[] c = { 13404901, 39952424, 47847739, 94939581, 13809950, 70966043, 11161555, 17102313, 47079425, 50682833,
74154313, 61562613, 93200452, 37103342, 18479435, 32502597, 36198035, 54210010, 73191775, 48358178,
85544503, 5996766, 54651623, 52113220, 27465181, 23871783, 22496415, 54107041, 65899605, 56528700,
82671109, 61176034, 42374678, 51612628, 63329997, 56591652, 04552733, 12789324, 89586343, 51935014,
38611966, 43916409, 70996050, 98263070, 1418023, 65345049, 21734275, 76846198, 71506230, 833171,
67128139, 41367555, 64769510, 44010700, 16475199, 93164325, 9386162, 95324041, 80688223, 67629139,
79552617, 76219736, 50368644, 45096021, 54972488, 63779011, 28862942, 73145521, 74078605, 66924991,
12806850, 02171001, 70896866, 73434467, 8487641, 44415025, 32500082, 84412833, 83896188, 52243759,
49191410, 38744339, 48079796, 44937032, 06267501, 81866886, 38575984, 25978688, 78974338, 41247821,
12356966, 64842303, 79127158, 2366944, 68000570, 12426275, 96409230, 705972, 8266503, 83820884, 8831807,
43273308, 23216105, 29196547, 95160161, 05553537, 52182214, 32641346, 91553427, 24436506, 77433749,
1979664, 52028151, 88985343, 1761499, 76203088, 63237368, 23405334, 59788467, 9683688, 67755443,
29946533, 12053603, 437479, 15200030, 45286643, 93537527, 82465821, 57367208, 53899751, 15354933,
97760830, 68933762, 80220545, 1892750, 39868288, 21524323, 69716610, 65083815, 78048499, 3227391,
83340521, 87365045, 71720254, 51031183, 89168555, 8503028, 37086236, 25103057, 87002524, 22808816,
80928090, 90741678, 15993372, 99117082, 49938176, 21755083, 86903426, 87830263, 53959980, 75758119,
59781354, 58679691, 25666982, 56307643, 47180521, 62776522, 78136608, 44882734, 90758589, 8075999,
66303819, 23480347, 11580163, 87080118, 18329165, 92514163, 89404632, 92377859, 3912329, 17499963,
59699979, 79876366, 63894807, 37857001, 86003935, 90087123, 29433345, 80298948, 61531153, 61046319,
37839841, 19421134, 48747364, 35196916, 62484573, 59907079, 36845702, 21631642, 72739317, 26283700,
80114017, 76639390, 29154110, 35159758, 47788699, 11818851, 56520669, 36396767, 36031167, 83817428,
10657376, 90076467, 14676452, 11024560, 16327605, 76048344, 14444084, 95452011, 99612346, 65172562,
84813675, 88618282, 38704390, 27998014, 63859011, 33787505, 60024611, 16229880, 13899299, 35240335,
29173227, 45036451, 66177893, 82658333, 43100730, 44520187, 74290047, 85013538, 9926730, 27724594,
95148523, 20503000, 64390907, 26006953, 98116293, 97457666, 29017396, 04634371, 70791589 };
// 参加a，参加b ，没有参加c
// 即 数组ab有c没有的数字
int [] temp = new int [a.length];
int num = 0;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
if (a[i] == b[j]) {
temp[num] = a[i];
System.out.println(temp[num]);
num++;
}
}
}
for (int i = 0; i < temp.length; i++) {
for (int j = 0; j < c.length; j++) {
if (temp[i] == c[j]) {
num--;
}
}
}
System.out.println(num);
}
}
C、纸牌三角形
A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。
下图就是一种排法：A
9 6
4 83 7 5 2
这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？
请你计算并提交该数字。
注意：需要提交的是一个整数，不要提交任何多余内容。
题解：
package action;
public class demo {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
dfs(arr, 0, arr.length);
System.out.println(count / 6);
}
static int count = 0;
public static void dfs(int[] arr, int k, int end) {
// 结束条件
if (k == end) {
int x = arr[0] + arr[1] + arr[2] + arr[3];
int y = arr[3] + arr[4] + arr[5] + arr[6];
int z = arr[6] + arr[7] + arr[8] + arr[0];
if (x == y && x == z) {
count++;
}
return;
}
for (int i = k; i < end; i++) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
dfs(arr, k + 1, end);
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
D、承压计算
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同。
金属材料被严格地堆放成金字塔形。7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X其中的数字代表金属块的重量（计量单位较大）。
最下一层的X代表30台极高精度的电子秤。假设每块原料的重量都十分精确地平均落在下方的两个金属块上，
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小，所以显示的数字很大。工作人员发现，其中读数最小的电子秤的示数为：2086458231
请你推算出：读数最大的电子秤的示数为多少？
注意：需要提交的是一个整数，不要填写任何多余的内容。
题解：
package action;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double [][] num = new double[30][30];
for (int i = 0; i < num.length - 1; i++) {
for (int j = 0; j <= i; j++) {
num[i][j] = sc.nextDouble();
}
}
for (int i = 1; i < num.length; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) { // 每一行第一个
num[i][j] += num[i-1][j]/2;
} else if (j == i) { // 这一行最后一个
num[i][j] += num[i-1][j-1]/2;
} else {
num[i][j] += num[i-1][j-1]/2 + num[i-1][j]/2;
}
}
}
for (int i = 0; i < 30; i++) {
for (int j = 0; j <= i; j++) {
System.out.print(num[i][j]+" ");
}
System.out.println();
}
// 找第30行的最大值和最小值
double min = 100000;
double max = 0;
for (int i = 0; i < num[29].length; i++) {
if (num[29][i] > max) {
max = num[29][i];
}
if (num[29][i] < min) {
min = num[29][i];
}
}
long ans = (long) (2086458231/min * max);
System.out.println(ans);
}
}
E、杨辉三角(填空)
杨辉三角也叫帕斯卡三角，在很多数量关系中可以看到，十分重要。
第0行： 1
第1行： 1 1
第2行： 1 2 1
第3行： 1 3 3 1
第4行： 1 4 6 4 1
....两边的元素都是1， 中间的元素是左上角的元素与右上角的元素和。
我们约定，行号，列号都从0计数。
所以： 第6行的第2个元素是15，第3个元素是20直观地看，需要开辟一个二维数组，其实一维数组也可以胜任。
如下程序就是用一维数组“腾挪”的解法。public class A
{
// 杨辉三角形的第row行第col列
static long f(int row, int col){
if(row<2) return 1;
if(col==0) return 1;
if(col==row) return 1;
long[] a = new long[row+1];
a[0]=1;
a[1]=1;
int p = 2;
while(p<=row){
a[p] = 1;
for( __________________ ) 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));
}
}
请仔细分析源码，并完成划线部分缺少的代码。
注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。
题解：
package action;
public class demo {
// 杨辉三角形的第row行第col列
static long f(int row, int col){
if(row<2) return 1; // 前两行都为1
if(col==0) return 1; // 每一行第一个为1
if(col==row) return 1; // 每一行最后一个为1
long[] a = new long[row+1]; // 存储每一行数据的数组
a[0]=1; // 这个可以看成第一行的第一个值和第二个值 ， 等的下一行的时候，这个就跟着变了
a[1]=1;
int p = 2; // 行数
while(p<=row){
a[p] = 1; // 这一行最后一个数为1
for(int q = p - 1;q > 0 ;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));
}
}
F、最大公共子串
最大公共子串就是求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路，并补全划线部分缺失的代码。
public class A
{
static int f(String s1, String s2)
{
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length+1][c2.length+1];
int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) {
a[i][j] = _______________________ ; //填空
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);
}
}注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。
题解：
package action;
public class demo {
static int f(String s1, String s2)
{
// 将两个字符串切割成字符数组
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length+1][c2.length+1];
int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) { // 当这个值相等时，那么我要加上它前一个上的数并且+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);
}
}
G、Excle地址
Excel单元格的地址表示很有趣，它使用字母来表示列号。
比如，
A表示第1列，
B表示第2列，
Z表示第26列，
AA表示第27列，
AB表示第28列，
BA表示第53列，
....当然Excel的最大列号是有限度的，所以转换起来不难。
如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？本题目既是要求对输入的数字, 输出其对应的Excel地址表示方式。
例如，
输入：
26
则程序应该输出：
Z再例如，
输入：
2054
则程序应该输出：
BZZ我们约定，输入的整数范围[1,2147483647]
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
题解：
package action;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int [] litter = new int[10]; // 位数存储值
int n = sc.nextInt();
int num = 1; // 第几位
while (n != 0) {
if (n % 26 == 0) { // 能除尽，即为z
litter[num] = 26 + 64; // 65是A
n -= 1;
} else {
litter[num] = n % 26 + 64;
}
n /= 26;
num++;
}
// 倒叙打印
for (int i = num - 1; i > 0; i--) {
System.out.print((char)litter[i]);
}
}
}
H、拉马车
小的时候，你玩过纸牌游戏吗？
有一种叫做“拉马车”的游戏，规则很简单，却很吸引小朋友。其规则简述如下：
假设参加游戏的小朋友是A和B，游戏开始的时候，他们得到的随机的纸牌序列如下：
A方：[K, 8, X, K, A, 2, A, 9, 5, A]
B方：[2, 7, K, 5, J, 5, Q, 6, K, 4]其中的X表示“10”，我们忽略了纸牌的花色。
从A方开始，A、B双方轮流出牌。
当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。
此例中，游戏过程：
A出K，B出2，A出8，B出7，A出X，此时桌上的序列为：K,2,8,7,X
当轮到B出牌时，他的牌K与桌上的纸牌序列中的K相同，则把包括K在内的以及两个K之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。
此时，A、B双方的手里牌为：
A方：[K, A, 2, A, 9, 5, A]
B方：[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]赢牌的一方继续出牌。也就是B接着出5，A出K，B出J，A出A，B出5，又赢牌了。
5,K,J,A,5
此时双方手里牌：
A方：[2, A, 9, 5, A]
B方：[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。
当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。
对于本例的初始手牌情况下，最后A会输掉，而B最后的手里牌为：
9K2A62KAX58K57KJ5
本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出-1。
输入为2行，2个串，分别表示A、B双方初始手里的牌序列。
输出为1行，1个串，表示A先出牌，最后赢的一方手里的牌序。例如，
输入：
96J5A898QA
6278A7Q973则程序应该输出：
2J9A7QA6Q6889977再比如，
输入：
25663K6X7448
J88A5KJXX45A则程序应该输出：
6KAJ458KXAX885XJ645我们约定，输入的串的长度不超过30
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
题解：
package action;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class demo {
static char temp;
static boolean ok = true;
static boolean flag = true;
static ArrayList<Character> a = new ArrayList<Character>();
static ArrayList<Character> b = new ArrayList<Character>();
static ArrayList<Character> onging = new ArrayList<Character>();
public static void main(String[] args) {
String str;
Scanner input = new Scanner(System.in);
// 输入
str = input.next();
for (char cha : str.toCharArray()) {
a.add(cha);
}
str = input.next();
for (char cha : str.toCharArray()) {
b.add(cha);
}
input.close();
// 执行
// true就是继续出牌,false就是有没排的
while (ok) {
// flag是我两个人切换的关键点
if (flag) {
ok = underway(a, onging);
if (ok) {
flag = sourse(flag, a, onging);
}
} else {
ok = underway(b, onging);
if (ok) {
flag = sourse(flag, b, onging);
}
}
}
// 打印
if (flag) {
Iterator<Character> it = b.iterator();
while (it.hasNext()) {
System.out.print(it.next());
}
} else {
Iterator<Character> it = a.iterator();
while (it.hasNext()) {
System.out.print(it.next());
}
}
}
// 出牌
public static boolean underway(ArrayList<Character> x, ArrayList<Character> onging) {
temp = x.remove(0);
onging.add(temp);
// 如果其中一方没牌或者出现一次可赢局面（可以拿走牌的情况）
if (x.size() == 0 && onging.lastIndexOf(temp) == onging.indexOf(temp)) {
return false;
}
return true;
}
// 每一次出牌后我都需要验证
public static boolean sourse(boolean flag, ArrayList<Character> x, ArrayList<Character> onging) {
if (onging.size() != 0) {
// temp出现的位置更新说明，又出现了一个temp，取牌后继续执行；反之，没有出现相同的，下个人执行
if (onging.lastIndexOf(temp) == onging.indexOf(temp)) {
return !flag;
}
int end = onging.indexOf(temp) - 1;
// 将lastIndex---Index中间的添加到x中，同时从ongoing中移出
while (onging.size() - 1 != end) {
int onMax = onging.size() - 1;
x.add(onging.get(onMax));
onging.remove(onMax);
}
}
return flag;
}
}
I、青蛙跳杯子
X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。*WWWBBB
其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。
X星的青蛙很有些癖好，它们只做3个动作之一：
1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。对于上图的局面，只要1步，就可跳成下图局面：
WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入为2行，2个串，表示初始局面和目标局面。
输出要求为一个整数，表示至少需要多少步的青蛙跳。例如：
输入：
*WWBB
WWBB*则程序应该输出：
2再例如，
输入：
WWW*BBB
BBB*WWW则程序应该输出：
10我们约定，输入的串的长度不超过15
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
题解视频：
题解：
package action;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class demo {
static String start;
static String end;
static Queue<State> q = new LinkedList<>();
static Set<String> set = new HashSet<>();// 过滤纸重复的队列模式
static int[] dir = { 1, 2, 3, -1, -2, -3 };// 六种状态，-3表示向左边跳三个距离
public static String swap(int a, int b, String str) {// 交换str中 a、b 两处的字符
char cs[] = str.toCharArray();
char temp = cs[a];
cs[a] = cs[b];
cs[b] = temp;
str = new String(cs);
return str;
}
public static int bfs(String now, int pos, int step) {
q.add(new State(now, pos, step));
while (!q.isEmpty()) {
State curState = q.poll();
if (curState.pattern.equals(end))
return curState.step;
if (set.contains(curState.pattern)) {
continue;
} else {
set.add(curState.pattern);
}
for (int i = 0; i < dir.length; i++) {// 六个状态
int nextPos = curState.pos + dir[i];// 下一个空杯的位置
if (nextPos < curState.pattern.length() && nextPos >= 0) {// 得在合法的位置
String temp = curState.pattern;// 记录当前的队列状态
String nextPattern = swap(curState.pos, nextPos, temp);// 交换，产生新的队列模式
State nextState = new State(nextPattern, nextPos, curState.step + 1);
if (!set.contains(nextPattern))
q.add(nextState);
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
start = sc.nextLine();
end = sc.nextLine();
sc.close();
int pos = 0;
for (int i = 0; i < start.length(); i++) {
if (start.charAt(i) == '*') {
pos = i;
break;
}
}
System.out.println(bfs(start, pos, 0));
}
}
class State {
String pattern;// 当前队列模式
int pos;// * 所在的索引
int step;// 从初始队列模式到当前队列模式经过的步数
public State(String now, int pos, int step) {
this.pattern = now;
this.pos = pos;
this.step = step;
}
}
J、图形排版
小明需要在一篇文档中加入 N 张图片，其中第 i 张图片的宽度是 Wi，高度是 Hi。
假设纸张的宽度是 M，小明使用的文档编辑工具会用以下方式对图片进行自动排版：1. 该工具会按照图片顺序，在宽度 M 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。
例如在 M=10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为4。
(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第x张图片占用的版面)0123456789
----------
111
111 333
11122333
111223332. 如果当前行剩余宽度大于0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向 上取整)，然后放入当前行。例如再放入一张4x9的图片，由于剩余宽度是2，这张图片会被压缩到2x5，再被放入第一行的末尾。此时该行高度为5：
0123456789
----------
44
111 44
111 33344
1112233344
11122333443. 如果当前行剩余宽度为0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 N 张图片的排版高度。例如再放入11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为11：
0123456789
----------
44
111 44
111 33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 N 张图片中选择一张删除掉以降低总高度。他希望剩余N-1张图片按原顺序的排版高度最低，你能求出最低高度是多少么？
输入：
第一行包含两个整数 M 和 N，分别表示纸张宽度和图片的数量。
接下来 N 行，每行2个整数Wi, Hi，表示第 i 个图大小为 Wi*Hi。对于30%的数据，满足1<=N<=1000
对于100%的数据，满足1<=N<=100000，1<=M, Wi, Hi<=100输出：
一个整数，表示在删除掉某一张图片之后，排版高度最少能是多少。样例输入：
4 3
2 2
2 3
2 2样例输出：
2另一个示例，
样例输入：
2 10
4 4
4 3
1 3
4 5
2 1
2 3
5 4
5 3
1 5
2 4样例输出：
17资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
题解：
package action;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class demo {
public static void main(String[] arg) {
solve();
}
static StringTokenizer ST;
static BufferedReader BR;
static PrintWriter PW;
static String next() {
while (ST == null || !ST.hasMoreTokens()) {
try {
ST = new StringTokenizer(BR.readLine());
} catch (Exception e) {
// TODO: handle exception
throw new RuntimeException(e);
}
}
return ST.nextToken();
}
static int nextInt() {
return Integer.parseInt(next());
}
public static void solve() {
BR = new BufferedReader(new InputStreamReader(System.in));
PW = new PrintWriter(System.out);
int m = nextInt(), n = nextInt();
Pair a[] = new Pair[n + 10];
Triple cr[] = new Triple[n + 10];
cr[0] = new Triple();
// 正向处理出加到第i块的状态，Triple记忆第i块右下坐标(x,y)和第i块缩放后的高度h
for (int i = 1; i <= n; i++) {
// 创建
Triple tmp = new Triple(cr[i - 1]);
// 如果这一行装不下，就置零换行
if (tmp.x == m)
tmp.x = tmp.h = 0;
// 新建输入的宽高
a[i] = new Pair(nextInt(), nextInt());
cr[i] = new Triple();
Pair b = Change(a[i], m - tmp.x);
// 保存当前的位置
cr[i].x = tmp.x + b.x;
cr[i].h = Math.max(tmp.h, b.y);
cr[i].y = cr[i].h + tmp.y - tmp.h;
}
Triple A[] = new Triple[m];
Triple B[] = new Triple[m];
for (int i = 0; i < m; i++) {
A[i] = new Triple();
B[i] = new Triple();
}
int ans = cr[n].y;
// 把每一个都尝试一下
for (int i = n; i >= 1; i--) {
// 处理删除第i块的答案ah
Triple pre = cr[i - 1];
int ah;
if (pre.x == m) {
ah = pre.y + B[0].y;
} else {
ah = pre.y - pre.h + B[pre.x].y - B[pre.x].h + Math.max(pre.h, B[pre.x].h);
}
ans = Math.min(ans, ah);
// 逆向DP，处理出第i至n块从(0,j)位置开始放置
for (int j = 0; j < m; j++) {
Pair b = Change(a[i], m - j);
Triple tmp;
// 放完这个我就要换行
if (j + b.x == m)
tmp = new Triple(0, B[0].y, 0);
// 如果不换行，还是这个
else
tmp = new Triple(B[j + b.x]);
A[j].h = Math.max(b.y, tmp.h);
A[j].y = A[j].h + tmp.y - tmp.h;
}
for (int j = 0; j < m; j++)
B[j] = new Triple(A[j]);
}
PW.print(ans);
PW.close();
}
// a的x小就返回a，否则返回
static Pair Change(Pair A, int x) {
if (A.x <= x)
return new Pair(A);
return new Pair(x, (A.y * x + A.x - 1) / A.x);
}
}
class Pair implements Comparable<Pair> {
int x, y;
Pair() {
}
Pair(Pair A) {
x = A.x;
y = A.y;
}
Pair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pair A) {
return x == A.x ? y - A.y : x - A.x;
}
}
class Triple {
int x, y, h;
Triple() {
}
Triple(int x, int y, int h) {
this.x = x;
this.y = y;
this.h = h;
}
Triple(Triple A) {
x = A.x;
y = A.y;
h = A.h;
}
@Override
public String toString() {
return String.valueOf(x) + " " + String.valueOf(y) + " " + String.valueOf(h);
}
}
- 点赞
- 收藏
- 关注作者
评论（0）