第八届蓝桥杯java B组国赛题目

xiaoxiao2021-02-28 34

第八届蓝桥杯java B组国赛题目

第一题：平方十位数

由0~9这10个数字不重复、不遗漏，可以组成很多10位数字。这其中也有很多恰好是平方数（是某个数的平方）。比如：1026753849，就是其中最小的一个平方数。请你找出其中最大的一个平方数是多少？注意：你需要提交的是一个10位数字，不要填写任何多余内容。

直接全排求，我得到的答案取最大的：9814072356

import java.util.HashMap; import java.util.Iterator; import java.util.Random; import java.util.Scanner; public class Main { static int arr[] = {9,8,7,6,5,4,3,2,1,0}; static int visited[] = {0,0,0,0,0,0,0,0,0,0}; public static void main(String[] args) { dfs(0); } public static void dfs(int offset) { if(offset == 10 ) { long a = 0l; for(int i = 0; i < 10; i++) { a = a * 10 + arr[i]; } long sq = (long) Math.sqrt(a); if(sq * sq == a) { System.out.println(a); return; } } for(int i = 0; i < 10; i++) { if(visited[i] == 0) { visited[i] = 1; arr[offset] = i; dfs(offset+1); visited[i] = 0; } } } }

第二题：生命游戏

康威生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。这个游戏在一个无限大的2D网格上进行。初始时，每个小方格中居住着一个活着或死了的细胞。下一时刻每个细胞的状态都由它周围八个格子的细胞状态决定。具体来说： 1. 当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时，该细胞变成死亡状态。（模拟生命数量稀少） 2. 当前细胞为存活状态时，当周围有2个或3个存活细胞时，该细胞保持原样。 3. 当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多） 4. 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。（模拟繁殖）当前代所有细胞同时被以上规则处理后, 可以得到下一代细胞图。按规则继续处理这一代的细胞图，可以得到再下一代的细胞图，周而复始。例如假设初始是:(X代表活细胞，.代表死细胞) ..... ..... .XXX. .....

下一代会变为:

..... ..X.. ..X.. ..X.. ..... 康威生命游戏中会出现一些有趣的模式。例如稳定不变的模式： .... .XX. .XX. .... 还有会循环的模式： ...... ...... ...... .XX... .XX... .XX... .XX... .X.... .XX... ...XX. -> ....X. -> ...XX. ...XX. ...XX. ...XX. ...... ...... ...... 本题中我们要讨论的是一个非常特殊的模式，被称作"Gosper glider gun"： ...................................... .........................X............ .......................X.X............ .............XX......XX............XX. ............X...X....XX............XX. .XX........X.....X...XX............... .XX........X...X.XX....X.X............ ...........X.....X.......X............ ............X...X..................... .............XX....................... ...................................... 假设以上初始状态是第0代，请问第1000000000(十亿)代一共有多少活着的细胞？注意：我们假定细胞机在无限的2D网格上推演，并非只有题目中画出的那点空间。当然，对于遥远的位置，其初始状态一概为死细胞。

注意：需要提交的是一个整数，不要填写多余内容。

解答：十亿代看起来，，很吓人，，但是其实到后面已经有规律了，

下面这一串数字是每一代变化之后比起前一代，活细胞数量的变化

3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7

大家注意我的颜色标识，这是一段重复的数据串

根据这一段，就可以很轻松的算出来10亿代后的结果

而不用跑10亿次循环，结果是166666682，具体代码如下

import java.math.BigInteger; import java.util.ArrayList; public class T2 { static ArrayList<point> list = new ArrayList<point>(); static ArrayList<point> listcopy = new ArrayList<point>(); static String values[] = { "......................................", ".........................X............", ".......................X.X............", ".............XX......XX............XX.", "............X...X....XX............XX.", ".XX........X.....X...XX...............", ".XX........X...X.XX....X.X............", "...........X.....X.......X............", "............X...X.....................", ".............XX.......................", "......................................", }; static ArrayList<Integer> sizelist = new ArrayList<Integer>(); public static void main(String[] Args) { for (int i = 0; i < values.length; i++) { for (int j = 0; j < values[i].length(); j++) { if (values[i].charAt(j) == 'X') list.add(new point(i + 1, j + 1)); } } BigInteger time = new BigInteger("0");// 计数器 while (true) { // print(list); time = time.add(new BigInteger("1")); // 模拟一轮的变化，并将新的活细胞位置存在listcopy中 for (int i = 0; i < list.size(); i++) { // print(list); // System.out.println(); int j = 0; int x = list.get(i).x; int y = list.get(i).y; if (list.contains(new point(x - 1, y - 1))) { j++; } else if (round(new point(x - 1, y - 1), list) == 3) { if (!listcopy.contains(new point(x - 1, y - 1))) listcopy.add(new point(x - 1, y - 1)); } if (list.contains(new point(x, y - 1))) { j++; } else if (round(new point(x, y - 1), list) == 3) { if (!listcopy.contains(new point(x, y - 1))) listcopy.add(new point(x, y - 1)); } if (list.contains(new point(x + 1, y - 1))) { j++; } else if (round(new point(x + 1, y - 1), list) == 3) { if (!listcopy.contains(new point(x + 1, y - 1))) listcopy.add(new point(x + 1, y - 1)); } if (list.contains(new point(x - 1, y))) { j++; } else if (round(new point(x - 1, y), list) == 3) { if (!listcopy.contains(new point(x - 1, y))) listcopy.add(new point(x - 1, y)); } if (list.contains(new point(x + 1, y))) { j++; } else if (round(new point(x + 1, y), list) == 3) { if (!listcopy.contains(new point(x + 1, y))) listcopy.add(new point(x + 1, y)); } if (list.contains(new point(x - 1, y + 1))) { j++; } else if (round(new point(x - 1, y + 1), list) == 3) { if (!listcopy.contains(new point(x - 1, y + 1))) listcopy.add(new point(x - 1, y + 1)); } if (list.contains(new point(x, y + 1))) { j++; } else if (round(new point(x, y + 1), list) == 3) { if (!listcopy.contains(new point(x, y + 1))) listcopy.add(new point(x, y + 1)); } if (list.contains(new point(x + 1, y + 1))) { j++; } else if (round(new point(x + 1, y + 1), list) == 3) { if (!listcopy.contains(new point(x + 1, y + 1))) listcopy.add(new point(x + 1, y + 1)); } if (j == 2 || j == 3) listcopy.add(list.get(i)); } sizelist.add(listcopy.size() - list.size()); //System.out.print(listcopy.size() - list.size() + " "); list = listcopy; listcopy = new ArrayList<point>(); if (back(sizelist)) { BigInteger arrlenth = new BigInteger(sizelist.size() / 4 + ""); int sum = 0; for (Integer inte : sizelist) { sum += inte; } sum /= 4; BigInteger first = new BigInteger(sum + ""); BigInteger change = new BigInteger(sum + ""); BigInteger answer = new BigInteger("0"); int mut = new BigInteger("1000000000").remainder(arrlenth).intValue(); for (int i = 0; i < mut; i++) { answer = answer.add(new BigInteger("" + sizelist.get(i))); } answer = answer.add(first.add(change.multiply(new BigInteger("1000000000").divide(arrlenth)))); System.out.println(answer); break; } } } // 返回点i周围存活点的个数 public static int round(point i, ArrayList<point> vals) { int j = 0; int x = i.x; int y = i.y; if (list.contains(new point(x - 1, y - 1))) { j++; } if (list.contains(new point(x, y - 1))) { j++; } if (list.contains(new point(x + 1, y - 1))) { j++; } if (list.contains(new point(x - 1, y))) { j++; } if (list.contains(new point(x + 1, y))) { j++; } if (list.contains(new point(x - 1, y + 1))) { j++; } if (list.contains(new point(x, y + 1))) { j++; } if (list.contains(new point(x + 1, y + 1))) { j++; } return j; } // 当List中数组为4个循环时返回真 public static boolean back(ArrayList<Integer> val) { if (val.size() % 4 != 0) return false; else { for (int i = 0; i < val.size() / 4; i++) { if (val.get(i) != val.get(i + val.size() / 4) || val.get(i) != val.get(i + val.size() / 2) || val.get(i) != val.get(i + 3 * val.size() / 4)) return false; } return true; } } // 尝试输出，用于检查错误 public static void print(ArrayList<point> val) { point[] vcc = new point[0]; vcc = val.toArray(vcc); int maxx = vcc[0].x; int minx = vcc[0].x; int maxy = vcc[0].y; int miny = vcc[0].y; for (point point : vcc) { if (point.x > maxx) maxx = point.x; else if (point.x < minx) minx = point.x; if (point.y > maxy) maxy = point.y; else if (point.y < miny) miny = point.y; } for (int x = minx; x <= maxx; x++) { for (int y = miny; y <= maxy; y++) { if (val.contains(new point(x, y))) System.out.print("X"); else System.out.print("."); } System.out.println(); } } } // 用于代表细胞 class point { int x; int y; public point(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object obj) { if (obj instanceof point) if (((point) obj).x == this.x && ((point) obj).y == this.y) return true; return false; } }

第三题：树形显示

对于分类结构可以用树形来形象地表示。比如：文件系统就是典型的例子。树中的结点具有父子关系。我们在显示的时候，把子项向右缩进（用空格，不是tab），并添加必要的连接线，以使其层次关系更醒目。下面的代码就是为了这个目的的，请仔细阅读源码，并填写划线部分缺少的代码。

如有平字体对齐问题，可以参见图【p1.png】

注意，只填写划线部分缺少的代码，不要抄写已有的代码或符号。

答案：s = (last_child(pa) ? "":"|") + space(4) + s;

import java.util.*; class MyTree { private Map<String, List<String>> map_ch = new HashMap<String, List<String>>(); private Map<String, String> map_pa = new HashMap<String, String>(); public void add(String parent, String child) { map_pa.put(child, parent); List<String> lst = map_ch.get(parent); if (lst == null) { lst = new ArrayList<String>(); map_ch.put(parent, lst); } lst.add(child); } public String get_parent(String me) { return map_pa.get(me); } public List<String> get_child(String me) { return map_ch.get(me); } private String space(int n) { String s = ""; for (int i = 0; i < n; i++) s += ' '; return s; } private boolean last_child(String x) { String pa = map_pa.get(x); if (pa == null) return true; List<String> lst = map_ch.get(pa); return lst.get(lst.size() - 1).equals(x); } public void show(String x) { String s = "+--" + x; String pa = x; while (true) { pa = map_pa.get(pa); if (pa == null) break; s = ___________________________________; // 填空 } System.out.println(s); } public void dfs(String x) { show(x); List<String> lst = map_ch.get(x); if (lst == null) return; for (String it : lst) { dfs(it); } } } public class TreeView { public static void main(String[] args) { MyTree tree = new MyTree(); tree.add("root", "dog"); tree.add("root", "cat"); tree.add("root", "duck"); tree.add("dog", "AAdog"); tree.add("dog", "BBdog"); tree.add("dog", "CCdog"); tree.add("AAdog", "AAdog01"); tree.add("AAdog", "AAdog02"); tree.add("cat", "XXcat"); tree.add("cat", "YYcat"); tree.add("XXcat", "XXcat-oo"); tree.add("XXcat", "XXcat-qq"); tree.add("XXcat-qq", "XXcat-qq-hahah"); tree.add("duck", "TTduck"); tree.add("TTduck", "TTduck-001"); tree.add("TTduck", "TTduck-002"); tree.add("TTduck", "TTduck-003"); tree.add("YYcat", "YYcat.hello"); tree.add("YYcat", "YYcat.yes"); tree.add("YYcat", "YYcat.me"); tree.dfs("root"); } }

对于题目中的测试数据，输出结果:+--root +--dog | +--AAdog | | +--AAdog01 | | +--AAdog02 | +--BBdog | +--CCdog +--cat | +--XXcat | | +--XXcat-oo | | +--XXcat-qq | | +--XXcat-qq-hahah | +--YYcat | +--YYcat.hello | +--YYcat.yes | +--YYcat.me +--duck +--TTduck +--TTduck-001 +--TTduck-002 +--TTduck-003

第四题：小计算器

模拟程序型计算器，依次输入指令，可能包含的指令有

1. 数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数2. 运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余3. 进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36)4. 输出指令：'EQUAL'，以当前进制输出结果5. 重置指令：'CLEAR'，清除当前数字指令按照以下规则给出：数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令进制转换指令可能出现在任何地方运算过程中中间变量均为非负整数，且小于2^63。以大写的'A'~'Z'表示10~35[输入格式]第1行：1个n，表示指令数量第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则[输出格式]依次给出每一次'EQUAL'得到的结果[样例输入]7CLEARNUM 1024CHANGE 2ADDNUM 100000CHANGE 8EQUAL[样例输出]2040

#include <cstdio> #include <string> #include <cstdlib> #include <vector> #include <iostream> #include <cstring> using namespace std; typedef long long LL; string Left,oper,Right,Hex="10"; LL hexToTen(string num){ LL HEX=atoll(Hex.c_str()); if(HEX==10) return atoll(num.c_str()); LL res=0,temp=1; int base=0; for(int i=num.size()-1;i>=0;--i){ char c=num[i]; if(c>='A'&&c<='Z') base=10+(c-'A'); else base=c-'0'; res+=temp*base; temp*=HEX; } return res; } LL getResult(){ LL a=atoll(Left.c_str()),b=atoll(Right.c_str()),c=0; if(oper=="ADD") c=a+b; else if(oper=="SUB") c=a-b; else if(oper=="MUL") c=a*b; else if(oper=="DIV") c=a/b; else if(oper=="MOD") c=a%b; return c; } void hexToNow(LL result){ if(result==0){ puts("0"); return; } vector<char>vect; LL t,HEX=atoll(Hex.c_str()); while(result!=0){ t=result%HEX; if(t>=10) vect.push_back((char)('A'+t-10)); else vect.push_back((char)(t+'0')); result/=HEX; } char res[101]; int len=0; for(int i=vect.size()-1;i>=0;--i){ res[len++]=vect[i]; } res[len]='\0'; puts(res); } void solveOper(string order,string num){ char temp[101]; if(order=="NUM"){ if(oper==""){ sprintf(temp,"%lld",hexToTen(num)); Left=string(temp); } else{ sprintf(temp,"%lld",hexToTen(num)); Right=string(temp); sprintf(temp,"%lld",getResult()); Left=string(temp); oper=Right=""; } } else if(order=="CHANGE"){ Hex=num; } else if(order=="EQUAL"){ hexToNow(atoll(Left.c_str())); } else if(order=="CLEAR"){ Left=oper=Right=""; } else{ oper=order; } } int main(){ int n; char str[51]; scanf("%d",&n); getchar(); while(n--){ fgets(str,sizeof(str),stdin); string order(str,strlen(str)-1); int index=order.find(' '); if(index<0){ solveOper(order,""); }else{ solveOper(order.substr(0,index),order.substr(index+1)); } } }

第五题：填字母游戏

小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说： “我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。 K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。并且： 1. 轮到某人填的时候，只能在某个空格中填入L或O 2. 谁先让字母组成了“LOL”的字样，谁获胜。 3. 如果所有格子都填满了，仍无法组成LOL，则平局。小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。本题的输入格式为：第一行，数字n（n<10），表示下面有n个初始局面。接下来，n行，每行一个串，表示开始的局面。比如：“******”, 表示有6个空格。 “L****”, 表示左边是一个字母L，它的右边是4个空格。要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。 1 表示能赢 -1 表示必输 0 表示可以逼平例如，输入： 4 *** L**L L**L***L L*****L 则程序应该输出： 0 -1 1 1 资源约定：峰值内存消耗 < 256M

CPU消耗 < 1000ms

解析：该问题为有平局博弈问题，一般解决方法：

f(局面 x) { t = 输 for(所有可能走法){ 试走 x --> y if f(y)= ? { 输 ==> return 赢平 ==> t = 平 } 回溯 } return t }

code:

public class Main { static int f(char [] c) { String s=new String(c); if(s.contains("LOL")) return -1; if(s.contains("*")==false) return 0;//出口勿漏 boolean ping=false;//假设无法逼平 for(int i=0;i<c.length;i++) { if(c[i]=='*') { try { c[i]='L';//进行试探 if(f(c)==-1) return 1; else if(f(c)==0) ping=true; //不能直接返回0，否则不能进行进一步试探 c[i]='O'; if(f(c)==-1) return 1; else if(f(c)==0) ping=true; } finally { c[i]='*';//回溯 } } } if(ping) return 0; return -1; } public static void main(String[] args) { System.out.println(f("***".toCharArray())); System.out.println(f("L**L".toCharArray())); System.out.println(f("L**L***L".toCharArray())); System.out.println(f("L*****L".toCharArray())); } }

第六题：区间移位

数轴上有n个闭区间：D1,...,Dn。其中区间Di用一对整数[ai, bi]来描述，满足ai < bi。已知这些区间的长度之和至少有10000。所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖[0, 10000]——也就是说[0, 10000]这个区间内的每一个点都落于至少一个区间内。你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。具体来说，假设你将Di移动到[ai+ci, bi+ci]这个位置。你希望使得maxi{|ci|} 最小。【输入格式】输入的第一行包含一个整数n，表示区间的数量。接下来有n行，每行2个整数ai, bi，以一个空格分开，表示区间[ai, bi]。保证区间的长度之和至少是10000。【输出格式】输出一个数字，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。【样例输入】 2 10 5010 4980 9980 【样例输出】 20 【样例说明】第一个区间往左移动10；第二个区间往右移动20。【样例输入】 4 0 4000 3000 5000 5001 8000 7000 10000 【样例输出】 0.5 【样例说明】第2个区间往右移0.5；第3个区间往左移0.5即可。【数据规模与约定】对于30%的评测用例，1 <= n <= 10；对于100%的评测用例，1 <= n <= 10000，0 <= ai < bi <= 10000。资源约定：峰值内存消耗 < 256M

CPU消耗 < 2000ms

import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ArrayList<Integer> a = new ArrayList<Integer>(); ArrayList<Integer> b = new ArrayList<Integer>(); int n = scanner.nextInt(); int mini = 0,maxi = 0; int min = 10000,max = 0; for(int i=0;i<n;i++) { int temp = scanner.nextInt(); a.add(temp); if(temp<min){ mini=i; min=temp; } temp = scanner.nextInt(); b.add(temp); if(temp>max){ maxi=i; max = temp; } } int left=0,right=10000; float yimax=0; while(left<right) { int l=left,r=right; int yi = min-left; int yi1; if(yi>=0){ yi1=yi; }else{ yi1=yi*(-1); } left = b.get(mini)-yi; yi = right - max; int yi2 ; if(yi>=0){ yi2=yi; }else{ yi2=yi*(-1); } right = a.get(maxi)+yi; if(right<left) { float p = a.get(maxi); float q = b.get(mini); float j = (p-q)/2; float zuo = a.get(mini)+j; float you = b.get(maxi)-j; if(zuo>l) { j+=(zuo-l); }else if(you<r) { j+=(r-you); } if(j<yi1&&j<yi2){ if(yimax<j) yimax=j; } else if(yi1>=yi2){ if(yi1>yimax) yimax=yi1; } else if(yi1<yi2){ if(yi2>yimax) yimax=yi2; } }else { if(yi1>=yi2){ if(yi1>yimax) yimax=yi1; } else if(yi1<yi2){ if(yi2>yimax) yimax=yi2; } } a.remove(mini); b.remove(mini); if(maxi!=mini) { if(maxi>mini)maxi--; a.remove(maxi); b.remove(maxi); } if(a.size()==0)break; mini=0; maxi=0; int minju = Math.abs(a.get(0)-left); int maxju = Math.abs(b.get(0)-right); for(int i=1;i<a.size();i++) { int temp = Math.abs(a.get(i)-left); if(temp<minju){ minju=temp; mini=i; } temp = Math.abs(b.get(i)-right); if(temp<maxju){ maxju=temp; maxi=i; } } min = a.get(mini); max = b.get(maxi); } if(yimax-(int)yimax==0)System.out.print((int)yimax); else System.out.printf("%.1f",yimax); } }

转载请注明原文地址: https://www.6miu.com/read-2623150.html

技术

最新回复(0)