A 逃離高塔

第一道填空題很簡單，根據題意跑一邊循環即可，一共是202個符合條件的數

    public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int ans=0;for(long i=0;i<=2025;i++){if((i*i*i)%10==3)ans++;}System.out.println(ans);}

需要注意的是循環變量要定義成long型，不然三次方會爆int，只會得到153個數字

B消失的藍寶

這題想了一會沒思路直接跳過了...

C電池分組

要將數組分成兩塊，并使它們的異或和相同，直接暴力求解是很繁瑣的

異或是同一個比特位上兩個數相同則為0，不同為1，要找出異或和相同的兩組數，假設已經找到這兩組數了，這個時候兩個異或和是相同的，對他們做異或運算結果是0

也就是說，假設a^b^c 和d^e是我們找到的兩組異或和相同的兩組數，那么(a^b^c)^(d^e)=0

而且異或運算滿足交換律，所以我們直接對輸入的所有數字做異或運算，看最后的結果如果為0就代表滿足題意

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int t=0;t=scanner.nextInt();int x=0;while((t--)>0){int n = scanner.nextInt();x=0;for(int i=0;i<n;i++){x^=scanner.nextInt();}if(x==0){System.out.println("YES");}else{System.out.println("NO");}}}
}

不過我在考場上第一時間沒有想到這個思路，我是后面回過頭來在看的這道題目，我觀察了一下題目，發現當某個比特位上出現1的個數為偶數時符合題意，為奇數時則不符合題意，所以我就統計所有數每個比特位上1的個數，如果某個比特位上1的個數為奇數則直接輸出NO，否則就是符合題意的，考完后仔細想了一下，也算是歪打正著做對了

當某個位上出現1的個數為偶數個時，這些1的異或和是0，和剩下的0在做異或結果也是0

當某個位上出現1的個數為奇數個時，這些1的異或和是1，和剩下的0在做異或結果為1，那么最后所有數的異或和絕不會為0

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int t=0;t=scanner.nextInt();int x=0;//存儲每個比特位上1的個數int[] bit=new int[32];int cnt=0;boolean istrue=true;while((t--)>0){int n = scanner.nextInt();istrue=true;//清空上次結果for(int i=0;i<32;i++){bit[i]=0;}for(int i=0;i<n;i++){cnt=0;x=scanner.nextInt();while(x>0){if((x&1)>0){bit[cnt]++;}x>>=1;cnt++;}}for(int i=0;i<32;i++){if(bit[i]%2==1){istrue=false;}}if(istrue){System.out.println("YES");}else{System.out.println("NO");}}}}

D魔法科考試

?這題沒想到太好的思路，直接提前做了一個素數篩，然后兩層循環暴力求解，只能過60%測試用例

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//素數篩boolean[] isz=new boolean[40010];isz[1]=true;for(int i=2;i*i<=40001;i++){if(!isz[i]){for(int j=i+i;j<=40001;j+=i){isz[j]=true;}}}int n=scanner.nextInt();int m=scanner.nextInt();int[] a=new int[n];int[] b=new int[m];for(int i=0;i<n;i++){a[i]=scanner.nextInt();}for(int i=0;i<m;i++){b[i]=scanner.nextInt();}int s=0,sum=n+m,ans=0;boolean[] vis=new boolean[sum+1];for(int i=0;i<n;i++){for(int j=0;j<m;j++){s=a[i]+b[j];if(s<=sum&&!isz[s]&&!vis[s]){ans++;vis[s]=true;}}}System.out.println(ans);}
}

E爆破

?剛開始看見又是圓心又是半徑的，直接就跳過了，看完后面回過頭來發現這就是一個最小生成樹

直接暴力選邊是不可取的，時間復雜度高不說，無法保證每個圓都連通，題目提到如果兩個魔法陣相交，可以一起引爆，可以自己選擇連邊讓孤立的圓與其他圓連接，當時就直接想到了最小生成樹

注意，題目中所說兩個魔法陣相交的意思是圓心之間的距離小于等于半徑之和

解題思路是，將坐標系當作一個圖，我們將每個圓當作圖中的一個點，以輸入的下標當作圓的編號，開始時假設每個圓與其他所有圓都有一個無向邊，邊長是兩圓心之間的距離減去半徑之和，也就是想讓這兩個圓相交的最小代價，假設一共n個圓，那么就有n*(n-1)/2條邊，存進數組中根據邊長排序，后面利用并查集從小到大選邊

相交的兩個圓的邊長是負數，在處理時不用計入答案，標記后直接跳過就好

import java.util.*;public class Main {public static class edge{private int x;private int y;private double r;public edge(int x, int y, double r){this.x = x;this.y = y;this.r = r;}}private static int[] father;private static int n,m;//初始化public static void init(){father = new int[n+1];for(int i=0;i<father.length;i++){father[i] = i;}}//查找父節點，同時更新父節點信息public static int find(int x){return father[x]==x?x:(father[x]=find(father[x]));}public static double kruskal(edge[] edges){//初始化父親數組init();double ans=0;int fx=0,fy=0;for(edge e:edges){fx=find(e.x);fy=find(e.y);if(fx!=fy){father[fx]=fy;//大于0時計入答案if(e.r>0){ans+=e.r;}}}return ans;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m=n*(n-1)/2;int cnt=0;int[] x = new int[n];int[] y = new int[n];int[] r = new int[n];edge[] edges = new edge[m];for(int i=0;i<n;i++){x[i] = scanner.nextInt();y[i] = scanner.nextInt();r[i] = scanner.nextInt();}double line=0;int lx=0,ly=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){lx=x[i]-x[j];ly=y[i]-y[j];line=Math.sqrt((lx*lx)+(ly*ly))-r[i]-r[j];edges[cnt]=new edge(i,j,line);cnt++;}}//按邊的長度從小到大排序Arrays.sort(edges,new Comparator<edge>(){public int compare(edge e1, edge e2) {double x=e1.r-e2.r;if(x<0) return -1;if(x>0) return 1;return 0;}});double ans=kruskal(edges);System.out.printf("%.2f",ans);}
}

剩下的三題不確定思路是否正確，等后面我研究一下再發