# APCS 2022/6 題解
## ==數字遊戲==
### <font color="0E81A6">題目</font>
[數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399)
### <font color="0E81A6">核心</font>
陣列、排序
### <font color="0E81A6">思路</font>
大到小排序，扣掉重複。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int A[3];
    scanf("%d%d%d",A,A+1,A+2);
    int num=1;
    sort(A,A+3,greater<int>());
    for(int i=1;i<3;i++)
    {
        if(A[i]==A[i-1]) num++;
    }
    printf("%d %d ",num,A[0]);
    for(int i=1;i<3;i++)
    {
        if(A[i]!=A[i-1]) printf("%d ",A[i]);
    }
}

## ==字串解碼==
### <font color="0E81A6">題目</font>
[字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400)
### <font color="0E81A6">核心</font>
二維陣列、模擬、String
### <font color="0E81A6">思路</font>
注意字串長度奇數和偶數要分別判斷。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int m,n;
    cin>>m>>n;
    string s;
    int code[105][105],oddNum[105];
    for(int i=0;i<m;i++)
    {
        cin>>s;
        for(int j=0;j<n;j++)
        {
            code[i][j]=s[j]-'0';
            if(code[i][j]&1) oddNum[i]++;
        }
    }
    string str1;
    cin>>str1;
    for(int i=m-1;i>=0;i--)
    {
        string str2,temp1,temp2;
        for(int j=n-1;j>=0;j--)
        {
            if(code[i][j]&1) str2=str2+str1[j];
            else str2=str1[j]+str2;
        }
        if(oddNum[i]&1 && n&1)
        {
            temp1=str2.substr(0,n/2);
            temp2=str2.substr(n/2+1);
            str2=temp2+str2[n/2]+temp1;
        }
        else if(oddNum[i]&1)
        {
            temp1=str2.substr(0,n/2);
            temp2=str2.substr(n/2);
            str2=temp2+temp1;
        }
        str1=str2;
    }
    cout<<str1<<endl;
}

## ==雷射測試==
### <font color="0E81A6">題目</font>
[雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401)
### <font color="0E81A6">核心</font>
二分搜、模擬
### <font color="0E81A6">思路</font>
當入射方向為向左或向右時，X值固定，要考慮此時最接近Y值。
當入射方向為向上或向下時，Y值固定，要考慮此時最接近X值。
由於最接近的值有可能是大於或小於，故分別用upper_bound和lower_bound。
若找不到值則break。

#include<bits/stdc++.h>
using namespace std;
#define N 250005
#define M 30005
#define piib pair<pair<int,int>,bool>
#define ff first.first
#define fs first.second
set<piib> Xst; //(y,x),grs
set<piib> Yst; //(x,y),grs
//0 up, 1 down, 2 left, 3 right
int main()
{
    int n;
    scanf("%d",&n);
    int x,y,g;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&g);
        Xst.insert({{y,x},g});
        Yst.insert({{x,y},g});
    }
    piib now={{0,0},0}; //x,y,g
    int dir=3;
    int ans=0;
    while(true)
    {
        if(dir==0)
        {
            auto it=Yst.upper_bound(now);
            if(it==Yst.end()) break;
            piib next=*it;
            if(next.ff!=now.ff) break;
            ans++;
            bool grass=next.second;
            if(grass) dir=2;
            else dir=3;
            now=next;
        }
        else if(dir==1)
        {
            auto it=Yst.lower_bound(now);
            if(it==Yst.begin()) break;
            piib next=*(prev(it));
            if(next.ff!=now.ff) break;
            ans++;
            bool grass=next.second;
            if(grass) dir=3;
            else dir=2;
            now=next;
        }
        else if(dir==2)
        {
            auto it=Xst.lower_bound({{now.fs,now.ff},now.second});
            if(it==Xst.begin()) break;
            piib next=*(prev(it));
            if(next.ff!=now.fs) break;
            ans++;
            bool grass=next.second;
            if(grass) dir=0;
            else dir=1;
            now={{next.fs,next.ff},next.second};
        }
        else
        {
            auto it=Xst.upper_bound({{now.fs,now.ff},now.second});
            if(it==Xst.end()) break;
            piib next=*it;
            if(next.ff!=now.fs) break;
            ans++;
            bool grass=next.second;
            if(grass) dir=1;
            else dir=0;
            now={{next.fs,next.ff},next.second};
        }
    }
    printf("%d\n",ans);
}

## ==內積==
### <font color="0E81A6">題目</font>
[內積](https://zerojudge.tw/ShowProblem?problemid=i402)
### <font color="0E81A6">核心</font>
dp、LCS、枚舉
### <font color="0E81A6">思路</font>
前i對前j。
dp記錄此時最大內積值，presum記錄先前連續的內積值。
注意邊界(這裡是單一個內積的時候)。
注意需要將一個陣列反過來做一次。

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n,m,ans=INT_MIN;
int A[N],B[N],dp[N][N],presum[N][N];
void caculate()
{
    memset(dp,0,sizeof(dp));
    memset(presum,0,sizeof(presum));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=A[i]*B[j];
            if(i>1&&j>1)
            {
                dp[i][j]=max({A[i]*B[j],dp[i-1][j-1],presum[i-1][j-1]+A[i]*B[j]});
            }
            presum[i][j]=max(A[i]*B[j],presum[i-1][j-1]+A[i]*B[j]);
            ans=max(ans,dp[i][j]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",A+i);
    for(int i=1;i<=m;i++) scanf("%d",B+i);
    caculate();
    for(int i=1;i<=n/2;i++) swap(A[i],A[n+1-i]);
    caculate();
    printf("%d\n",ans);
}