蓝桥杯javaB决赛历届真题

第六届T1 分机号T2 五星填数T3 显示二叉树T4 穿越雷区T5 表格计算T6 铺瓷砖 第七届T1 愤怒小鸟T2 反幻方T3 打靶T4 路径之谜T5 碱基T6 圆圈舞 第八届T1 平方十位数T2 生命游戏T3 树形显示T4 小计算器T5 填字母游戏 第九届T1T2T3 全排列T4 整理玩具T6 防御力 第十届试题 A: 递增序列试题 B: 平方拆分试题 C: 切割试题 D: 最优旅行试题 E: 序列求和试题 F: 最长子序列试题 G: 数正方形试题 H: 大胖子走迷宫试题 I: 估计人数试题 J: 分考场

第六届

T1 分机号

X老板脾气古怪，他们公司的电话分机号都是3位数，老板规定，所有号码必须是降序排列，且不能有重复的数位。比如：751,520,321 都满足要求，而，766,918,201 就不符合要求。现在请你计算一下，按照这样的规定，一共有多少个可用的3位分机号码？请直接提交该数字，不要填写任何多余的内容。

T2 五星填数

如【图1.png】的五星图案节点填上数字：1~12，除去7和11。要求每条直线上数字和相等。如图就是恰当的填法。请你利用计算机搜索所有可能的填法有多少种。注意：旋转或镜像后相同的算同一种填法。请提交表示方案数目的整数，不要填写任何其它内容。

T3 显示二叉树

排序二叉树的特征是：某个节点的左子树的所有节点值都不大于本节点值。某个节点的右子树的所有节点值都不小于本节点值。为了能形象地观察二叉树的建立过程，小明写了一段程序来显示出二叉树的结构来。class BiTree{private int v;private BiTree l;private BiTree r;public BiTree(int v){this.v = v;}public void add(BiTree the){if(the.v < v){if(l==null) l = the;else l.add(the);}else{if(r==null) r = the;else r.add(the);}}public int getHeight(){int h = 2;int hl = l==null? 0 : l.getHeight();int hr = r==null? 0 : r.getHeight();return h + Math.max(hl,hr);}public int getWidth(){int w = (""+v).length();if(l!=null) w += l.getWidth();if(r!=null) w += r.getWidth();return w;}public void show(){char[][] buf = new char[getHeight()][getWidth()];printInBuf(buf, 0, 0);showBuf(buf);}private void showBuf(char[][] x){for(int i=0; i<x.length; i++){for(int j=0; j<x[i].length; j++)System.out.print(x[i][j]==0? ' ':x[i][j]);System.out.println();}}private void printInBuf(char[][] buf, int x, int y){String sv = "" + v;int p1 = l==null? x : l.getRootPos(x);int p2 = getRootPos(x);int p3 = r==null? p2 : r.getRootPos(p2+sv.length());buf[y][p2] = '|';for(int i=p1; i<=p3; i++) buf[y+1][i]='-';for(int i=0; i<sv.length(); i++) ________________________________; //填空位置if(p1<p2) buf[y+1][p1] = '/';if(p3>p2) buf[y+1][p3] = '\\';if(l!=null) l.printInBuf(buf,x,y+2);if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);}private int getRootPos(int x){return l==null? x : x + l.getWidth();}}public class Main{public static void main(String[] args){BiTree tree = new BiTree(500);tree.add(new BiTree(200));tree.add(new BiTree(509));tree.add(new BiTree(100));tree.add(new BiTree(250));tree.add(new BiTree(507));tree.add(new BiTree(600));tree.add(new BiTree(650));tree.add(new BiTree(450));tree.add(new BiTree(510));tree.add(new BiTree(440));tree.add(new BiTree(220));tree.show();}}对于上边的测试数据，应该显示出：|/--------------500---\||/--200---\ /--509---\| | | |100 /--250---\507 /--600\| | ||220 /--450 510 650|440（如有对齐问题，请参考【图1.png】）请分析程序逻辑，填写划线部分缺失的代码。注意，只填写缺少的部分，不要填写已有的代码或符号，也不要加任何说明文字。

T4 穿越雷区

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。例如：A + - + -- + - - +- + + + -+ - + - +B + - + -坦克车只能水平或垂直方向上移动到相邻的区。数据格式要求：输入第一行是一个整数n，表示方阵的大小， 4<=n<100接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。A，B都只出现一次。要求输出一个整数，表示坦克从A区到B区的最少移动步数。如果没有方案，则输出-1例如：用户输入：5A + - + -- + - - +- + + + -+ - + - +B + - + -则程序应该输出：10资源约定：峰值内存消耗（含虚拟机） < 512MCPU消耗 < 2000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

T5 表格计算

某次无聊中， atm 发现了一个很老的程序。这个程序的功能类似于 Excel ，它对一个表格进行操作。不妨设表格有 n 行，每行有 m 个格子。每个格子的内容可以是一个正整数，也可以是一个公式。公式包括三种：1. SUM(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的和。2. AVG(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的平均数。3. STD(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的标准差。标准差即为方差的平方根。方差就是：每个数据与平均值的差的平方的平均值，用来衡量单个数据离开平均数的程度。公式都不会出现嵌套。如果这个格子内是一个数，则这个格子的值等于这个数，否则这个格子的值等于格子公式求值结果。输入这个表格后，程序会输出每个格子的值。atm 觉得这个程序很好玩，他也想实现一下这个程序。「输入格式」第一行两个数 n, m 。接下来 n 行输入一个表格。每行 m 个由空格隔开的字符串，分别表示对应格子的内容。输入保证不会出现循环依赖的情况，即不会出现两个格子 a 和 b 使得 a 的值依赖 b 的值且 b 的值依赖 a 的值。「输出格式」输出一个表格，共 n 行，每行 m 个保留两位小数的实数。数据保证不会有格子的值超过 1e6 。「样例输入」3 21 SUM(2,1:3,1)2 AVG(1,1:1,2)SUM(1,1:2,1) STD(1,1:2,2)「样例输出」1.00 5.002.00 3.003.00 1.48「数据范围」对于 30% 的数据，满足： n, m <= 5对于 100% 的数据，满足： n, m <= 50资源约定：峰值内存消耗（含虚拟机） < 512MCPU消耗 < 2000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

T6 铺瓷砖

为了让蓝桥杯竞赛更顺利的进行，主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个n*m的矩形，而这次使用的瓷砖比较特别，有两种形状，如【图1.png】所示。在铺放瓷砖时，可以旋转。主办方想知道，如果使用这两种瓷砖把机房铺满，有多少种方案。【输入格式】输入的第一行包含两个整数，分别表示机房两个方向的长度。【输出格式】输出一个整数，表示可行的方案数。这个数可能很大，请输出这个数除以65521的余数。【样例输入1】4 4【样例输出1】2【样例说明1】这两种方案如下【图2.png】所示：【样例输入2】2 6【样例输出2】4【数据规模与约定】对于20%的数据，1<=n, m<=5。对于50%的数据，1<=n<=100，1<=m<=5。对于100%的数据，1<=n<=10^15，1<=m<=6。资源约定：峰值内存消耗（含虚拟机） < 512MCPU消耗 < 8000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

第七届

T1 愤怒小鸟

X星球愤怒的小鸟喜欢撞火车！一根平直的铁轨上两火车间相距 1000 米两火车 （不妨称A和B） 以时速 10米/秒 相对行驶。愤怒的小鸟从A车出发，时速50米/秒，撞向B车，然后返回去撞A车，再返回去撞B车，如此往复....两火车在相距1米处停车。问：这期间愤怒的小鸟撞 B 车多少次？注意：需要提交的是一个整数（表示撞B车的次数），不要填写任何其它内容。

T2 反幻方

我国古籍很早就记载着2 9 47 5 36 1 8这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。下面考虑一个相反的问题。可不可以用 1~9 的数字填入九宫格。使得：每行每列每个对角线上的数字和都互不相等呢？这应该能做到。比如：9 1 28 4 37 5 6你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。旋转或镜像算同一种。比如：9 1 28 4 37 5 67 8 95 4 16 3 22 1 93 4 86 5 7等都算作同一种情况。请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。

T3 打靶

小明参加X星球的打靶比赛。比赛使用电子感应计分系统。其中有一局，小明得了96分。这局小明共打了6发子弹，没有脱靶。但望远镜看过去，只有3个弹孔。显然，有些子弹准确地穿过了前边的弹孔。不同环数得分是这样设置的：1,2,3,5,10,20,25,50那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？下面的程序解决了这个问题。仔细阅读分析代码，填写划线部分缺失的内容。public class Main{static void f(int[] ta, int[] da, int k, int ho, int bu, int sc){if(ho<0 || bu<0 || sc<0) return;if(k==ta.length){if(ho>0 || bu>0 || sc>0) return;for(int i=0; i<da.length; i++){for(int j=0; j<da[i]; j++) System.out.print(ta[i] + " ");}System.out.println();return;}for(int i=0; i<=bu; i++){da[k] = i;f(ta, da, k+1, __________________ , bu-i, sc-ta[k]*i); // 填空位置}da[k] = 0;}public static void main(String[] args){int[] ta = {1,2,3,5,10,20,25,50};int[] da = new int[8];f(ta, da, 0, 3, 6, 96);}}注意：只填写划线处缺少的内容，不要填写已有的代码或符号，也不要填写任何解释说明文字等。

T4 路径之谜

小明冒充X星球的骑士，进入了一个奇怪的城堡。城堡里边什么都没有，只有方形石头铺成的地面。假设城堡地面是 n x n 个方格。【如图1.png】所示。按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必做完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如图1.png中的例子。本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）输入：第一行一个整数N(0<N<20)，表示地面有 N x N 个方格第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）输出：一行若干个整数，表示骑士路径。为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....比如，图1.png中的方块编号为：0 1 2 34 5 6 78 9 10 1112 13 14 15示例：用户输入：42 4 3 44 3 3 3程序应该输出：0 4 5 1 2 3 7 11 10 9 13 14 15资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

T5 碱基

生物学家正在对n个物种进行研究。其中第i个物种的DNA序列为s[i]，其中的第j个碱基为s[i][j],碱基一定是A、T、G、C之一。生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说，科学家关心的序列用2m元组(i1,p1,i2,p2....im,pm)表示，满足:1<=i1<i2<....<im<=n;且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=....=s[im][pm+q]。现在给定所有生物的DNA序列，请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同，则认为是不同的元组。【输入格式】输入的第一行包含三个整数n、m、k，两个整数之间用一个空格分隔，意义如题目所述。接下来n行，每行一个字符串表示一种生物的DNA序列。DNA序列从1至n编号，每个序列中的碱基从1开始依次编号，不同的生物的DNA序列长度可能不同。【输出格式】输出一个整数，表示关注的元组个数。答案可能很大，你需要输出答案除以1000000007的余数。【样例输入】3 2 2ATCTCGACG【样例输出】2再例如：【样例输入】4 3 3AAAAAAAAAAAAA【样例输出】7【数据规模与约定】对于20%的数据，k<=5,所有字符串总长L满足L <=100对于30%的数据，L<=10000对于60%的数据，L<=30000对于100%的数据，n<=5,m<=5,1<=k<=L<=100000保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

T6 圆圈舞

春天温暖的阳光照耀着大地，正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会，欢度这美好的时光。舞会上最重要的一个环节就是跳圆舞曲，n只小动物手拉手围成一大圈，随着音乐跳起来。在跳的过程中，小动物们可能会变换队形。它们的变换方式是动物A松开自己右手，动物B松开自己的左手，动物A和B手拉到一起，而它们对应的松开的手（如果有的话）也拉到一起。例如，假设有10只小动物，按顺序围成一圈，动物1的右手拉着动物2的左手，动物2的右手拉着动物3的左手，依次类推，最后动物10的右手拉着动物1的左手。如果通过动物2和8变换队形，则动物2的右手拉着动物8的左手，而对应的动物3的左手拉着动物7的右手，这样形成了1-2-8-9-10和3-4-5-6-7两个圈。如果此时通过动物2和6变换队形，则将形成1-2-6-7-3-4-5-8-9-10一个大圈。注意，如果此时通过动物1和2变换队形，那么队形不会改变，因为动物1的右手和动物2的左手松开后又拉到一起了。在跳舞的过程中，每个动物i都有一个欢乐值Hi和一个感动值Fi。如果两个动物在一个圈中，欢乐值会彼此影响，产生欢乐能量。如果两个动物i, j（i≠j）在同一个大小为t的圈中，而动物i在动物j右手的第p个位置（动物j右手的第1个位置就是动物j右手所拉着的动物，而第2个位置就是右手第1个位置的动物右手拉着的动物，依次类推），则产生的欢乐能量为(t-p)*Hj*Fi。在跳舞的过程中，动物们的欢乐值和感动值有可能发生变化。圆舞曲开始的时候，所有的动物按编号顺序围成一个圈，动物n右手的第i个位置正好是动物i。现在已知小动物们变换队形的过程和欢乐值、感动值变化的过程，求每次变换后所有动物所产生的欢迎能量之和。【输入格式】输入的第一行包含一个整数n，表示动物的数量。接下来n行，每行两个用空格分隔的整数Hi, Fi，按编号顺序给出每只动物的欢乐值和感动值。接下来一行包含一个整数m，表示队形、欢乐值、感动值的变化次数。接下来m行，每行三个用空格分隔的整数k, p, q，当k=1时，表示小动物们通过动物p和动物q变换了队形，当k=2时，表示动物p的欢乐值变为q，当k=3时，表示动物p的感动值变为了q。【输出格式】输出m行，每行一个整数，表示每次变化后所有动物产生的能量之和。答案可能很大，你需要计算答案除以1000000007的余数。【样例输入】101 11 11 11 11 11 11 11 11 11 191 2 81 2 62 8 103 5 101 1 21 2 12 5 51 4 81 4 5【样例输出】10045085513411341811923338923【数据规模与约定】对于20%的数据，2<=n,m<=100。对于30%的数据，2<=n,m<=1000。另有20%的数据，只有k=1的操作且Hi,Fi均为1。另有20%的数据，只有k=1或2的操作且Fi均为1。对于100%的数据，2<=n,m<=100000，0<=Hi,Fi<=10^9，1<=k<=3，k=1时1<=p,q<=n且p≠q，k=2或3时1<=p<=n且0<=q<=10^9。资源约定：峰值内存消耗 < 256MCPU消耗 < 5000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

第八届

T1 平方十位数

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

T2 生命游戏

康威生命游戏是英国数学家约翰·何顿·康威在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网格上推演，并非只有题目中画出的那点空间。当然，对于遥远的位置，其初始状态一概为死细胞。注意：需要提交的是一个整数，不要填写多余内容。

T3 树形显示

对于分类结构可以用树形来形象地表示。比如：文件系统就是典型的例子。树中的结点具有父子关系。我们在显示的时候，把子项向右缩进（用空格，不是tab），并添加必要的连接线，以使其层次关系更醒目。下面的代码就是为了这个目的的，请仔细阅读源码，并填写划线部分缺少的代码。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如有平字体对齐问题，可以参见图【p1.png】注意，只填写划线部分缺少的代码，不要抄写已有的代码或符号。

T4 小计算器

模拟程序型计算器，依次输入指令，可能包含的指令有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补充说明：1. n 值范围: 1<= n < 500002. 初始默认的进制是十进制资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

T5 填字母游戏

小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。并且：1. 轮到某人填的时候，只能在某个空格中填入L或O2. 谁先让字母组成了“LOL”的字样，谁获胜。3. 如果所有格子都填满了，仍无法组成LOL，则平局。小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。本题的输入格式为：第一行，数字n（n<10），表示下面有n个初始局面。接下来，n行，每行一个串，表示开始的局面。比如：“******”, 表示有6个空格。“L****”, 表示左边是一个字母L，它的右边是4个空格。要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。1 表示能赢-1 表示必输0 表示可以逼平例如，输入：4***L**LL**L***LL*****L则程序应该输出：0-111资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。## T6 区间移位数轴上有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。【输出格式】输出一个数字，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。【样例输入】210 50104980 9980【样例输出】20【样例说明】第一个区间往左移动10；第二个区间往右移动20。【样例输入】40 40003000 50005001 80007000 10000【样例输出】0.5【样例说明】第2个区间往右移0.5；第3个区间往左移0.5即可。【数据规模与约定】对于30%的评测用例，1 <= n <= 10；对于100%的评测用例，1 <= n <= 10000，0 <= ai < bi <= 10000。资源约定：峰值内存消耗 < 256MCPU消耗 < 2000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

第九届

T1

标题：三角形面积已知三角形三个顶点在直角坐标系下的坐标分别为：(2.3, 2.5)(6.4, 3.1)(5.1, 7.2)求该三角形的面积。注意，要提交的是一个小数形式表示的浮点数。要求精确到小数后3位，如不足3位，需要补零。

T2

标题：最大乘积把 1~9 这9个数字分成两组，中间插入乘号，有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。比如：984672 * 351 = 34561987298751 * 3462 = 3418759629 * 87146325 = 784316925...符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。（只提交乘积，不要提交整个算式）

T3 全排列

对于某个串，比如：“1234”，求它的所有全排列。并且要求这些全排列一定要按照字母的升序排列。对于“1234”，应该输出(一共4!=24行)：123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321下面是实现程序，请仔细分析程序逻辑，并填写划线部分缺少的代码。// 轮换前k个，再递归处理import java.util.*;public class A{static void permu(char[] data, int cur){if(cur==data.length-1){System.out.println(new String(data));return;}for(int i=cur; i<data.length; i++){char tmp = data[i]; for(int j=i-1; j>=cur; j--) data[j+1] = data[j];data[cur] = tmp;permu(data, cur+1);tmp = data[cur]; __________________________________________ ;data[i] = tmp;}}static void permu(String x){permu(x.toCharArray(),0);}public static void main(String[] args){permu("1234");}}请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。

T4 整理玩具

小明有一套玩具，一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中，每个小格子中恰好摆放一个部件。 每一个部件上标记有一个0~9的整数，有可能有多个部件标记相同的整数。 小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。如以下摆放是满足要求的：000220003344444 1224412244122330123456789以下摆放不满足要求：111221112233311111111122221122221111111111221111333333给出一种摆放方式，请你判断是否符合小明的要求。输入----输入包含多组数据。 第一行包含一个整数T，代表数据组数。 (1 <= T <= 10) 以下包含T组数据。 每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10) 以下包含N行M列的矩阵，代表摆放方式。 输出---对于每组数据，输出YES或者NO代表是否符合小明的要求。 【样例输入】3 3 5 000220003344444 3 5 1112211122333112 5 0123456789【样例输出】YESNOYES资源约定：峰值内存消耗（含虚拟机） < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。主类的名字必须是：Main，否则按无效代码处理。## T5标题：版本分支小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。现在这个项目的代码一共有N个版本，编号1~N，其中1号版本是最初的版本。除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。 如下图就是一个可能的版本树：1/ \2 3| / \5 4 6现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗？输入----第一行包含两个整数N和Q，代表版本总数和查询总数。 以下N-1行，每行包含2个整数u和v，代表版本u是版本v的直接父版本。 再之后Q行，每行包含2个整数x和y，代表询问版本x是不是版本y的祖先版本。 对于30%的数据，1 <= N <= 1000 1 <= Q <= 1000 对于100%的数据，1 <= N <= 100000 1 <= Q <= 100000 输出----对于每个询问，输出YES或NO代表x是否是y的祖先。 【样例输入】6 51 21 32 53 63 41 11 42 65 26 4【样例输出】YESYESNONONO资源约定：峰值内存消耗（含虚拟机） < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。主类的名字必须是：Main，否则按无效代码处理。

T6 防御力

小明最近在玩一款游戏。对游戏中的防御力很感兴趣。我们认为直接影响防御的参数为“防御性能”，记作d，而面板上有两个防御值A和B，与d成对数关系，A=2^d，B=3^d（注意任何时候上式都成立）。在游戏过程中，可能有一些道具把防御值A增加一个值，有另一些道具把防御值B增加一个值。现在小明身上有n1个道具增加A的值和n2个道具增加B的值，增加量已知。现在已知第i次使用的道具是增加A还是增加B的值，但具体使用那个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。初始时防御性能为0，即d=0，所以A=B=1。【输入格式】输入的第一行包含两个数n1,n2，空格分隔。第二行n1个数，表示增加A值的那些道具的增加量。第三行n2个数，表示增加B值的那些道具的增加量。第四行一个长度为n1+n2的字符串，由0和1组成，表示道具的使用顺序。0表示使用增加A值的道具，1表示使用增加B值的道具。输入数据保证恰好有n1个0，n2个1。【输出格式】对于每组数据，输出n1+n2+1行，前n1+n2行按顺序输出道具的使用情况，若使用增加A值的道具，输出Ax，x为道具在该类道具中的编号（从1开始）。若使用增加B值的道具则输出Bx。最后一行输出一个大写字母E。【样例输入1】1 242 8101【样例输出1】B2A1B1E【样例输入2】3 07 11 13000【样例输出2】A1A2A3E【样例说明】对于第一组测试数据，操作过程如下：操作 d A B初始 0 1 1B2 2 4 9A1 3 8 27B1 log3(29) 2^(log3(29)) 29可以证明，这个值是最大的。对于第二组测试数据，可见无论用什么顺序，A最后总为32，即d总为5，B总为243。 【数据规模】对于20%的数据，字符串长度<=10000；对于70%的数据，字符串长度<=200000；对于100%的数据，字符串长度<=2000000，输入的每个增加值不超过2^30。资源约定：峰值内存消耗（含虚拟机） < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。主类的名字必须是：Main，否则按无效代码处理。

第十届

试题 A: 递增序列

本题总分：5 分【问题描述】对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。例如，如下矩阵中LANNQIAO有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 个递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看是不同的顺序。对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAGSDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQFZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGABDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRLYVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKHZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBUXFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLRZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPGMHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPAVIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIFGWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJCEKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASKPEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWWCGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZPRWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGSPFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMRJNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECLYZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLPHBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLNDQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGFLXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYWCZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQIYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYIZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZBHGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKPFEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEASVJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJBMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSRRRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVYABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

52800

package 国赛第十届;import java.util.Scanner;public class T1 {/*VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAGSDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQFZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGABDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRLYVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKHZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBUXFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLRZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPGMHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPAVIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIFGWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJCEKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASKPEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWWCGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZPRWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGSPFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMRJNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECLYZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLPHBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLNDQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGFLXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYWCZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQIYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYIZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZBHGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKPFEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEASVJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJBMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSRRRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVYABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX*/public static char[][] arr;public static void main(String[] args) {Scanner in = new Scanner(System.in);//50int n = 30,m = 50;arr = new char[n][m];for(int i =0;i<n;i++ ) {arr[i] = in.next().toCharArray();}//for(int i =0;i<n;i++ ) {//for(int j =0;j<m;j++ ) {//System.out.print(arr[i][j]);//}//System.out.println();//}int ans = 0;for(int i =0;i<n;i++ ) {for(int j =0;j<m;j++ ) {for(int k = 0;k<n;k++) {for(int p = 0;p<m;p++) {if(i==k&&p == j) continue;if((k-i!=p-j)&&i!=k&&j!=p&&(k-i!=j-p)) continue;//System.out.println(i+""+j+""+k+""+p);ans += check(i,j,k,p);}}}}//System.out.println(ans);System.out.println(ans/2);}private static int check(int i, int j, int a, int b) {int ans = 0;if(a<i && b<j) {if(arr[a][b] < arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a<i&&b==j) {if(arr[a][b] < arr[i][j]){ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a<i&&b>j) {if(arr[a][b] != arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a ==i &&b<j) {if(arr[a][b] < arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a ==i&&b>j) {if(arr[a][b] > arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a >i&&b<j) {if(arr[a][b] != arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a >i&&b==j) {if(arr[a][b] > arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}else if(a >i&&b>j) {if(arr[a][b] > arr[i][j]) {ans ++;//System.out.println(arr[a][b] +" "+ arr[i][j]);}}return ans;//for(int a=-1;a<=1;a++) {//for(int b = -1;b<=1;b++) {//if(a==0&&b==0) continue;//if(i+a>=0&&i+a<2&&j+b>=0&&j+b<4) {////if(a ==-1&&b==-1) {//if(arr[i+a][j+b] != arr[i][i]) ans ++;////}else if(a ==-1&&b==0) {//if(arr[i+a][j+b] < arr[i][i]) ans ++;////}else if(a ==-1&&b==1) {//if(arr[i+a][j+b] != arr[i][i]) ans ++;////}else if(a ==0&&b==-1) {//if(arr[i+a][j+b] < arr[i][i]) ans ++;////}else if(a ==0&&b==1) {//if(arr[i+a][j+b] > arr[i][i]) ans ++;////}else if(a ==1&&b==-1) {//if(arr[i+a][j+b] != arr[i][i]) ans ++;////}else if(a ==1&&b==0) {//if(arr[i+a][j+b] > arr[i][i]) ans ++;////}else if(a ==1&&b==1) {//if(arr[i+a][j+b] > arr[i][i]) ans ++;//}////}//}////////}}}

试题 B: 平方拆分

本题总分：5 分【问题描述】将 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法？注意交换顺序视为同一种方法，例如 132 + 252 + 352 = 与 132 + 352 +252 = 视为同一种方法。【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 C: 切割

本题总分：10 分【问题描述】在 4 × 4 的方格矩阵中画一条直线。则直线穿过的方格集合有多少种不同的可能？这个里直线穿过一个方格当且仅当直线将该方格分割成面积都大于 0 的两部分。【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 D: 最优旅行

本题总分：10 分【问题描述】中国的高铁四通八达，乘坐方便，小明经常乘坐高铁在城市间旅游。现在，小明又有了一个长假，他打算继续乘坐高铁旅游。这次，他打算到下面的城市旅游。上海、广州、长沙、西安、杭州、济南、成都、南京、昆明、郑州、天津、太原、武汉、重庆、南昌、长春、沈阳、贵阳、福州。小明打算从北京出发，游览以上每个城市正好一次，最终回到北京。在每个城市（除北京外），小明都至少停留 24 小时。而当小明决定从一个城市去往另一个城市时，他只会选择有直接高铁连接的城市，不会在中途换乘转车。在试题目录下有一个文件 trip.txt 保存了小明可以选择的车次，小明不会选择其他车次。小明出发的时间是第 1 天的中午 12:00。请问，小明游览完以上城市正好一次，最终回到北京，最快需要多少分钟（请注意单位为分钟，请注意除北京外的城市需要至少停留 24 小时，即最少停留 1440 分钟）。【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 E: 序列求和

本题总分：15 分【问题描述】学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 S t 。例如 S 1 = 1, S 2 = 2, S 3 = 4, S 4 = 6，· · · 。现在小明想知道，前 60 个 S i 的和是多少？即 S 1 + S 2 + · · · + S 60 是多少？【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 F: 最长子序列

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分【问题描述】我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。给定两个字符串 S 和 T，请问 T 中从第一个字符开始最长连续多少个字符被 S 包含？【输入格式】输入两行，每行一个字符串。第一行的字符串为 S，第二行的字符串为 T。两个字符串均非空而且只包含大写英文字母。【输出格式】输出一个整数，表示答案。【样例输入】ABCDEABCDAABZ【样例输出】3【评测用例规模与约定】对于 20% 的评测用例，1 ≤ |T| ≤ |S | ≤ 20；对于 40% 的评测用例，1 ≤ |T| ≤ |S | ≤ 100；对于所有评测用例，1 ≤ |T| ≤ |S | ≤ 1000。

试题 G: 数正方形

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分【问题描述】在一个 N × N 的点阵上，取其中 4 个点恰好组成一个正方形的 4 个顶点，一共有多少种不同的取法？由于结果可能非常大，你只需要输出模 109 + 7 的余数。如上图所示的正方形都是合法的。【输入格式】输入包含一个整数 N。【输出格式】输出一个整数代表答案。【样例输入】4【样例输出】20试题 G: 数正方形 9第十届蓝桥杯大赛软件类决赛 Java 大学 B 组【数据规模与约定】对于所有评测用例，2 ≤ N ≤ 1000000。

试题 H: 大胖子走迷宫

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分【问题描述】小明是个大胖子，或者说是个大大胖子，如果说正常人占用 1 × 1 的面积，小明要占用 5 × 5 的面积。由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。朋友们设计了一个迷宫，迷宫可以看成是一个由 n × n 个方阵组成的方阵，正常人每次占用方阵中 1 × 1 的区域，而小明要占用 5 × 5 的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都有障碍物。为了方便小明，朋友们把迷宫的起点设置在了第 3 行第 3 列，终点设置在了第 n 2 行第 n 2 列。小明在时刻 0 出发，每单位时间可以向当前位置的上、下、左、右移动单位 1 的距离，也可以停留在原地不动。小明走迷宫走得很辛苦，如果他在迷宫里面待的时间很长，则由于消耗了很多脂肪，他会在时刻 k 变成一个胖子，只占用 3 × 3 的区域。如果待的时间更长，他会在时刻 2k 变成一个正常人，只占用 1 × 1 的区域。注意，当小明变瘦时迷宫的起点和终点不变。请问，小明最少多长时间能走到迷宫的终点。注意，小明走到终点时可能变瘦了也可能没有变瘦。【输入格式】输入的第一行包含两个整数 n, k。接下来 n 行，每行一个由 n 个字符组成的字符串，字符为 + 表示为空地，字符为 * 表示为阻碍物。试题 H: 大胖子走迷宫 11第十届蓝桥杯大赛软件类决赛 Java 大学 B 组【输出格式】输出一个整数，表示答案。【样例输入】9 5+++++++++++++++++++++++++++++++++++++++++++++***+*****+++++++++++++++++++++++++++【样例输出】16【评测用例规模与约定】对于 30% 的评测用例，1 ≤ n ≤ 50。对于 60% 的评测用例，1 ≤ n ≤ 100。对于所有评测用例，1 ≤ n ≤ 300，1 ≤ k ≤ 1000。

试题 I: 估计人数

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分【问题描述】给定一个 N × M 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。请你计算至少有多少人在矩阵上走过。【输入格式】输入第一行包含两个整数 N、M。以下 N 行每行包含 M 个整数 (0/1)，代表方格矩阵。【输出格式】输出一个整数代表答案。【样例输入】5 50010011111001001111100100【样例输出】3试题 I: 估计人数 13第十届蓝桥杯大赛软件类决赛 Java 大学 B 组【数据规模与约定】对于所有评测用例，1 ≤ N, M ≤ 20，标记为 1 的方格不超过 200 个。

试题 J: 分考场

时间限制: 10.0s 内存限制: 512.0MB 本题总分：25 分【问题背景】古语有云：春风得意马蹄疾，一日看尽长安花。当然在一场考试中所有人都春风得意马蹄疾是不可能的，尤其是碰到一些毒瘤出题人的时候。【问题描述】又到了每月一次的月考，又是 xf 老师出题。上一次 xf 老师出的题太毒瘤了，平均分只有 40 多，同学们都非常不满意，毕竟别的科的平均分都是 80 多。这次 xf 为了不被同学们寄刀片，想了一个办法：只公布所有考场的平均分的平均分。这样他就可以通过调整考场的分配方式，使得平均分显得高。（每个考场都可以容纳无限人）每次考试也不是所有同学都参加的，只有学号在 [l,r] 这个区间中的同学会参加。他想知道对于每次考试，他调整过考场后，所有考场的平均分的平均分的最大值。当然，同学们也可能会努力学习或整日颓废使成绩发生改变。【输入格式】输入的第一行包含一个整数 n。第二行包含 n 个整数，第 i 个数 vi，表示开始时每个同学的成绩。第三行包含一个整数 q，表示有 q 次操作。之后 q 行，每行描述一个操作，第一个数表示操作类型。如果操作为 1 p x，表示学号为 p 的同学分数变为 x。试题 J: 分考场 15第十届蓝桥杯大赛软件类决赛 Java 大学 B 组如果操作为 2 l r k, 表示把学号在 [l,r] 中的同学分成 k 个考场，求这 k 个考场的平均分的平均分的最大值。【输出格式】对于每个 2 操作输出一行，四舍五入保留正好 3 位小数。【样例输入】55 3 4 2 152 1 4 31 4 82 3 5 31 2 22 1 3 2【样例输出】3.8334.3334.000【样例说明】第一个操作询问学号在 [1, 4] 之间的同学分成 3 个考场的平均分的平均分的最大值，最优策略是：{1}, {2, 4}, {3}，平均分是51 +3+22 + 41 3 。第二个操作把学号为 4 的同学的分数变为 8。第三个操作询问学号在 [3, 5] 之间的同学分成 3 个考场的平均分的平均分的最大值，最优策略是：{3}, {4}, {5}。第四个操作把学号为 2 的同学分数变为 2。第五个操作询问学号在 [1, 3] 之间的同学分成 2 个考场的平均分的平均分的最大值，最优策略是：{1}, {2 3}。【评测用例规模与约定】对于全部评测用列，n ≤ 200000, q ≤ 200000, 任意时刻同学的分数 vi ≤ 109， k ≤ r l + 1。评测时将使用 10 个评测用例测试你的程序，每个评测用例的限制如下：评测用例编号 n ≤ q ≤ 特殊说明