海口市住房和城乡建设局网站市场推广方法
目录
一.拼正方形
1.题目
2.思路
3.代码
二.劲舞团
1.题目
2.思路
3.代码
三.数组诗意
1.题目
2.思路
3.代码
四.封闭图形个数
1.题目
2.思路
3.代码
五.吊坠
1.题目
六.商品库存管理
1.题目
2.思路
3.代码
七.挖矿
1.题目
2.思路
3.代码
八.回文字符串
1.题目
2.思路
3.代码
一.拼正方形
1.题目
2.思路
首先把1x1的方块转换为2x2的方块，然后算出所有的2x2的方块，只需要对这个值求根即可，因为数据过大，剩余的几个方块可以忽略不计，最后乘以2即可(因为方块边长为2)
3.代码
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);System.out.println(2717561*2);scan.close();}
}二.劲舞团
1.题目
2.思路
暴力枚举搜索即可，稍微有点麻烦的是数据处理，用一个二维的字符串数组来存储每条记录，在字符相等的前提下，找出时间相差1ms的连续数据的即可，需要注意的是k次正确敲击是k次连击，所以最后的结果需要加1
3.代码
public class text17 {public static void main(String[] args) {String[][] s = new String[10000][3];Scanner scan = new Scanner(System.in);int i = 0;while(scan.hasNextLine()){String p = scan.nextLine();if(p.isEmpty()) break;s[i++] = p.split(" ");}int max = 0;int sum = 0;for(int j = 1;j<2000;j++){long tmp = Long.valueOf(s[j-1][2]);if(s[j][0].equals(s[j][1])){long temp = Long.valueOf(s[j][2]);if(temp-tmp<=1000L){sum++;max = Math.max(sum,max);//这里的max实际上是k-1次连击continue;}}sum = 0;}System.out.println(max+1);scan.close();}
}
三.数组诗意
1.题目
2.思路
就是一道思维数学题，只有能找出规律就能写出来，找不到规律暴力求解只能通过30%，向这种大数据范围的数学题一般都有规律，我们先把满足题目要求的解小范围输出看看有没有什么规律，像这道题输出1000以内满足条件的数据就可以看出来只有是2的整数次幂的数字都不满足连续整数相加相等这个条件，所以只需要判断给的数据有多少个是2的整数次幂就可以
注:这里运用到了位运算，因为2的整数次幂的2进制表示只有一个1，x&(x-1)==0就是符合2的整数次幂的条件
eg:8 ->1000
7->0111
3.代码
public class Main {public static int res;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();long[] a = new long[n];for(int i = 0;i<n;i++){a[i] = scan.nextLong();if ((a[i] & (a[i] - 1)) == 0) {res++;}}System.out.println(res);scan.close();}
}四.封闭图形个数
1.题目
2.思路
本题就是考察排序，输入数据范围很大，用冒泡O(n*n)是肯定不能通过所有测试用例的，时间复杂度太高了，用Arrays提供的sort就可以(sort内部是快速排序O(nlogn))
先按照封闭个数排序，如果封闭个数相等就按数值排序
3.代码
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[] res = {1,0,0,0,1,0,1,0,2,1};//分别对应数字1-9的封闭空间个数//如果封闭空间个数相同,按数值大小比较int[][] a = new int[n][2];for(int i = 0;i<n;i++)a[i][0] = scan.nextInt();//思路:先按照封闭空间个数来排序，排序完再排数值大小for(int i = 0;i<n;i++){int tmp = a[i][0];int sum = 0;while(tmp>0){int cnt = tmp % 10;sum = sum + res[cnt];tmp = tmp / 10;}if(a[i][0]==0) a[i][1] = 1;elsea[i][1] = sum;//记录封闭个数}//已将全部数字的封闭个数处理完毕Arrays.sort(a,(o1,o2)->o1[1]==o2[1] ? Integer.compare(o1[0],o2[0]) : Integer.compare(o1[1],o2[1]));for(int i = 0;i<n;i++)System.out.print(a[i][0]+" ");scan.close();}
}五.吊坠
1.题目
最小生成树问题，不会写哈，没学过这个
六.商品库存管理
1.题目
2.思路
看到区间修改，就应该想到前缀和与差分，将时间复杂度优化到O(1)
前缀和：设置一个数组，数组每个元素保存的是该下标前所有元素的和，通过sum[i]-sum[i-1]
可以得到第i个元素的值
差分：设置一个数组，数组每一个元素是该当前下标与前一个下标元素的差值，当对数组区间进行操作用差分时间复杂度低，差分数组的前缀和就是数组的值
eg:给[l,r]区间所有的数加1
只需要对差分数组d[l]++，d[r+1]--，即可
因为本题数据很大，暴力解法只能通过部分用例
3.代码
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[] a = new int[n+1];int[] d = new int[n+2];int[][] k= new int[m+1][2];for(int i = 1;i<=m;i++){k[i][0] = scan.nextInt();k[i][1] = scan.nextInt();d[k[i][0]]++;d[k[i][1]+1]--;//更新差分数组//如果不设置差分数组:每次操作都需要遍历一次时间复杂度为(遍历次数+操作次数)}int[] sum = new int[n+1];sum[1] = d[1];for(int i = 2;i<=n;i++)sum[i] = sum[i-1] + d[i];//原数组int res1 = 0;for(int i = 1;i<=n;i++)if(sum[i]==0) res1++;for(int i = 1;i<=m;i++){int left = k[i][0];int right = k[i][1];int res2 = 0;for(int j = left;j<=right;j++){if(sum[j]==1)res2++;}System.out.println(res1+res2);}scan.close();}
}七.挖矿
1.题目
2.思路
贪心问题+前缀和，首先我们要能想到挖矿的时候最多回头一次，或者不回头，符合贪心思想
通过前缀和数组来查询走到i距离时有多少个矿洞，用两个数组分别表示正负轴，但不能把0下标矿洞存储进去，要不然会重复计算0下标(有回头的情况)
3.代码
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[] a1 = new int[1000001];int[] a2 = new int[1000001];int a0 = 0;for(int i = 0;i<n;i++){int cnt = scan.nextInt();if(cnt>0)a1[cnt]++;if(cnt<0)a2[-cnt]++;if(cnt==0)a0++;}int[] sum1 = new int[1000001];//前缀和数组int[] sum2 = new int[1000001];for(int i = 1;i<=1000000;i++){sum1[i] = sum1[i-1] + a1[i];sum2[i] = sum2[i-1] + a2[i];}int max = Math.max(sum1[m],sum2[m]);//一直向一个方向走for(int i = 1;i<=1000000;i++){if(m-2*i>0) {max = Math.max(max, sum1[i] + sum2[m - 2 * i]);//走到i位置处回头max = Math.max(max, sum2[i] + sum1[m - 2 * i]);}}if(a0==1) max++;System.out.println(max);}
}八.回文字符串
1.题目
2.思路
就是kmp匹配算法，暴力就行了，数据范围很小
3.代码
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();scan.nextLine();for(int k = 0;k<n;k++){char[] s = scan.nextLine().toCharArray();//首先判断是否是回文字符串int left = 0;int right = s.length-1;boolean tmp = false;while(left<=right){if(s[left]==s[right]){left++;right--;}else{if(s[left]=='l'||s[left]=='q'||s[left]=='b')left++;else if(s[right]=='l'||s[right]=='q'||s[right]=='b')right--;else{System.out.println("No");tmp = true;break;}}}if(tmp) continue;else System.out.println("Yes");}scan.close();}
}