---
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;
}
```
:::
Sign in with Wallet
Connect another wallet