# APCS 2024 Jan Java Solution
### 前言
因為大學了，就不去占名額(想當初搶得要死的)，我就沒去報名了。
### [P1 遊戲選角](https://zerojudge.tw/ShowProblem?problemid=m931)
這題可以開兩個陣列或一個 pair 陣列記起來，第一次記住整題最大值，再掃過第二次時候避開最大值的地方(因為題目保證相異)，記住第二大的是哪一個就可以了。 時間/空間複雜度 $O(N)$，另外用排序也可以，複雜度會爛一點但這題數據很小所以沒啥差別，只是也沒比較好寫。
附上~~精選~~ code: (管 Main() 就好，下面是模板)
```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,cnt;
public static int reti,rd,n,m,ans;
public static String[] in;
public static String in1="";
public static boolean neg,b1,b2,b3;
public static void main(String[] args) throws Exception{
final int n=readint(); // input
int mux=0,mux2=0,id=0; //mux = max, mux2 = 2nd max
int[] a=new int[n];
int[] b=new int[n];
for(int i=0;i<n;i++) {
a[i]=readint();
b[i]=readint();
mux=Math.max(mux, a[i]*a[i]+b[i]*b[i]);
}
for(int i=0;i<n;i++) {
int p=a[i]*a[i]+b[i]*b[i];
if(p!=mux&&p>mux2) {
mux2=p;
id=i;
}
}
outn(a[id]+" "+b[id]); //output
}
/*
*/
//fast io
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;
}
//fast typing
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(char in) {
System.out.println(in);
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(double in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(char in) {
System.out.print(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(double in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
public static void fl() {
System.out.flush();
}
public static String[] res() throws IOException{
return br.readLine().split(" ");
}
public static String re() throws IOException{
return br.readLine().split(" ")[0];
}
}
```
### [P2 蜜蜂觀察](https://zerojudge.tw/ShowProblem?problemid=m932)
六邊形的很難寫，但我們把它變成熟悉的形狀就好了。
這樣應該會比較好理解，而我們依照上面的定義可以用$(x,y)$的坐標系表示，把這題的向量 $\vec{v_0} = (1,0), \vec{v_1} = (0,1), \vec{v_2} = (1, 1)$ ，而對於 $i \geq 3$ 我們有 $\vec{v_{i}} = -\vec{v_{i-3}}$，也就是乘以 $-1$ 的 scalar 。再判斷邊界就可以了，時間/空間複雜度 $O(NM+K)$。
最後要判斷的話，因為字元沒很多種，要算他的貢獻的話直接開個 boolean 陣列記，最後再整個跑一次看哪些有走過就在答案 $+1$ 就可以了。
附上~~精選~~ code: (以下的 $x$ 方向為了方便寫跟上面的方向是相反的)
```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,cnt;
public static int reti,rd,n,m,ans;
public static String[] in;
public static String in1="";
public static boolean neg,b1,b2,b3;
public static void main(String[] args) throws Exception{
char[][] mp=new char[105][105];
in=res();
final int n=pint(in[0]);
final int m=pint(in[1]);
final int k=pint(in[2]);
for(int i=1;i<=n;i++) {
in=res();
for(int j=1;j<=m;j++) {
mp[i][j]=in[0].charAt(j-1); //honeycomb
}
}
boolean[] b=new boolean[100];
int x=n,y=1,nx=n,ny=1; //nx, ny = new_x, new_y
String S="";
in=res();
for(int i=0;i<k;i++) {
int d=pint(in[i]); //get movement
int c=1;
if(d>2) { // scalar *= -1
d-=3;
c=-1;
}
if(d==0) {
nx=x-c;
ny=y;
}
if(d==1) {
nx=x;
ny=y+c;
}
if(d==2) {
nx=x+c;
ny=y+c;
}
if(nx<=n&&ny<=m&&nx*ny>0) {
x=nx; //not out of bound
y=ny;
}
S+=mp[x][y];
b[mp[x][y]-'A']=true; //boolean
}
int ans=0;
for(boolean i:b) {
if(i) ans++;
}
outn(S);
outn(ans);
}
/*
*/
//fast io
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;
}
//fast typing
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(char in) {
System.out.println(in);
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(double in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(char in) {
System.out.print(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(double in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
public static void fl() {
System.out.flush();
}
public static String[] res() throws IOException{
return br.readLine().split(" ");
}
public static String re() throws IOException{
return br.readLine().split(" ")[0];
}
}
```
### [P3 邏輯電路](https://zerojudge.tw/ShowProblem?problemid=m933)
這題就是一個 $\text{bfs}$ 裸題，照題目的實作就可以了，定義一個 Queue 叫做 $Q$，一開始先把起點都丟進去，之後拜訪到中間節點(邏輯閘)，因為有一些節點的入 $deg = 2$，一邊到了之後另一邊可能還沒走到，所以對於 $deg = 2$ 要判斷兩邊都走過後才可以把它丟進 $Q$ 裡面，最深深度可以開一個陣列，定義 $dist(i)$ 走到 $i$ 時的最遠距離 (我們定義 $dist(x) = 0, 1 \leq x \leq p$)，那我們算出所有的 $dist(i)$ 後，把 $dist(x)\ (p+q+1 \leq x \leq p+q+r)$ 取最大值就會是題目所求，要注意題目沒保證全部的邏輯閘都接到終點，你取 $1 \leq x \leq p+q+r$ 會是錯的(有可能中間走到死路，但距離更長)，這題的測試資料便是如此，時間複雜度 $O(p+q+r+m)$。
code: (最下面那堆是模板)
```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,cnt;
public static int reti,rd,n,m,ans;
public static String[] in;
public static String in1="";
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=1000015;
public static Useful us=new Useful(mod);
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
int MAXN=60000;
final int p=readint();
final int q=readint();
final int r=readint();
final int m=readint();
int[] type=new int[MAXN];
int[] value=new int[MAXN];
int[] cnt=new int[MAXN];
int[] deg=new int[MAXN];
Queue<Integer> Q=new LinkedList<>();
for(int i=1;i<=p;i++) {
value[i]=readint();
Q.offer(i); // init queue
}
for(int i=p+1;i<=p+q;i++) {
type[i]=readint();
}
us.al(E,p+q+r+5); //init arraylist
for(int i=0;i<m;i++) {
E.get(readint()).add(readint()); // add direct edge
}
int o, ans=0;
while(!Q.isEmpty()) {
o=Q.poll();
for(int i:E.get(o)) {
if(i<=p+q) {
if(type[i]==4) { // not
value[i]=value[o]^1;
Q.offer(i);
}
else if(deg[i]==0) { //first, no queuing.
deg[i]=1;
value[i]=value[o];
}
else {
if(type[i]==1) value[i]&=value[o];
if(type[i]==2) value[i]|=value[o];
if(type[i]==3) value[i]^=value[o];
Q.offer(i);
}
}
else {
value[i]=value[o];
}
cnt[i]=Math.max(cnt[o]+1, cnt[i]); //cal dist
}
}
for(int i=p+q+1;i<=p+q+r;i++) {
ans=Math.max(cnt[i]-1, ans); //dist
}
bw.write(ans+"\n");
for(int i=p+q+1;i<=p+q+r;i++) {
bw.write(value[i]+" ");
}
bw.flush();
}
//fast io
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;
}
//fast typing
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(char in) {
System.out.println(in);
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(double in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(char in) {
System.out.print(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(double in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
public static void fl() {
System.out.flush();
}
public static String[] res() throws IOException{
return br.readLine().split(" ");
}
public static String re() throws IOException{
return br.readLine().split(" ")[0];
}
}
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 fastn(long x,long pw) {
if(pw==1)return x;
long h=fastn(x,pw>>1);
if((pw&1)==0) {
return h*h;
}
return h*h*x;
}
long fast(long x,long pw) {
if(x==0)return 1;
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;
}
long fast(long x,long pw,long mod) {
if(pw<=0)return 1;
if(pw==1)return x;
long h=fast(x,pw>>1,mod);
if((pw&1)==0) {
return h*h%mod;
}
return h*h%mod*x%mod;
}
long[][] mul(long[][] a,long[][] b){
long[][] c=new long[a.length][b[0].length];
for(int i=0;i<a.length;i++) {
for(int j=0;j<b[0].length;j++) {
for(int k=0;k<a[0].length;k++) {
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
}
}
return c;
}
long[][] mul(long[][] a,long[][] b,long mod){
long[][] c=new long[a.length][b[0].length];
for(int i=0;i<a.length;i++) {
for(int j=0;j<b[0].length;j++) {
for(int k=0;k<a[0].length;k++) {
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
}
}
return c;
}
long[][] fast(long[][] x,long pw){
if(pw==1)return x;
long[][] h=fast(x,pw>>1);
if((pw&1)==0) {
return mul(h,h);
}
else {
return mul(mul(h,h),x);
}
}
long[][] fast(long[][] x,long pw,long mod){
if(pw==1)return x;
long[][] h=fast(x,pw>>1,mod);
if((pw&1)==0) {
return mul(h,h,mod);
}
else {
return mul(mul(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(long x) {
return (Math.log(x)/Math.log(2));
}
double logx(long x,long y) {
return (Math.log(y)/Math.log(x));
}
}
```
### [P4 合併成本](https://zerojudge.tw/ShowProblem?problemid=m934)
定義 $dp(L,R)$ 代表合併區間 $[L,R]$ 成一個的答案，要合併兩個數，如以下範例的紅藍兩個要合併，因為他是在一條線上的，那其實我們可以把它想回拆解前的狀態。
會發現紅、藍、紅 $\cup$ 藍都是連續的，因為這個性質，那勢必答案可以表示成 $dp(L_{紅},R_{紅})+dp(L_{藍},R_{藍})+這兩塊合併的\ cost$。
具體的做法
以下的程式是用 dp-memorization 的方式，先呼叫 $dp(1,N)$，之後往下窮舉各個切法，切成 $[L,mid], [mid+1,R]$ 兩塊後繼續算，記得算過的要存入 $dp$ 陣列就不用重複算，時間複雜度 $O(N^3)$。另外維護前綴和可以做到 $O(1)$ 查詢兩塊各自的 weight，但其實除了前綴和也有別的做法可以做到整體複雜度相同的維護，只是比較麻煩。
Code:
```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,cnt;
public static int reti,rd,n,m,ans;
public static String[] in;
public static String in1="";
public static boolean neg,b1,b2,b3;
public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=1000015;
public static Useful us=new Useful(mod);
public static long[] Al=new long[105];
public static long[][] dp=new long[105][105];
public static long[] p=new long[105];
public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
public static void main(String[] args) throws Exception{
final int n=readint();
for(int i=1;i<=n;i++) {
Al[i]=readint();
p[i]=Al[i]+p[i-1]; //prefix sum
}
us.arr(dp, -1); // init dp with -1
outn(DP(1,n)); //calculate dp [1,N]
}
public static long DP(int l,int r) { //top down
if(dp[l][r]!=-1)return dp[l][r]; //if calculated, return
if(l==r)return 0; //base case
long ans=(1L<<60);
for(int i=l;i<r;i++) { // iterate all ways to divide l,r into 2 pieces.
ans=Math.min(DP(l,i)+DP(i+1,r)+Math.abs(p[r]-2*p[i]+p[l-1]), ans);
}
dp[l][r]=ans; //dp-memoization
return ans;
}
//fast io
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;
}
//fast typing
public static int pint(String in) {
return Integer.parseInt(in);
}
public static long plong(String in) {
return Long.parseLong(in);
}
public static void outn() {
System.out.println();
}
public static void outn(char in) {
System.out.println(in);
}
public static void outn(long in) {
System.out.println(in);
}
public static void outn(double in) {
System.out.println(in);
}
public static void outn(boolean in) {
System.out.println(in);
}
public static void outn(String in) {
System.out.println(in);
}
public static void out(char in) {
System.out.print(in);
}
public static void out(long in) {
System.out.print(in);
}
public static void out(double in) {
System.out.print(in);
}
public static void out(boolean in) {
System.out.print(in);
}
public static void out(String in) {
System.out.print(in);
}
public static void fl() {
System.out.flush();
}
public static String[] res() throws IOException{
return br.readLine().split(" ");
}
public static String re() throws IOException{
return br.readLine().split(" ")[0];
}
}
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 fastn(long x,long pw) {
if(pw==1)return x;
long h=fastn(x,pw>>1);
if((pw&1)==0) {
return h*h;
}
return h*h*x;
}
long fast(long x,long pw) {
if(x==0)return 1;
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;
}
long fast(long x,long pw,long mod) {
if(pw<=0)return 1;
if(pw==1)return x;
long h=fast(x,pw>>1,mod);
if((pw&1)==0) {
return h*h%mod;
}
return h*h%mod*x%mod;
}
long[][] mul(long[][] a,long[][] b){
long[][] c=new long[a.length][b[0].length];
for(int i=0;i<a.length;i++) {
for(int j=0;j<b[0].length;j++) {
for(int k=0;k<a[0].length;k++) {
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
}
}
return c;
}
long[][] mul(long[][] a,long[][] b,long mod){
long[][] c=new long[a.length][b[0].length];
for(int i=0;i<a.length;i++) {
for(int j=0;j<b[0].length;j++) {
for(int k=0;k<a[0].length;k++) {
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
}
}
return c;
}
long[][] fast(long[][] x,long pw){
if(pw==1)return x;
long[][] h=fast(x,pw>>1);
if((pw&1)==0) {
return mul(h,h);
}
else {
return mul(mul(h,h),x);
}
}
long[][] fast(long[][] x,long pw,long mod){
if(pw==1)return x;
long[][] h=fast(x,pw>>1,mod);
if((pw&1)==0) {
return mul(h,h,mod);
}
else {
return mul(mul(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(long x) {
return (Math.log(x)/Math.log(2));
}
double logx(long x,long y) {
return (Math.log(y)/Math.log(x));
}
}
```
Sign in with Wallet
Connect another wallet