目錄

一.拼正方形

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();}
}