# APCS 2022.6解法(?) ### P1 題目:給你三個數字(1~9),輸出出現的最多次數以及把他們不重複的從大到小輸出 解法:看你要bubble sort還怎樣,反正解法很簡單 ### P2 題目:好複雜晚點記得寫 解法:就把他逆回去,本來是從左右拿出來,用個deque維護,逆著放回去,至於那個交換在一次做完之後做,複雜度$O(NM)$ ### P3 題目:二維座標上,給你一堆斜45度的鏡子(座標範圍$3 \times 10^4$,$N\ 2.5 \times 10^5$),有一個從0,0向右($x$+)發射的光,問你他會反射幾次?保證不會無限一直彈 解法:用兩個vector分別裝同x y座標的所有鏡子,排序,我們就可以知道每個鏡子他上下左右是什麼,接著就暴力就好,$O(NlogN)$ ```java= import java.util.*; import java.time.*; import java.io.*; import java.math.*; public class Main { public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static long ret; public static int reti,rd,n,idx=1,u=1; public static boolean neg; public static final int mod=998244353; public static Useful us=new Useful(mod); public static void main(String[] args) throws Exception{ final int n=readint(); final int maxn=30005; final int max2=60010; final int max3=250005; int[] type=new int[max3]; int[][] be=new int[max3][4]; us.arr(be,-1); ArrayList<ArrayList<Pii>> sx=new ArrayList<>(); ArrayList<ArrayList<Pii>> sy=new ArrayList<>(); for(int i=0;i<maxn;i++)sx.add(new ArrayList<>()); for(int i=0;i<max2;i++)sy.add(new ArrayList<>()); int ix,iy,sz,ans=0; for(int i=0;i<n;i++) { ix=readint(); iy=readint()+maxn; sx.get(ix).add(new Pii(i,iy)); sy.get(iy).add(new Pii(i,ix)); type[i]=readint(); } ArrayList<Pii> po; for(int i=0;i<maxn;i++) { po=sx.get(i); sz=po.size(); if(sz<=1)continue; Collections.sort(po,new Comparator<Pii>() { public int compare(Pii f,Pii s) {return f.y-s.y;} }); be[po.get(0).x][1]=po.get(1).x; be[po.get(sz-1).x][0]=po.get(sz-2).x; for(int j=1;j<sz-1;j++) { be[po.get(j).x][1]=po.get(j+1).x; be[po.get(j).x][0]=po.get(j-1).x; } } int now=n,min=(1<<30),dir=3; for(int i=0;i<max2;i++) { po=sy.get(i); sz=po.size(); if(i==maxn) { for(Pii j:po) { if(j.y<min) { min=j.y; now=j.x; } } } if(sz<=1)continue; Collections.sort(po,new Comparator<Pii>() { public int compare(Pii f,Pii s) {return f.y-s.y;} }); be[po.get(0).x][3]=po.get(1).x; be[po.get(sz-1).x][2]=po.get(sz-2).x; for(int j=1;j<sz-1;j++) { be[po.get(j).x][3]=po.get(j+1).x; be[po.get(j).x][2]=po.get(j-1).x; } } if(now!=n) { ans++; if(type[now]==0) { dir^=2; } else { dir^=3; } } while(be[now][dir]!=-1) { now=be[now][dir]; ans++; if(type[now]==0) { dir^=2; } else { dir^=3; } } System.out.println(ans); } public static int readint() throws Exception{ reti=0; neg=false; while(rd<48||rd>57) { rd=br.read(); if(rd=='-') { neg=true; } } while(rd>47&&rd<58) { reti*=10; reti+=(rd&15); rd=br.read(); } if(neg)reti*=-1; return reti; } public static long readlong() throws Exception{ ret=0; neg=false; while(rd<48||rd>57) { rd=br.read(); if(rd=='-') { neg=true; } } while(rd>47&&rd<58) { ret*=10; ret+=(rd&15); rd=br.read(); } if(neg)ret*=-1; return ret; } } /* */ /* */ class Pii{ int x,y; long ans; Pii(int a,int b){ x=a; y=b; } } class Pll{ long x,y; Pll(long a,long b){ x=a; y=b; } } class Useful{ long mod; Useful(long m){mod=m;} void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}} void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}} void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}} void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}} void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}} void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}} void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}} void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}} void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}} long fast(long x,long pw) { if(pw<=0)return 1; if(pw==1)return x; long h=fast(x,pw>>1); if((pw&1)==0) { return h*h%mod; } return h*h%mod*x%mod; } int gcd(int a,int b) { if(a==0)return b; if(b==0)return a; return gcd(b,a%b); } long gcd(long a,long b) { if(a==0)return b; if(b==0)return a; return gcd(b,a%b); } long lcm(long a, long b){ return a*(b/gcd(a,b)); } double log2(int x) { return (Math.log(x)/Math.log(2)); } double log2(long x) { return (Math.log(x)/Math.log(2)); } } ``` ### P4 題目:a1,a2,a3,...,an ...w b1,b2,b3,...,bn ...x 可以變 an,a_{n-1},...,a1 ...y bn,b_{n-1},...,b1 ...z 請你從w,y跟x,z中選一個組合(例如w跟z),然後在兩個序列中找到任意一樣長的區段(>=1)然後兩兩相乘 解法:令$dp[i][j]$代表前$i,j$個能形成的最大和,注意答案可能是負的 $dp[i][j] = max(0,dp[i-1][j-1])+A_i \times B_j$ 也就是找到最大的$dp[i][j]$ 複雜度$O(NM)$ ```java= import java.util.*; import java.time.*; import java.io.*; import java.math.*; public class Main { public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static long ret; public static int reti,rd,n,idx=1,u=1; public static boolean neg; public static final int mod=998244353; public static void main(String[] args) throws Exception{ final int n=readint(); final int m=readint(); long ans=-(1<<30); long[][] dp00=new long[1005][1005]; long[][] dp01=new long[1005][1005]; long[] A=new long[1005]; long[] Ap=new long[1005]; long[] B=new long[1005]; long[] Bp=new long[1005]; for(int i=1;i<=n;i++) { A[i]=readint(); } for(int i=1;i<=n;i++) { Ap[i]=A[n-i+1]; } for(int i=1;i<=m;i++) { B[i]=readint(); } for(int i=1;i<=m;i++) { Bp[i]=B[m-i+1]; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { dp00[i][j]=Math.max(dp00[i-1][j-1],0)+A[i]*B[j]; ans=Math.max(dp00[i][j],ans); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { dp01[i][j]=Math.max(dp01[i-1][j-1],0)+A[i]*Bp[j]; ans=Math.max(dp01[i][j],ans); } } System.out.println(ans); } public static int readint() throws Exception{ reti=0; neg=false; while(rd<48||rd>57) { rd=br.read(); if(rd=='-') { neg=true; } } while(rd>47&&rd<58) { reti*=10; reti+=(rd&15); rd=br.read(); } if(neg)reti*=-1; return reti; } } /* */ /* */ ```