蓝桥杯练习系统算法训练习题加答案解析java版本.pdf

《蓝桥杯练习系统算法训练习题加答案解析java版本.pdf》由会员分享，可在线阅读，更多相关《蓝桥杯练习系统算法训练习题加答案解析java版本.pdf（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选试题蓝桥杯练习系统算法训练习题加答案解析java版本编 制：_审 核：_出 版：算法训练编号：A L G 0-1题目：区间k大数查询列关键字：排序查找类型：普通试题问题描述给定一个序列，每次询问序列中第1个数到第1个数中第K大的数是哪个。输入格式第一行包含一个数n,表示序列长度。第二行包含n个正整数，表示给定的序列。第三个包含一个正整数m,表示询问个数。接下来m行，每行三个数1,r,K,表示询问序列从左往右第1个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。输出格式总共输出m行，每行一个数，表示询问的答案。样例输入51 2 3 4 521 5 22 3 2样例输出42数据

2、规模与约定对于3 0%的数据，n,m =1 0 0；对 于1 0 0%的数据，n,m =1 0 0 0：保证k =(r-I+l),序列中的数=1 0 0 0 0 0 0。本题的J a v a参考代码如下：i m por t c l a s s M a i nprivate static BufferedlnputStream in=new BufferedInputStream;public static void main(String args)throws lOException(int nums=new intreadlnt();for(int i=0;i0;i)(int a=read

3、lnt();int b=readlnt();int c=readlnt();int tn=new intb-a+l;for(int j=0;j57);for(;(i&56)=48|(i&62)=56;i=()sum=sum*10+(i&15);return sum;编号：ALGO-2题目：最大最小公倍数关键字：贪心类型：普通试题问题描述已知一个正整数N,问从1N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公倍数。样例输入9样例输出504数据规模与约定1 =N=1000000o本题的Java参考代码如下：import class

4、 Mainpublic static void main(String args)Scanner sc=new Scanner;int n=();long anser=1;switch(n)case 95152:;public class Main public static void main(String|args)throws lOException BufferedReader bfr=new BufferedReader(new InputStreamReader);String s=().split(+H);int K=(s0);intL=(sl);int f=new intLK;

5、int i,j,k,sum=0;for(j=0;jl)(for(i=l;iL;i+)for(j=0;jK;j+)for(k=0;kK;k+)if(k!=j-l&k!=j+l)(fiU+=fi-lk;fij%=07;for(j=0;jK;j+)sum+=fL-lj;sum%=07;)编号：ALGO-4题目：节点选择关键字：树形动态规划类型：普通试题问题描述有一棵n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少输入格式第一行包含一个整数n。接下来的一行包含n 个正整数，第 i 个正整数代表点i 的权值。接下来一共n

6、-1 行，每行描述树上的一条边。输出格式输出一个整数，代表选出的点的权值和的最大值。样例输入51 23451 21 32425样例输出12样例说明选择3、4、5 号点，权值和为3+4+5=1 2。数据规模与约定对于20%的数据，n=20o对于50%的数据，n=1000对 于 100%的数据，n=100000,权值均为不超过1000的正整数。本题的Java参考代码如下：importimportpublic class Main final static int MAX_N=100010;xt)int v=Ei.v;if(visv)continue;Ed=true;statop+=v;visv=t

7、rue;)if(Ed)continue;-top;for(int i=headu;i+1 !=0;i=Ei.nxt)int v=Ei.v;dpv0+=(dpu0,dpul);dpvl+=dpu|0;)void run()throws lOException int n=();for(int i=1;i=n;+i)dpil=()；(head,-1);for(int i=1;i n;+i)int u=();int v=();add(u,v);add(v,u);)dfs(l,-1);int ans=(dpl0,dPll);(ans);0；public static void main(String

8、args)throws lOException new Main().run();)Main()cin=new InputReader;importclass Main(static int n,m;static int u;static int v;static int w;static int d;static int first;static int next;static Queue q=new LinkedList();static booleanf inq;public static void main(String args)throws lOException(int i;Bu

9、fferedReader bfr=new BufferedReader(new InputStreamReader);String str=();String s=(M sn);n=(s0);m=(sl);n+;m+;u=new intm;v=new intm;w=new intm;first=new intfn;next=new intm;d=new intn;inq=new booleann;for(i=l;in;i+)firsti=-l;fbr(i=l;im;i+)(str=();s=)；ui=(s0);vi=(sl);wi=(s2);nexti=firstui;firstui=i;sp

10、fa(l);for(i=2;in;i+)public static void spfa(int s)(int i,x；for(i=2;idx+wi)(dvi=dx+wi;if(!inqvi)(inqvi=true;(vi)；）编号：ALGO-6题目：安慰奶牛关键字：最小生成树类型：普通试题问题描述Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到 N o 每一个牧场都是一个奶牛的家。F J计划除去P 条道路中尽可能多的道路，但是还要保持牧场之间的连通性。你首先要决定那些道路是需要保留的N-1条道路。第 j 条双向道路连接了牧

11、场Sj和 Ej（l=Sj=N;1 =Ej=N;Sj!=Ej）,而且走完它需要L j的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i 个牧场的时候（即使你已经到过），你必须花去C i的时间和奶牛交谈。你每个晚上都会在同一个牧场（这是供你选择的）过夜，直到奶牛们都从悲伤中缓过神来。在早上起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。输入格式第 1行包含两个整数N 和 Po接下来N

12、行，每行包含一个整数Ci。接下来P 行，每行包含三个整数Sj,Ej和 Lj。输出格式输出一个整数，所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。样例输入571010206301 2523524 1234 1725 15356样例输出176数据规模与约定5=N=10000,N-l=P=100000,0=Lj=1000,1 =Ci=1,000。本题的Java参考代码如下：import Reader3 static BufferedReader reader;static SlringTokenizer tokenizer;static void init(InputStream in

13、put)reader=new BufferedReader(new InputStreamReader(input);tokenizer=new StringTokenizer(n);)static String next()throws IOExceptionwhile(!()tokenizer=new StringTokenizer()；return();static int nextlnt()throws IOExceptionreturn(next();)static double nextDouble()throws IOExceptionreturn(next();class Kr

14、uskalDuiint a,b,l;)public class Main/*param args*throws lOException*/static int father=new int 100000;static ArrayList path=new ArrayList();public static int getfather(int x)if(x!=fatherx)fatherx=getfather(fatherx);)return fatherx;)public static void _qst_w(inl l,int r)int i=l,j=r,mw=(i+j)/2).l;whil

15、e(i=j)while(i).lmw)j;if(i=j)(path,i,j);i+；j-；)if(lj)_qst_w(l,j);if(ir)_qst_w(i,r);)public static void main(String args)throws lOException fy=getfather(k).b);if(fx!=fy)fatherfx=fy;result+=(k).l;count+;)k+;)编号：ALGO-7题目：逆序对关键字：平衡二叉树类型：普通试题问题描述Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在

16、逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：有一颗2n-l个节点的二叉树，它有恰好n 个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a l-a n,现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。输入格

17、式第一行一个整数n。下面每行，一个数X。如果x=0,表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果xW0,表示这个节点是叶子节点，权值为X。输出格式输出一个整数，表示最少有多少逆序对。样例输入300312样例输出1数据规模与约定对于20%的数据，n=5000o对于 100%的数据，1 =n=200000,0=a i 2A31该题暂时没有人完全正确，暂时没有该语言的参考程序。编号：ALGO-8题目：操作格子关键字：线段树类型：普通试题问题描述有 n 个格子，从左到右放成一排，编号为1-n。共有m 次操作，有 3 种操作类型：1.修改一个格子的权值，2.求连续一段格子权值和，3

18、.求连续一段格子的最大值。对于每个2、3 操作输出你所求出的结果。输入格式第一行2 个整数n,mo接下来一行n 个整数表示n 个格子的初始权值。接下来m 行，每行3 个整数p,x,y,p 表示操作类型，p=l时表示修改格子x 的权值为y,p=2时表示求区间 x,y 内格子权值和，p=3时表示求区间 x,y 内格子最大的权值。输出格式有若干行，行数等于p=2或 3 的操作总数。每 行 1个整数，对应了每个p=2或 3 操作的结果。样例输入4312342 1 31433 1 4样例输出63数据规模与约定对于 20%的数据 n=100,m=200对于 50%的数据 n=5000,m=5000。对于

19、100%的数据 1 =n=100000,m=100000,0 =格子权值 =10000。本题的Java参考代码如下：importimportpublic class Main final static int MAX_N=100007;class Node int 1,r;int sum,max;Node()Node(int _1,int _r,int _s,int _m)1 =J；r=_r;sum=_s;max=_m;int n,m;Node tree=new NodeMAX_N 2;int a=new intMAX_N;void up(int id)treeid.sum=treeid l.

20、sum+treeid 1|l.sum;tree id,max=(treeid l.max,treeid 1|l.max);)void build(int id,int 1,int r)tree id=new Node。0,0);if(l=r)treeid.sum=treeid.max=al;return;int mid=(1+r)1;build(id 1,1,mid);build(id 1|1,mid+1,r);up(id);void update(int id,int pos,int val)if(treefid.1 =treeid.r)treeid.sum=treeid.max=val;r

21、eturn;int mid=(treeid.l+treeid.r)1;if(pos=mid)update(id 1,pos,val);else update(id 1|1,pos,val);up(id);)int sum(int id,int 1,int r)if(1=treeid.l&treeid.r=r)return treeid.sum;)int mid=(treeid.l+treeid.r)1;if(r mid)return sum(id 1|1,1,r);else return sum(id 1,1,mid)+sum(id 1|1,mid+1,r);int max(int id,in

22、t 1,int r)if(l=treeid.l&treeid.r=r)return treefid.max;)int mid=(treeid.l+treeid.r)1;if(r mid)return max(id 1|1,1,r);else return(max(id 1,1,mid),max(id 1|1,mid+1,r);)void run()throws lOException n=()；m 二 ()；for(int i=1;i=n;+i)ai=0；build(l,1,n);for(int i=0;i m;+i)int type=();inti=();int r=();if(type=1

23、)update(l,1,r);else if(type=2)(sum(l,lt r);else(max(l,1,r);0;)public static void main(String args)throws lOException new Main().run();Main()cin=new InputReader;序列中的所有数都是不大于k 的正整数；2.序列中至少有两个数。3.序列中的数两两不相等；4.如果第i-1个数比第i-2 个数大，则第i 个数比第i-2 个数小；如果第i-1个数比第i-2 个数小，则第i 个数比第i-2 个数大。比如，当 k=3 时，有下面几个这样的序列：1 21

24、 32 12 1 32323 13 132一共有8 种，给定k,请求出满足上面要求的序列的个数。输入格式输入包含了一个整数ko(k=20)输出格式输出一个整数，表示满足要求的序列个数。样例输入3样例输出本题的Java参考代码如下：import.*;public class Mainpublic static void main(String args)throws IOExceptionBufferedReader bf=new BufferedReader(new InputStreamReader);int n=();编号：ALGO-10题目：集合运算关键字：数组排序类型：vip问题描述给

25、出两个整数集合A、B,求出他们的交集、并集以及B 在 A 中的余集。输入格式第一行为一个整数n,表示集合A 中的元素个数。第二行有n 个互不相同的用空格隔开的整数，表示集合A 中的元素。第三行为一个整数m,表示集合B 中的元素个数。第四行有m 个互不相同的用空格隔开的整数，表示集合B 中的元素。集合中的所有元素均为int范围内的整数，n、m=1000输出格式第一行按从小到大的顺序输出A、B 交集中的所有元素。第二行按从小到大的顺序输出A、B 并集中的所有元素。第三行按从小到大的顺序输出B 在 A 中的余集中的所有元素。样例输入51 2 34552 4 6 8 10样例输出241 2 3 4 5

26、 6 8 101 35样例输入412343567样例输出1 2 3 4 5 6 71234本题的Java参考代码如下：importimport class Main public static void main(String args)throws lOException BufferedReader br=new BufferedReader(new InputStreamReader);int n=();int|arr=new intn;String st=().split();for(int a=0;a ;a+)arra=(sta);)(arr);int m=();int tag=ne

27、w int|m;String str=().split();for(int a=0;a ;a+)taga=(stra);)(tag);func(arr,tag);)public static void func(int arr,int tag)int x;for(int a=0;a=0)+)；)Set set=new HashSet();for(int a=0;a ;a+)(arra);)for(int a=0;a ;a+)(taga);)int sor=new inl();lterator it=();while()for(int a=0;a ;a+)sora=();)(sor);for(i

28、nt a=0;a ;a+)+);int y;for(int a=0;a ;a+)y=(tag,arrfa);if(y0)+)；编号：ALGO-11题目：瓷砖铺放关键字：递归类型：vip试题问题描述：有一长度为N(l=N=10)的地板，给定两种不同瓷砖：一种长度为1,另一种长度为2,数目不限。要将这个长度为N 的地板铺满，一共有多少种不同的铺法例如，长度为4 的地面一共有如下5 种铺法：4=1+1+1+14=2+1+14=1+2+14=1+1+24=2+2编程用递归的方法求解上述问题。输入格式只有一个数N,代表地板的长度输出格式输出一个数，代表所有不同的瓷砖铺放方法的总数样例输入4样例输出5参考

29、代码：import class Main(public static void main(String args)(Scanner input=new Scanner;int n=();if(l=n&n=10)if(n=l)(1);)elseint lagtagO=tagl=if(n=l)=new intlnl;for(inl a=2;an;a+)taga=taga-l+taga-2;编号：ALGO-12题目：累方分解关键字：递归类型：vip试题问题描述：任何一个正整数都可以用2的基次方表示。例如：137=27+23+20同时约定方次用括号来表示，即a b可表示为a(b)。由此可知，137可表

30、示为：2(7)+2(3)+2(0)进一步：7=22+2+20(21 用 2 表示)3=2+20所以最后137可表示为：2(2(2)+2+2(0)+2(2+2(0)+2(0)又如：1315=210+28+25+2+1所 以1315最后可表示为：2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)输入格式输入包含一个正整数N(N=20000),为要求分解的整数。输出格式程序输出包含一行字符串，为符合约定的n 的 0,2 表示(在表示中不能有空格)参考代码：import class Main public static void main(String args)t

31、hrows Exception BufferedReader br=new BufferedReader(new InputStreamReader);int number=();toString(number);)private static void toString(String binary)char temp=();boolean control=false;for(int i=0;i 1)toString(mi);”)”)；编号：ALGO-13题目：拦截导弹关键字：贪心动态规划类型：vip试题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺

32、陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。输入格式一行，为导弹依次飞来的高度输出格式两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数样例输入389 207 155 300 299 170 158 65样例输出62参考代码：importimportpublic class Main

33、public static void main(String args)throws IOExceptionBufferedReader bf=new BufferedReader(new InputStreamReader);String s=();String ss=(n n);int numa=new int;int numb=new int;int numc=new int;for(int i=0;i;i+)numai=(ssi);numbi=l;numci=l;)int al=;int a2=;for(int i=0;i;i+)for(intj=0;ji;j+)if(numainum

34、aj&numbinumbj+l)numbi=numbj+1;)al=(al,numbi);for(int i=0;i;i+)for(int j=O;jnumaj&numcinumcj+l)numci=numcj+l;)a2=(a2,numci);）编号：ALGO-14题目：回文数关键字：模拟高精度计算类型：vip试题问题描述：若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个10进制数5 6,将 56加 65（即把56从右向左读），得 到 121是一个回文数。又如：对 于 10进制数87：STEP1：87+78=165 STEP2：165+561=726

35、STEP3：726+627=1353 STEP4：1353+3531=4884在这里的一步是指进行了一次N 进制的加法，上例最少用了 4 步得到回文数4884。写一个程序，给定一个N（2=N 30)Impossible!);return;)long sum=a+b;String str=,H;while(sum=n)long tmp=sum%n;sum/=n;if(tmp=10)str=(char)(55+tmp)+str;elsestr=tmp+str;)if(sum=10)str=(char)(55+sum)+str;elsestr=sum+str;String reverse=new S

36、tringBuilder(str).reverse().toString();if(!(reverse)a=(str,n);b=(reverse,n);func(a,b);else“STEP二 +count);return;编号：ALGO-15题目：旅行家的预算关键字：贪心类型：vip试题问题描述：一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、福升汽油能行驶的距离D2、出发点每升汽油价格P 和沿途油站数N(N 可以为零)，油站i 离出发点的距离Di、每升汽油价格P i(i=l,2,N)。计算结果四舍五

37、入至小数点后两位。如果无法到达目的地，则输出 KNo Solution输入格式第一行为4 个实数D l、C、D2、P 与一个非负整数N；接下来N 行，每行两个实数Di、Pi。输出格式如果可以到达目的地，输出一个实数(四舍五入至小数点后两位)，表示最小费用；否则输出No Solution(不含引号)。样例输入2样例输出参考代码：import class Main)public static void main(String args)double p=new double1 10241024;Scanner sc=new Scanner;int i,j,k=0;double dl=();doub

38、le c=();double d2=();p O l =();i n t n =();n+;f or (i =1;i n;i+)p i 0 =()；p i l =()；)p n+0 =d l;d ou b l e f =c *d 2;f or (i =0;i f)“No S ol u t i on );r e t u r n;)d ou b l e m i n =0,m a x,d;f or (i =0;i 0)w h i l e (p i +l 0 -p k 0 -d =f)k+;f or (j =k;j =i;j+)i f(p r j l d)m a x =d;d -=m a x;m i

39、n +=m a x /d 2 *p k l ;)%.2 f,m i n);编号：ALGO-1 6题目：进制转化关键字：进制转化类型：v i p试题问题描述：我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置 的（值 减1 ）为指数，以1 0为底数的基之和的形式。例如：1 2 3可 表 示 为1*102+2*1 01+3*1 00这样的形式。与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的(值一1)为指数，以 2 为底数的幕之和的形式。一般说来，任何一个正整数R 或一个负整数一R 都可以被选来作为一个数制系统的基数。如果是以R或一R 为

40、基数，则需要用到的数 码 为 0,1.R 1。例如，当R=7 时，所需用到的数码是0,1,2,3,4,5 和 6,这与其是R 或一 R 无关。如果作为基数的数绝对值超过1 0,则为了表示这些数码,通常使用英文字母来表示那些大于9 的数码。例如对1 6 进制数来说，用A表 示 1 0,用 B表 示 1 1,用 C 表 示 1 2,用 D表 示 1 3,用 E 表 示 1 4,用 F 表 示 1 5。在负进制数中是用一 R 作为基数，例如一 1 5(十进制)相当于1 1 0 0 0 1 (2进制)，并且它可以被表示为2 的基级数的和数：1 1 0 0 0 1 =1 *(-2)5+1*(-2)4+0

41、*(-2)3+0*(-2)2+0*(-2)1 +1*(-2)0设计一个程序，读入一个十进制数和一个负进制数的基数，并将此十进制数转换为此负进制下的数：一RC -2,3,4,.,2 0)输入格式一行两个数，第一个是十进制数N(32768V=N V=3 2 7 6 7),第二个是负进制数的基数一 R。输出格式输出所求负进制数及其基数，若此基数超过1 0,则参照1 6 进制的方式处理。(格式参照样例)样例输入130000-2样例输出30000=0000(base-2)样例输入-20000-2样例输出-20000=000(base-2)样例输入28800-16样例输出28800=19180(base-

42、16)样例输入-25000-16样例输出-25000=7FB8(base-16)参考代码：import class Main public static void main(String args)Scanner scanner=new Scanner;int N=();int R=();char c=09ABCDEFGn.toCharArray();Strings1=N+”=；String s=,H,;while(N!=0)int t=N%R;if(t0)t=t-R;N=N/R+1;elseN=N/R;s=ct+s;+s+“(base”+R+)”)；)编号：ALGO-17题目：乘积最大关键字

43、：动态规划类型：Vip试题问题描述：今年是国际数学联盟确定的“2000世界数学年”，又恰逢我国着名数学家华罗庚先生诞辰 90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N 的数字串，要求选手使用K 个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：3 1 2,当 N=3,K=1时会有以下两种分法：3*12=3631*2=62这时，符合题目要求的结果是：31*2=

44、62现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。输入格式程序的输入共有两行：第一行共有2 个自然数N,K(6WNW40,1WKW6)第二行是一个长度为N 的数字串。输出格式输出所求得的最大乘积(一个自然数)。样例输入421231样例输出62参考代码：import class Main public static void main(String args)throws lOException StreamTokenizer st=new StreamTokenizer(newInputStreamReader);0；int N=(int);0；int K=(int);0；long

45、 M=(long);String str=(M);long dp=new longK+1N+1;for(int i=1;i=N;i+)dpOi=(O,i);)for(int i=1;i=K;i+)for(int j=1 +i;j=N;j+)for(int k=i;k=N;k+)int font=0;for(int 1 =k;I j;1+)font=(1)-0,+font*10;)if(dpijdpi-lk*font)dpij=dpi-lk*font;BufferedReader(new编号：ALGO-18题目：单词接龙关键字：搜索类型：vip试题问题描述：单词接龙是一个与我们经常玩的成语接龙相

46、类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次)，在两个单词相连时，其重合部分合为一部分，例 如 beast和 astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系，例如a t和 atide间不能相连。输入格式输入的第一行为一个单独的整数n(n=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表 示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.输出格式只需输出以此字母开头的最长的“龙”的长度样例输入5attouchcheatchooseta

47、cta样例输出23样例说明连成的 龙”为 atoucheatactactouchoose参考代码：import class Main private static String a=new String20;private static int b=new int|2Ol;private static ini max;private static int n;public static void main(String args)Scanner scanner=new Scanner;n=()；for(int i=0;i n;i+)ai=()；String string=();f(string

48、,();)private static void f(String s,int length)for(int i=0;i n;i+)if(ai.indexOf(s)=0&bi 2)int length 1 =();int length?=ai.length();bi+；int p=1;length=length+length2-length 1;while(p max length:max;编号：ALGO-19题目：方格取数关键字：动态规划类型：vip试题问题描述：设 有 N*N的方格图(N=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。某人从图的左上角的A 点(1,1

49、)出发，可以向下行走，也可以向右走，直到到达右下角的 B 点(N,N)。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。此人从A 点到B 点共走两次，试找出2 条这样的路径，使得取得的数之和为最大。输入格式输入的第一行为一个整数N(表示N*N的方格图)，接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0 表示输入结束。输出格式只需输出一个整数，表示2 条路径上取得的最大的和。样例输入823 1326635744 14522156463 157 2 14000样例输出67参考代码：import class Mainstatic int x;stat

50、ic int y;static int n;public static void main(String args)throws lOException)BufferedReader br=new BufferedReader(new InputStreamReader);n=()；int tag=new int2*n+12*n+1;int air=new intn*n2;out:for(int i=1;i+)String str=().split(n);for(int j=0;j l;j+)x=arri0=(strO);y=arril=(strl);tagxy=(str2);if(X =0&