蓝桥杯第六届国赛java

密文搜索
奇怪的数列
密文搜索
切开字符串

一、密文搜索

福尔摩斯从X星收到一份资料，全部是小写字母组成。他的助手提供了另一份资料：许多长度为8的密码列表。福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。

请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。

数据格式：输入第一行：一个字符串s，全部由小写字母组成，长度小于1024*1024 紧接着一行是一个整数n,表示以下有n行密码，1<=n<=1000 紧接着是n行字符串，都是小写字母组成，长度都为8

要求输出：一个整数, 表示每行密码的所有排列在s中匹配次数的总和。

例如：用户输入： aaaabbbbaabbcccc 2 aaaabbbb abcabccc

则程序应该输出： 4

这是因为：第一个密码匹配了3次，第二个密码匹配了1次，一共4次。

资源约定：峰值内存消耗（含虚拟机） < 512M CPU消耗 < 5000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

思路：根据题意，我们一开始的思路是求解每行密码c的所有排列方式，然后与总的密文s进行逐个比较，记录匹配成功的次数。

而这个题目的巧妙之处在于：正因为需要求每行密码的所有排列在s中匹配次数的总和，所以我们可以直接统计每行密码中所包含各字母的个数，与长度为8的s子区间的各字母的个数进行比较。而且由于密码c的长度固定为8，所以我们只需在s中截取长度为8的区间，进行比较即可。而s中这样的区间刚好有s.length()-7个。

例如: 1 2 3 4 5 6 7 8 9 10 s长度为10

则长度为8的区间只有<1-8> <2-9> ❤️-10>，一共是10-7=3个。

（既然都要求全排列，那么也就是所有的排列方式都有可能，那实际上只需要计算各字母的个数就可以了，这里可能有点绕，仔细理解一下）

完整代码如下：

import java.util.Scanner;

public class Main {
    static Scanner in = new Scanner(System.in);
    static String s;
    static String[] c = new String[1000];
    static int n;
    static int cnt = 0;
    public static void main(String[] args) {
        s = in.next();
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            String c = in.next();
            String x = sum(c);
            for (int j = 0; j < s.length()-7; j++) {
                String con = s.substring(j, j+8);
                if (x.equals(sum(con))) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
    /**
     * sum(String)函数用来求子串中的各字母个数，返回一个String
     * 思路：采用桶排序的排序方式，在记录下每个字母出现的次数时，这里注意由于比较的是字母，对应数组下标的的话是数字，要进行类似c.charAt(i)-'a'
     * 最后传出String方便比较，将int[]转换成String
     * */
    private static String sum(String c) {
        String result = "";
        int[] sum = new int[26];
        
        for (int i = 0; i <= c.length()-1; i++) {
            int index = c.charAt(i)-'a';
            sum[index]+=1;
        }
        /**
         * int[]->String
         * */
        for (int i = 0; i < sum.length; i++) {
            result += sum[i] + "";
        }
        return result;
    }
}

下面这种做法是借鉴的网上的，基本思路基本相同，区别在于下面这种方法是最后比较的是int[]，而非String，代码量不如博主的少。在比赛中尽量避免繁琐的思路，代码越精简越好。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
		int n;
		String str =  new String();
		String s = new String();
		int[][] a = new int[1005][26];
		int[] b = new int[26];
		
		str = in.next();
		for (int i = 0; i < str.length()-7; i++) {
			for (int j = i; j <= i+7; j++) {
				a[i][str.charAt(j)- 'a'] += 1;
			}
		}
		n = in.nextInt();
		int sum = 0;
		for (int k = 0; k < n; k++) {
			int flag = 0;
			for (int i = 0; i < b.length; i++) {
				b[i] = 0;
			}
			
			s = in.next();
			
			for (int i = 0; i < s.length(); i++) {
				b[s.charAt(i) - 'a'] += 1;
			}
			
			for (int i = 0; i < str.length()-7; i++) {
				flag = 1;
				for (int j = 0; j < 26; j++) {
					if (a[i][j] != b[j]) {
						flag = 0;
						break;
					}
				}
				if (flag == 1) {
				sum++;
				}
			}
		}
		System.out.println(sum);
	}
}

二。奇怪的数列

从X星截获一份电码，是一些数字，如下： 13 1113 3113 132113 1113122113 .... YY博士经彻夜研究，发现了规律：第一行的数字随便是什么，以后每一行都是对上一行“读出来” 比如第2行，是对第1行的描述，意思是：1个1，1个3，所以是：1113 第3行，意思是：3个1,1个3，所以是：3113 请你编写一个程序，可以从初始数字开始，连续进行这样的变换。

数据格式：第一行输入一个数字组成的串，不超过100位第二行，一个数字n，表示需要你连续变换多少次，n不超过20

输出一个串，表示最后一次变换完的结果。

例如：用户输出： 5 7 则程序应该输出： 13211321322115

资源约定：峰值内存消耗（含虚拟机） < 512M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

考察方向：字符串拼接，每次将计量数（初始为1，用于统计重复字符）与对应位的字符串拼接成新的字符串。

完整代码如下：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int cnt = 1;
		String str = in.next();
		int m = in.nextInt();
		while (m != 0) {
			
			String ss = "";
			for (int i = 0; i < str.length(); i++) {
				if (i+1 < str.length() && str.charAt(i) == str.charAt(i+1)) {
					cnt++;
					continue;
				}
				ss += cnt + "" + str.charAt(i) ;
				cnt = 1;
			}
			str = ss;
			m--;
		}
		System.out.println(str);
	}
}

递归解法：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner  in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        f(n+"", 0, m);
    }

    private static void f(String str, int num, int m) {
        if (num >= m) {
            System.out.println(str);
            return ;
        }
        StringBuffer   sb = new StringBuffer();
        int  cnt = 1 ;
        for (int i = 0; i < str.length()-1; i++) {
            if (str.charAt(i) != str.charAt(i+1)) {
                sb.append(cnt + "" + str.charAt(i));
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        sb.append(cnt + "" + str.charAt(str.length()-1));
        f(sb.toString(), num+1, m);
    }
}

三、表格计算

某次无聊中， atm 发现了一个很老的程序。这个程序的功能类似于 Excel ，它对一个表格进行操作。不妨设表格有 n 行，每行有 m 个格子。每个格子的内容可以是一个正整数，也可以是一个公式。公式包括三种：

SUM(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的和。
AVG(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的平均数。
STD(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的标准差。标准差即为方差的平方根。方差就是：每个数据与平均值的差的平方的平均值，用来衡量单个数据离开平均数的程度。

公式都不会出现嵌套。

如果这个格子内是一个数，则这个格子的值等于这个数，否则这个格子的值等于格子公式求值结果。输入这个表格后，程序会输出每个格子的值。atm 觉得这个程序很好玩，他也想实现一下这个程序。

「输入格式」第一行两个数 n, m 。接下来 n 行输入一个表格。每行 m 个由空格隔开的字符串，分别表示对应格子的内容。输入保证不会出现循环依赖的情况，即不会出现两个格子 a 和 b 使得 a 的值依赖 b 的值且 b 的值依赖 a 的值。

「输出格式」输出一个表格，共 n 行，每行 m 个保留两位小数的实数。数据保证不会有格子的值超过 1e6 。

「样例输入」 3 2 1 SUM(2,1:3,1) 2 AVG(1,1:1,2) SUM(1,1:2,1) STD(1,1:2,2)

「样例输出」 1.00 5.00 2.00 3.00 3.00 1.48

「数据范围」对于 30% 的数据，满足： n, m <= 5 对于 100% 的数据，满足： n, m <= 50

资源约定：峰值内存消耗（含虚拟机） < 512M CPU消耗 < 2000ms

思路：非常抱歉的是代码量不少，如果有人有更好的解法可以私信我。这个题目实际上思路非常清晰，分析每个单元格中的内容，如果出现SUM、AVG、STD则进行数据处理。而在进行数据处理的过程中，我们需要获取到其中的x1, x2, y2, y2才能继续进行（由于这四个值不仅仅是个位数的情况，这里采用s.indexOf()的方法找准位置，然后进行分割，其中两个“，”的划分，第一个“，”直接截取，第二个“，”先将第一个“，”截去，然后再二次截取）。获取到四个坐标之后，在求解表达式的过程中要判断类似sum中包含sum的情况，所以要递归调用func()函数。

完整代码如下：

import java.util.Scanner;

public class Main
{
	static String[][] str = new String[50][50];
	static double[][] d = new double[50][50];
	static int n, m;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				String c = in.next();
				str[i][j] = c;
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (str[i][j].charAt(0) < '0' || str[i][j].charAt(0) > '9') {
					d[i][j] = func(str[i][j], i, j);
				} else {
					d[i][j] = Double.valueOf(str[i][j]);
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < m; j++) {
				System.out.printf("%.2f ",d[i][j]);
			}
			System.out.printf("%.2f\n", d[i][m]);
		}
	}
	
	/**
	 * 这里必须采用函数的方式将这里包起来，因为有的sum处理里面还会包含sum，所以需要再次调用这里的函数。
	 * */
	private static double func(String string, int i, int j) {
		// TODO Auto-generated method stub
		int subce[] = sub(str[i][j]);
		if (str[i][j].substring(0, 3).equals("SUM")) {
			return sum(subce);
		} else if (str[i][j].substring(0, 3).equals("AVG")) {
			return avg(subce);
		} else if (str[i][j].substring(0, 3).equals("STD")) {
			return std(subce);
		} else {
			return -1;
		}
	}
	/**
	 * 三个表达式的计算都很简单
	 * 在求avg和std中，要有注意如何求四个坐标所围矩阵中单元格的个数，可以使用(x2-x1+1)*(y2-y1+1)，也可以直接计数
	 * 由于每个计算都有可能出现类似sum的计算中包含sum的情况，所以要进行判断，再次调用func()
	 * */
	private static double sum(int[] ce2) {
		// TODO Auto-generated method stub
		double cnt = 0.0;
		for (int i = ce2[1]; i <= ce2[3]; i++) {
			for (int j = ce2[2]; j <= ce2[4]; j++) {
				if (str[i][j].charAt(0) < '0' || str[i][j].charAt(0) > '9') {
					cnt += func(str[i][j], i, j);
				} else {
					cnt += Double.valueOf(str[i][j]);
				}
			}
		}
		return cnt;
	}
	
	private static double avg(int[] ce2) {
		// TODO Auto-generated method stub
		double cnt = 0.0;
		int q = 0;
		for (int i = ce2[1]; i <= ce2[3]; i++) {
			for (int j = ce2[2]; j <= ce2[4]; j++) {
				if (str[i][j].charAt(0) < '0' || str[i][j].charAt(0) > '9') {
					cnt += func(str[i][j], i, j);
				} else {
					cnt += Double.valueOf(str[i][j]);
				}
				q++;
			}
		}
		return cnt/q;
	}
	
	private static double std(int[] ce2) {
		// TODO Auto-generated method stub
		double cnt = 0.0;
		int q = 0;
		double x = avg(ce2);
		for (int i = ce2[1]; i <= ce2[3]; i++) {
			for (int j = ce2[2]; j <= ce2[4]; j++) {
				if (str[i][j].charAt(0) < '0' || str[i][j].charAt(0) > '9') {
					cnt += Math.pow(func(str[i][j], i, j) - x, 2);
				} else {
					cnt += Math.pow(Double.valueOf(str[i][j]) - x, 2);
				}
				q++;
			}
		}
		return Math.sqrt(cnt/q);
	}
	
	/***
	 * 下面是对表达式进行截取拆分获取x1,x2,y1,y2的过程
	 * 由于出现了两次",",所以在获取的过程中要注意，第二个","的获取可以先将前一个","连同之前的内容截去，然后再进行一次截取
	 * 	
	 */
	private static int[] sub(String s) {
		// TODO Auto-generated method stub
		int[] ce = new int[5];
		for (int i = 0; i < ce.length; i++) {
			ce[i] = 0;
		}
	
		int befKuohao = s.indexOf('(');
		int firstDouhao = s.indexOf(',');
		int maohao = s.indexOf(':');
		int secDouhao = s.substring((s.indexOf(',')+1)).indexOf(',') + (s.indexOf(',')+1);
		int aftKuohao = s.indexOf(')');
		ce[1] = Integer.valueOf(s.substring(befKuohao+1, firstDouhao));
		ce[2] = Integer.valueOf(s.substring(firstDouhao+1, maohao));
		ce[3] = Integer.valueOf(s.substring(maohao+1, secDouhao));
		ce[4] = Integer.valueOf(s.substring(secDouhao+1, aftKuohao));
		return ce;
	}
}

四、切开字符串

Pear有一个字符串，不过他希望把它切成两段。这是一个长度为N（<=10^5）的字符串。 Pear希望选择一个位置，把字符串不重复不遗漏地切成两段，长度分别是t和N-t（这两段都必须非空）。 Pear用如下方式评估切割的方案：定义“正回文子串”为：长度为奇数的回文子串。设切成的两段字符串中，前一段中有A个不相同的正回文子串，后一段中有B个不相同的非正回文子串，则该方案的得分为A*B。

注意，后一段中的B表示的是：“...非正回文...”，而不是: “...正回文...”。那么所有的切割方案中，A*B的最大值是多少呢？

【输入数据】输入第一行一个正整数N（<=10^5）接下来一行一个字符串，长度为N。该字符串仅包含小写英文字母。【输出数据】一行一个正整数，表示所求的A*B的最大值。【样例输入】 10 bbaaabcaba 【样例输出】 38 【数据范围】对于20%的数据，N<=100 对于40%的数据，N<=1000 对于100%的数据，N<=10^5

资源约定：峰值内存消耗（含虚拟机） < 512M CPU消耗 < 2000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。

思路：蓝桥杯有不少涉及字符串拆分的题目，思路都很清晰，但是实现起来也会有不少细节需要注意，这个题目虽然一开始不太能理解题意，但是我们至少知道需要求判断回文串这可就是下面代码中的huiwen()（当然题目中进一步要求了是长度为奇数的回文串），对于一个字符串来说，它的回文子串是很多的，所以我们还需要进行循环处理，这就是下面代码中的panduan()。另一方面，对于B的要求又有不同，我们很难求解出来非正回文串的个数，但是我们可以求出一个字符串全部的子串个数，这里对应quan()，再减去正回文串的个数，即可得到B。

完整代码如下：

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	static int n;
	static String str = new String();
	static int max = 0;
	static int A, B, C;
    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		str = in.next();
		for (int t = 1; t < n-1; t++) {
			A = panduan(str.substring(0, t));
			B = quan(str.substring(t, n)) - panduan(str.substring(t, n));
			if (max < A*B) {
				max = A*B;
			}
		}
		System.out.println(max);
	}
    /**
     * B的要求是找出 不相同的非正回文子串 这里采用曲线救国的方案，求出B的 全部不相同子串 的个数，减去B中 不相同的正回文子串 的个数
     * 
     * */
	private static int quan(String sub) {
		// TODO Auto-generated method stub
		Set<String> set = new HashSet<String>();
		for (int i = 1; i <= sub.length(); i++) {
			for (int start = 0; start <= sub.length()-i; start++) {
				String s = sub.substring(start, start+i);
				set.add(s);
			}
		}
		return set.size();
	}
	/**
	 * 对于一个字符串，查找其中包含的正回文串个数
	 * */
	private static int panduan(String sub) {
		// TODO Auto-generated method stub
		Set<String> set = new HashSet<String>();
		set.clear();
		for (int i = 1; i <= sub.length(); i+=2) {
			for (int start = 0; start <= sub.length()-i; start++) {
				String s = sub.substring(start, start+i);
				if (huiwen(s) == true) {
					set.add(s);
				}
			}
		}
		return set.size();
	}
	/**
	 * 判断回文
	 * */
	private static boolean huiwen(String s) {
		// TODO Auto-generated method stub
		for (int i = 0; i < s.length()/2; i++) {
			if (s.charAt(i) == s.charAt(s.length()-1-i)) {
				continue;
			} else {
				return false;
			}
		}
		return true;
	}
}

n.xuanrui

退无可退，一往无前

一、密文搜索

二。奇怪的数列

三、表格计算

四、切开字符串