第一题：country leader
package googleJam; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.PrintStream; import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class CountryLeader { ArrayList<Character> list = new ArrayList<>(); public CountryLeader(Scanner in) { int T = in.nextInt(); for(int t=1;t<=T;t++){ int result=0; int index=0;//每次循环都要重新赋初值，那么就应该放在循环的开头 int n = in.nextInt(); String[] names = new String[n]; String dele = in.nextLine(); for(int i=0;i<n;i++){ names[i] = in.nextLine();//人名放在数组里 if(differLetter(names[i])>result){ index = i; result = differLetter(names[index]); }else if(differLetter(names[i])==result){ if(names[i].compareTo(names[index])<0){ index = i; result = differLetter(names[index]); } } } System.out.println("Case #"+t+": "+names[index]); } } public static void main(String[] args) throws Exception{ // TODO 自动生成的方法存根 String filename = "A-large-practice.in"; System.setIn(new FileInputStream(filename)); System.setOut(new PrintStream(new FileOutputStream("A-large-practice-out.txt"))); Scanner in = new Scanner(System.in); CountryLeader ex = new CountryLeader(in); in.close(); } public int differLetter(String str){ int count = 0; for(int i=0;i<str.length();i++){ if(!list.contains(str.charAt(i)) && (str.charAt(i)!=' ')){ list.add(str.charAt(i));//使用了26个额外的空间复杂度，但是常数级空间算O(1)还是O(N) count++; } } list.clear(); return count; } } 第二题：rain package googleJam; import googleJam.Rain2.Cell; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.PrintStream; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; //这道题循环遍历不是有网格来决定，而是由优先队列里的队首元素决定，每一个节点都可以先当做边界，不找低地，找最短边界储水 /* * @author Mingfang.z 在别人基础上自己修改的代码 * 思路：先将边界装入优先队列中（高度越小越优先），并标记为已访问。看队首元素四周未访问过的点， * 1、如果该点不比队首低，则将它加入队列，标记为已访问，即它变成了新的边界。 * 2、该点比队首低，意味着该点可以储水，更新res值，同时将它加入队列中，但是它的高度为原队首元素的高度，即以它为边界的点不能超过这个高度， * 同时将该点标记为已访问。 */ public class Rain { /** * @param args */ public Rain(Scanner in){ PriorityQueue<Grid> queue = new PriorityQueue<>(11,new Comparator<Grid>() { public int compare(Grid grid1, Grid grid2){ return grid1.h - grid2.h; } });//接口实现具体方法大括号后面要加分号 int T = in.nextInt(); for(int t=1;t<=T;t++){ int r = in.nextInt(); int c = in.nextInt(); int[][] h = new int[r][c]; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ h[i][j] = in.nextInt();//输入的原网格 if(i==0||i==r-1||j==0||j==c-1){ queue.add(new Grid(i, j, h[i][j]));//加入外围四条边,队列初始化 } } } boolean[][] visited = new boolean[r][c]; int wCount = 0;//记录储水值 while(!queue.isEmpty()){ Grid grid = queue.poll(); visited[grid.i][grid.j] = true; wCount += waterCount(h, visited, grid.i+1, grid.j, grid.h, queue); wCount += waterCount(h, visited, grid.i-1, grid.j, grid.h, queue); wCount += waterCount(h, visited, grid.i, grid.j-1, grid.h, queue); wCount += waterCount(h, visited, grid.i, grid.j+1, grid.h, queue); } System.out.println("Case #"+t+": "+wCount); } } /*对每一个优先队列里的最小边界节点计算周围储水值 * @param * curH是队首最小边界 * h[i][j]是四周遍历的节点 */ public int waterCount(int[][] h, boolean[][] vis, int i, int j, int curH, PriorityQueue<Grid> queue ){ if(i<0||i>=h.length||j<0||j>=h[0].length||vis[i][j]) return 0; else{ vis[i][j] = true;//判断该节点是否被访问 //curH = queue.poll().h; queue.add(new Grid(i, j, Math.max(curH, h[i][j]))); return Math.max(0, curH-h[i][j]); } } class Grid{//每一个网格的参数需要储存i，j，h int i, j, h; public Grid(int i, int j, int h){ this.i = i;//参数赋值给全局变量，实例变量是对象调用的需要this关键词 this.j = j; this.h = h; } } public static void main(String[] args) throws IOException { // TODO 自动生成的方法存根 String filename = "B-small-practice.in"; System.setIn(new FileInputStream(filename)); System.setOut(new PrintStream(new FileOutputStream("B-small-practice-out.txt"))); Scanner in = new Scanner(System.in); new Rain(in); in.close(); System.exit(0); } }第三题：jane's flower shop
花店这道题核心是理解题中给出的公式，找到公式规律。题中给出花店开了M月，和每个月的收入，以及刚开始的总成本，我们可以用一个int c[m+1]来储存，c[0]为总成本cost，其余为相对应每月的收入，这样有点好处就是，c[i]就是第i月的收入，索引不用减一。
然后写函数方程。很容易找到规律，题中方程为 -c[0]*(1+r)^m+c[1]*(1+r)^(m-1)+````+c[m-1]*(1+r)^1+c[m]*(1+r)^0 = 0；可以看出除了开头的cost部分，每月的收入都是c[i]*(1+r)^(m-i)，所以我们在计算函数值得时候，循环变量即为c数组的索引i，从1到m。注意，由于r的精度很高，所以此时必须使用大数计算BigDecimal函数，就是说每一次加减乘除都要先new BigDecimal对象，再用它的实例方法add（） multiply（），最后r的结果应该是double型，所以在查找r取值的时候，要以double型。
代码中的compute函数就是计算当IRR = r的时候根据方程所得函数值，返回的是一个bigdecimal的对象，其实我觉得也可以返回double或int型，提前判断是大于0还是小于0，单我看别人是用bigdecimal.compare去比较，所以也这么写了，可能精确一点吧，毕竟前面都是用它来计算。
然后是本题的核心部分，二分查找。拿到函数和自变量区间，我们首先应该去考虑它的特性（单调性，最值等），因为本题只有唯一解，所以图像与x轴只有一个交点，且F(-1)>0 因为方程末尾有常数项，所以得出函数单调递减。这样我们再二分查找的时候，当取得r值带进去算的函数值大于0，我们就知道要向右边移动，所以left =middle+0.000000000001，否则就是high = middle-0.000000000001。因为在二分查找的原型中，是用while（l<=r）来控制循环的，所以我们这里也可以借鉴过来，但是要想到，此时的left和right都是精确到小数点后12位的double型（根据题中给的测试用例可以得到），所以无法精确地比较两者大小，所以我们只需要控制他们的精度到小数点后12位就行了，其他的不用管，所以就是while（high-low>=0.000000000001）而当high和low在12位处相等时，我们选择显示两者中的任何一个当做r都可。
package googleJam; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.PrintStream; import java.math.BigDecimal; import java.util.Scanner; //此题不仅求解方程，对结果的精确度要求高，大数运算，因为small数据只是一次和二次方程，易求，可以先算出来 //java的输出数据格式要规定，format,数据输出精度只能大不能减，double>float public class JaneFlowerShop { /** * @param args */ JaneFlowerShop(Scanner in){ while(in.hasNext()){ int T = in.nextInt(); for(int t = 1;t<=T;t++){ int m = in.nextInt(); long[] c = new long[m+1]; for(int i=0;i<=m;i++){ c[i] = in.nextLong(); } System.out.println(String.format("Case #%d: %.12f", t,irr(c,m)));//格式化输出，保留double数据小数点后12位 } } } //计算参数r的函数值 public BigDecimal compute(long[] c,int m,double r){ BigDecimal r1 = new BigDecimal(1+r); BigDecimal res = new BigDecimal(c[0]).multiply(r1.pow(m)).negate();//初值,用的是bigdecimal的pow不是math的pow for(int i=1;i<=m;i++){ res = res.add(new BigDecimal(c[i]).multiply(r1.pow(m-i))); } return res; } //二分查找r在区间(-1,1)中，先用非递归,返回r public double irr(long[] c,int m){ double low = -1; double high = 1; while(high - low>=0.000000000001){//这只是控制了小数点后12位的精度，但如果high，low并不相等，到达小数点后13位且方程值仍不为0的话，就会跳出循环 double middle = (low+high)/2;//>>1只有int型有 BigDecimal value = compute(c,m,middle); if(value.compareTo(new BigDecimal(0.0))==0) return middle;//Double.valueOf(double d)是double的包装类，将基本类型转换为类的对象 else if(value.compareTo(new BigDecimal(0.0))>0){ low = middle + 0.000000000001;//因为在区间里，函数值value是逆序的 }else if(value.compareTo(new BigDecimal(0.0))<0){ high = middle - 0.000000000001; } } return low;//所以为了在控制的精度内返回r值，就当做当high和low相差小于1e-12时，当做两者相等，查找结束， } public static void main(String[] args) throws IOException { // TODO 自动生成的方法存根 String filename = "C-small-practice.in"; System.setIn(new FileInputStream(filename)); System.setOut(new PrintStream(new FileOutputStream("C-small-practice-out.txt"))); Scanner in = new Scanner(System.in); new JaneFlowerShop(in); in.close(); } }第四题：clash royale
这道题题意是：部落冲突是一款即时策略的卡牌游戏，现在需要制定一种策略，使得每次小家伙拿出的8张牌的总攻击力是最大的，在不超过自己拥有金币的前提下。
思路是借鉴别人的，才敢用暴力，当时在写的时候想到如果穷举，要写八个循环，吓怕了，后来看别人才知道其实还是能过的。
把八张卡牌分两次计算，前四张暴力穷举用list储存每一种组合所消耗的coins和产生的power，后四张同理。有说可以利用排序来删除无效数据，刚开始我想着也用优先队列来排，但是后来还要考虑筛选有效数据，就放弃了，因为毕竟我都已经用八个循环做了，不在乎这点了。
计算过程中需要加上一个条件，就是当四张牌消耗的coins总和超过了总的金币M，那这种组合就不用add了。
编写的时候，我们需要找到循环变量，因为这道题解答的是一种组合方案，而决定我每张牌不同组合的是它的level，也就是每张牌升级不同（等级不同），导致最后打别人的总攻击力不同。所以，计算时，我们的循环变量应该是每张牌的level，从L到K
下面只实现了small，别人的small都很短，我的写的太长，是奔着large去的，惭愧
代码中用了几个类来包装每张卡牌的coins和power，相比于用二维数组，觉得清晰一点
package googleJam; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.PrintStream; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; //这道题分两次暴力枚举，前四张牌和后四张牌，本来筛选后排序，可以删除掉无效数据，但是不会删，所以没有用queue //large的话，同样枚举，c（12,8）很小不影响，每次从12张中选出8张牌，计算每8张牌的resA power值并取最大（没写） public class ClashRoyale { /** * @param args */ //每一种方案的排序规则：coins从小到大排，当coins相同时，power从大到小排，都相同时无论先后（没有用到） PriorityQueue<Item> queue = new PriorityQueue<>(11,new Comparator<Item>() { public int compare(Item item1, Item item2){ if(item1.coins<item2.coins) return -1; else if(item1.coins>item2.coins) return 1; else{ if(item1.power>item2.power) return -1; else if(item1.power<item2.power) return 1; else return 0; } } });//接口实现具体方法大括号后面要加分号 List<Item> group1 = new ArrayList<>(); List<Item> group2 = new ArrayList<>();//前后四张牌的每种组合 ClashRoyale(Scanner in){ int T = in.nextInt(); for(int t=1;t<=T;t++){ int M = in.nextInt(); int N = in.nextInt(); long resA = 0;//储存最大power,每张牌最大power10^10,所以总的最大是8*10^10,为long型 //int resC = 0;//储存消耗coins List<Cards> list = new ArrayList<Cards>(8);//cards for(int i=0;i<N;i++){ int k = in.nextInt(); int l = in.nextInt(); int[] a = new int[k]; int[] c = new int[k-1]; for(int j=0;j<k;j++){ a[j] = in.nextInt(); } for(int z=0;z<k-1;z++){ c[z] = in.nextInt(); } list.add(new Cards(k, l, a, c)); } //前四张牌的穷举，计算coins和power int coinsi = 0;int coinsj = 0;int coinsm = 0;int coinsn = 0; for(int i=list.get(0).l;i<=list.get(0).k;i++){//用level变量循环 if(i==list.get(0).l) coinsi = 0; else coinsi += list.get(0).c[i-2]; /* for(int ii=0;ii<i-1;ii++){ coinsi += list.get(0).c[ii]; }*/ for(int j=list.get(1).l;j<=list.get(1).k;j++){ if(j==list.get(1).l) coinsj = 0; else coinsj += list.get(1).c[j-2]; for(int m=list.get(2).l;m<=list.get(2).k;m++){ if(m==list.get(2).l) coinsm = 0; else coinsm += list.get(2).c[m-2]; for(int n=list.get(3).l;n<=list.get(3).k;n++){ if(n==list.get(3).l) coinsn = 0; else coinsn += list.get(3).c[n-2]; if(coinsi+coinsj+coinsm+coinsn<=M) //queue.add(new Item(coinsi+coinsj+coinsm+coinsn, list.get(3).a[n-1]+list.get(2).a[m-1]+ // list.get(1).a[j-1]+list.get(0).a[i-1])); group1.add(new Item(coinsi+coinsj+coinsm+coinsn, list.get(3).a[n-1]+list.get(2).a[m-1]+ list.get(1).a[j-1]+list.get(0).a[i-1])); } } } } //后四张牌计算 int coinsi2 = 0;int coinsj2 = 0;int coinsm2 = 0;int coinsn2 = 0; for(int i2=list.get(4).l;i2<=list.get(4).k;i2++){ if(i2==list.get(4).l) coinsi2 = 0; else coinsi2 += list.get(4).c[i2-2]; for(int j2=list.get(5).l;j2<=list.get(5).k;j2++){ if(j2==list.get(5).l) coinsj2 = 0; else coinsj2 += list.get(5).c[j2-2]; for(int m2=list.get(6).l;m2<=list.get(6).k;m2++){ if(m2==list.get(6).l) coinsm2 = 0; else coinsm2 += list.get(6).c[m2-2]; for(int n2=list.get(7).l;n2<=list.get(7).k;n2++){ if(n2==list.get(7).l) coinsn2 = 0; else coinsn2 += list.get(7).c[n2-2]; if(coinsi2+coinsj2+coinsm2+coinsn2<=M) //queue2.add(new Item(coinsi2+coinsj2+coinsm2+coinsn2, list.get(7).a[n2-1]+list.get(6).a[m2-1]+ // list.get(5).a[j2-1]+list.get(4).a[i2-1])); group2.add(new Item(coinsi2+coinsj2+coinsm2+coinsn2, list.get(7).a[n2-1]+list.get(6).a[m2-1]+ list.get(5).a[j2-1]+list.get(4).a[i2-1])); } } } } //更新resA求最大power（暴力枚举，先不排序了） for(int z =0;z<group1.size(); z++){ for(int y=0;y<group2.size(); y++){ Item it1 = group1.get(z); Item it2 = group2.get(y); if(it1.coins+it2.coins<=M){ resA = Math.max(resA, it1.power+it2.power); } } } System.out.println("Case #"+t+": " + resA); group1.clear(); group2.clear(); } } public static void main(String[] args) throws IOException { // TODO 自动生成的方法存根 String filename = "D-small-practice.in"; System.setIn(new FileInputStream(filename)); System.setOut(new PrintStream(new FileOutputStream("D-small-practice-out.txt"))); Scanner in = new Scanner(System.in); new ClashRoyale(in); in.close(); } // i-th cards param class Cards{ int k,l; int[] a = new int[k];// each level power int[] c = new int[k-l];//upgrading each level coins Cards(int k,int l,int[] a,int[] c){ this.k = k; this.l = l; this.a = a; this.c = c; } } class Item{ int coins; int power; Item(int coins,int power){ this.coins = coins; this.power = power; } } }剩下的稍后写
如果有好的解答，欢迎分享
