郑州工商算法比赛java版本

C

图书馆有一堆图书，为了方便查找每本书都有自己的编号。

小明是图书馆的常客，现在图书馆将小明一年的借书都提取出来了，不过由于系统故障导致图书编号发生了重叠。

现在求助于你，请问小明借的书中出现最多的书的次数和编号。

第一行一个数表示图书馆馆藏n n<200

接下来的n行每行一个图书的编号只包含大小写字母且不长于80

最后一行小明写的编号只包含大小写字母，长度小于1000000

这道题我觉得是KMP算法，但是我忘记模板了，然后用暴力跑分，没跑出来...老师说是用trie，等大神

D

现在有个神奇的湖，

如果将BAA的B端碰触水面则字符串会增长为AABBAA

如果将BBA的A端碰触水面则字符串会增长为BBAABB

现在给出一个字符串请输出此字符串碰触湖水前的最小长度。

（一个字符串可 *** 作多次或者不 *** 作）

一个用A和B组成的字符串 长度<100000

仔细看题目，很容易想到二分法，然后再套一个逆转字符串，秒杀，上代码。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class {
	static String S;
	public static void main(String[] args) throws IOException {
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
		in.nextToken();
		S=in.sval;
//		System.out.println(S.substring(0,3+1));
//		System.out.println(S.substring(3+1,8));
		System.out.println(erfen());
		
	}
		public static int erfen(){
	        int left = 0;
	        int right = S.length()-1; 
	        while (left <= right) {
	            int middle = (left+right)/2;
	            if(S.substring(0,middle+1).equals(nizhuan(S.substring(middle+1,right+1)))){
	            	//继续判断,直接选择左边
	            	right=middle;
	            }else{
	            	return right-left+1;//没办法继续分了
	            }
	        }
	        return -1;
	    }
		static public String nizhuan(String sss){
			StringBuffer sb=new StringBuffer(sss);
			return sb.reverse().toString();
		}
	}

E

有一个游戏会给出如下数据

4

0 0 0 0

0 1 1 1

0 1 0 1

0 1 1 1

将被封死的0变为2

0 0 0 0

0 1 1 1

0 1 2 1

0 1 1 1

n<31

提示（每组只会有一个满足的闭合的多边形）

思路:DFS，把所有的封闭图形外边的点过一遍标记一下，里面的点到达不了的就是我们要求的点，上代码。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class M {
	static int [][]G;
	static int N;
	public static void main(String[] args) throws IOException {
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
		in.nextToken();
		N=(int)in.nval;
		G=new int[N][N];
		for(int i=0;i=N || j>=N) {
	           return;
	        }
	        if (G[i][j] == 1||G[i][j] ==9) {
	            return;
	        }
	        G[i][j] = 9;
	        dfs(i - 1, j);
	        dfs(i + 1, j);
	        dfs(i, j - 1);
	        dfs(i, j + 1);
	    }
	}

在路上设置了 n 个驿站1,2,⋯,n。行人可在这些驿站租用马车，并在之后的任何一个驿站归还马车。驿站 i 到驿站 j 之间的租金为 r(i,j)（1≤i 输入格式

第一行中有一个正整数 n，表示有 n 个驿站。接下来的 n−1 行是一个半矩阵 r(i,j)（1≤i

思路:迪杰斯特拉算法套用一下，秒杀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class {
	static int n;
	static int G[][];
	static int dis[];
	static boolean vis[];
	public static void main(String[] args) throws IOException {
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
		in.nextToken();
		n=(int)in.nval;
		G=new int[n+2][n+2];
		dis=new int[n+1];
		vis=new boolean[n+1];
		for(int i=1;i