---
# System prepended metadata

title: APCS 2022 6/13
tags: [Coding]

---

---
tags: Coding
---
# APCS 2022 6/13
## P1 數字遊戲
https://zerojudge.tw/ShowProblem?problemid=i399
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
using namespace std;
int main () {
    vector<int> A(3);
    for(int i=0;i<3;i++)cin>>A[i];
    sort(all(A),[](int a,int b){return a>b;});
    int a=1,b=1;
    bool c=true;
    for(int i=1;i<3;i++){
        if(A[i]==A[i-1]&&c)a++;
        else c=false;
        if(A[i]==A[i-1]&&!c)b++;
        if(max(a,b)==b){
            a=b;
            b=1;
            c=true;
        }
    }
    A.erase(unique(all(A)),A.end());
    cout<<a<<" ";
    for(auto i:A)cout<<i<<" ";
    return 0;
}
```
:::
## P2 字串密碼
https://zerojudge.tw/ShowProblem?problemid=i400
### 字元陣列版
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    int m,n;
    while(cin>>m>>n){
        char E[105][105],tran[300],str[105];
        int cnt[105]={0};
        string s;
        for(int i=0;i<m;i++){
            cin>>s;
            for(int j=0;j<n;j++){
                E[i][j]=s[j];
                cnt[i]+=s[j]-48;//0的ascii是48
            }
        }
        cin>>s;
        for(int i=0;i<n;i++){
            str[i]=s[i];
        }
        for(int i=m-1;i>=0;i--){
            int f=150;
            int b=151;
            for(int j=n-1;j>=0;j--){
                if(E[i][j]=='0'){
                    tran[f]=str[j];
                    f--;
                }
                if(E[i][j]=='1'){
                    tran[b]=str[j];
                    b++;
                }
            }
            f++;
            b--;
            if(cnt[i]%2==1){
                if(n%2){
                    for(int k=f;k<(n/2+f);k++){
                        swap(tran[k],tran[k+n/2+1]);
                    }
                }
                if(n%2==0){
                    for(int k=f;k<(n/2+f);k++){
                        swap(tran[k],tran[k+n/2]);
                    }
                }
            }
            for(int k=f,i=0;k!=b+1;k++,i++){
                    str[i]=tran[k];
            }
        }
        for(int i=0;i<n;i++) cout<<str[i];
    }
    return 0;
}
```
:::
### string版
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int m,n;
  vector<string> pasw;
  while(cin>>m>>n){
    string str,trans;
    int cnt=0;
    for(int i=0;i<m;i++){
      string s;
      cin>>s;
      pasw.push_back(s);
    }
    cin>>str;
    for(int i=m-1;i>=0;i--){
      cnt=0;
      trans="";
      for(int k=n-1;k>=0;k--){
        if(pasw[i][k]=='1'){
          trans.append(str,k,1);
          cnt++;
        }
        if(pasw[i][k]=='0'){
          trans.insert(0,str,k,1);
        }
      }
      if(cnt%2){
        if(n%2){
          trans=trans.substr(n/2+1,n/2)+trans.substr(n/2,1)+trans.substr(0,n/2);
        }
        if(!(n%2)){
          trans=trans.substr(n/2,n/2)+trans.substr(0,n/2);
        }
      }
      str=trans;
    }
    cout<<str;
  }
}
```
:::
## P3 雷射測試
https://zerojudge.tw/ShowProblem?problemid=i401
### 想法一 failed(tle):
抓一隻螞蟻慢慢爬每爬一格，都用二分搜檢查是否與鏡子重疊。
但時間複雜度太久
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define N 20050
#define all(a) a.begin(),a.end()
using namespace std;
struct pos{
    int x,y,t;
};
void debug(vector<pos>&a){
    for(auto i:a){
        cout<<i.x<<" "<<i.y<<" "<<i.t<<endl;
    }
}
bool cmp(const pos &a,const pos &b){
    if(a.x == b.x && a.y == b.y)return a.t<b.t;
    else if(a.x == b.x)return a.y<b.y;
    else return a.x<b.x;
}
int main () {
    int m;
    while(cin>>m){
        vector<pos> P;
        int X=0,Y=0;
        int dx=1,dy=0;
        int R=0,L=0,T=0,B=0;//right,left,top,bottom
        int cnt=0;
        for(int i=0;i<m;i++){
            pos k;
            cin>>k.x>>k.y>>k.t;
            R=max(k.x,R);
            T=max(k.y,T);
            B=min(k.y,B);
            P.push_back(k);
        }//P是所有鏡子的座標
        sort(all(P),cmp);
        while(1){
            X+=dx;
            Y+=dy;
            pos p1={X,Y,0};
            pos p2={X,Y,1};
            if(X<L || X>R || Y>T || T<B)break;
            if(binary_search(all(P),p1,cmp)){// mirror / //
                cnt++;
                if(dx==1 && dy==0){
                    dx=0;
                    dy=1;
                }else if(dx==0 && dy==1){
                    dx=1;
                    dy=0;
                }else if(dx==-1 && dy==0){
                    dx=0;
                    dy=-1;
                }else if(dx==0 && dy==-1){
                    dx=-1;
                    dy=0;
                }
            }else if(binary_search(all(P),p2,cmp)){// mirror \ //
                cnt++;
                if(dx==1 && dy==0){
                    dx=0;
                    dy=-1;
                }else if(dx==0 && dy==1){
                    dx=-1;
                    dy=0;
                }else if(dx==-1 && dy==0){
                    dx=0;
                    dy=1;
                }else if(dx==0 && dy==-1){
                    dx=1;
                    dy=0;
                }
            }
        }
        cout<<cnt;
    }
    return 0;
}
```
:::
### 想法二(sucess):
https://www.youtube.com/watch?v=ZDoEDTR6ftI
參考吳邦一教授，幫每隔鏡子找鄰居。
**找南北鄰居方式**: 座標先依照x由小到大當遇到兩個x座標一樣，就看y座標，y小的在南邊，y大的在北邊，接著用二維陣列nb[N][4]代表每個鏡子四個方向鄰居座標，存對方的id(for讀進的順序)。找東西鄰居依此類推。
**模擬**: 一開始方向往東，然後遇到的第一個鏡子一定會在y=0。接下來用一個二維陣列mir[2][4]代表折射後轉向的方向。方向轉完後在看下一個方向有沒有鏡子，沒有則是-1。
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define N 250010
#define east 0
#define south 1
#define west 2
#define north 3
using namespace std;
typedef struct{
    int x,y,id;
}pos;
bool cmpx(pos a,pos b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
bool cmpy(pos a,pos b){
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
int mir[2][4]={{north,west,south,east},{south,east,north,west}};/* mir 0=/ 1=\ */
pos tem[N];
int main () {
    int m;
    while(cin>>m){
        int nb[N][4]={0};//neighbor
        int me,cnt=0;
        int t[N];
        for(int i=0;i<N;i++)for(int j=0;j<4;j++)nb[i][j]=-1;
        for(int i=0;i<m;i++){
            cin>>tem[i].x>>tem[i].y>>t[i];
            tem[i].id=i;
        }
        sort(tem,tem+m,cmpx);
        for(int i=0;i<m-1;i++){
            if(tem[i].x==tem[i+1].x){
                nb[tem[i].id][north]=tem[i+1].id;
                nb[tem[i+1].id][south]=tem[i].id;
            }
        }
        sort(tem,tem+m,cmpy);
        for(int i=0;i<m-1;i++){
            if(tem[i].y==tem[i+1].y){
                nb[tem[i].id][east]=tem[i+1].id;
                nb[tem[i+1].id][west]=tem[i].id;
            }
        }
        bool finded=0;
        for(int i=0;i<m;i++){
            if(tem[i].y==0){
                int cur=tem[i].id;
                int dir=east;
                while(cur!=-1){
                    cnt++;
                    dir=mir[t[cur]][dir];
                    cur=nb[cur][dir];
                }
                cout<<cnt;
                finded =1;
                break;
            }
        }
        if(!finded){
            cout<<0;
        }
    }
    return 0;
}
```
:::
## P4 內積
https://zerojudge.tw/ShowProblem?problemid=i402
### 想法一(tle):
暴力解直接跟它拚，把所有可能都跑過一遍。
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
int main () {
    int m,n,ss,sum=INT_MIN,cnt=0;
    cin>>m>>n;
    vector<int> A(m),B(n);
    ss=min(m,n);
    for(int i=0;i<m;i++)cin>>A[i];
    for(int i=0;i<n;i++)cin>>B[i];
    for(int p=0;p<2;p++){
        for(int i=1;i<=ss;i++){
            for(int j=0;j<m+1-i;j++){
                for(int k=0;k<n+1-i;k++){
                    for(int l=0;l<i;l++){
                        cnt+=A[j+l]*B[k+l];
                    }
                    sum=max(sum,cnt);
                    cnt=0;
                }
            }
        }
        reverse(all(B));
    }
    cout<<sum;
}
```
:::
### 想法二:
用dp，建立一個二維表格dp[i][j]=A[i]*B[j]，然後跑遍所有的格子，跑的時候就看看dp[i-1][j-1]有沒有大於零，有的化就dp[i][j]+=dp[i-1][j-1]。記得表格最左跟最上面都要先填入才能計算。
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
using namespace std;
int dp[1001][1001];
int main () {
    int m=0,n=0,sum=INT_MIN;
    cin>>m>>n;
    vector<int> A(m),B(n);
    for(int i=0;i<m;i++)cin>>A[i];
    for(int i=0;i<n;i++)cin>>B[i];
    for(int k=0;k<2;k++){
        for(int j=0;j<n;j++){
            dp[0][j]=A[0]*B[j];
            sum=max(sum,dp[0][j]);
        }
        for(int i=1;i<m;i++){
            dp[i][0]=A[i]*B[0];
            sum=max(sum,dp[i][0]);
            for(int j=1;j<n;j++){
                dp[i][j]=A[i]*B[j];
                if(dp[i-1][j-1]>0)dp[i][j]+=dp[i-1][j-1];
                sum=max(sum,dp[i][j]);
            }
        }
        reverse(all(B));
    }
    cout<<sum;
}
```
:::
