# 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;
}
}
/*
*/
/*
*/
```