# APCS 2022/1 題解
## ==程式交易==
### <font color="0E81A6">題目</font>
[程式交易](https://zerojudge.tw/ShowProblem?problemid=h081)
### <font color="0E81A6">核心</font>
條件判斷
### <font color="0E81A6">思路</font>
不用陣列。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,D;
    scanf("%d%d",&n,&D);
    int cost,value;
    scanf("%d",&cost);
    int total=-cost;
    bool have=true;
    for(int i=1;i<n;i++)
    {
        scanf("%d",&value);
        if(have&&value>=cost+D) total+=value,have=false,cost=value;
        if(!have&&value<=cost-D) total-=value,have=true,cost=value;
    }
    if(have) total+=cost;
    printf("%d\n",total);
}

## ==贏家預測==
### <font color="0E81A6">題目</font>
[贏家預測](https://zerojudge.tw/ShowProblem?problemid=h082)
### <font color="0E81A6">核心</font>
模擬、vector
### <font color="0E81A6">思路</font>
注意運算時S[i]與T[i]的更動，需先賦予給暫存變數。
vector處理要熟記。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,From,num;
int S[1005],T[1005],Count[1005]={0};
vector<int> order,next_order;
void caculate(int win,int lose,int h)
{
    int a,b;
    next_order.insert(next_order.begin()+From,win);
    a=S[win],b=T[win];
    S[win]=S[win]+h/(2*b),T[win]=T[win]+h/(2*a);
    S[lose]=S[lose]+S[lose]/2,T[lose]=T[lose]+T[lose]/2;
    Count[lose]++;
    if(Count[lose]<m) next_order.push_back(lose);
    From++;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",S+i);
    for(int i=1;i<=n;i++) scanf("%lld",T+i);
    for(int i=0;i<n;i++) scanf("%lld",&num),order.push_back(num);
    while(order.size()>1)
    {
        n=order.size();
        int a,b;
        From=0;
        for(int i=1;i<n;i+=2)
        {
            int p1=order[i-1],p2=order[i];
            int h1=S[p1]*T[p1],h2=S[p2]*T[p2];
            if(h1>=h2) caculate(p1,p2,h2);
            else caculate(p2,p1,h1);
        }
        if(n&1) next_order.insert(next_order.begin()+From,order[n-1]);
        order=next_order;
        next_order.clear();
    }
    printf("%lld\n",order[0]);
}

## ==數位占卜==
### <font color="0E81A6">題目</font>
[數位占卜](https://zerojudge.tw/ShowProblem?problemid=h083)
### <font color="0E81A6">核心</font>
string、枚舉、set
### <font color="0E81A6">思路</font>
枚舉每一個字串，將頭尾分別長度由小到大拆分，若頭尾相同，則去set裡找中間子字串。
由於查找子字串長度會是較短方，故答案不會重複計算。

#include<bits/stdc++.h>
using namespace std;
set<string> S;
vector<string> V;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        string str;
        cin>>str;
        S.insert(str);
        V.push_back(str);
    }
    int ans=0;
    for(auto s:V)
    {
        for(int len=1; len<=s.size()/2; len++)
        {
            string head=s.substr(0,len);
            string tail=s.substr(s.size()-len,len);
            if(head==tail)
            {
                string want=s.substr(len,s.size()-2*len);
                ans+=S.count(want);
            }
        }
    }
    cout<<ans<<endl;
}

## ==牆上海報==
### <font color="0E81A6">題目</font>
[牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)
### <font color="0E81A6">核心</font>
二分搜、貪婪
### <font color="0E81A6">思路</font>
這題我以為不用照順序，害我卡個半死。

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,k,f[N],poster[5000];
bool post(int high)
{
    vector<int> V;
    int length=0;
    for(int i=0;i<n;i++)
    {
        if(f[i]>=high) length++;
        else
        {
            if(length!=0) V.push_back(length),length=0;
        }
    }
    if(length!=0) V.push_back(length);
    int cnt=0;
    for(int i=k-1;i>=0&&V.size();i--)
    {
        if(V.back()>=poster[i])
        {
            cnt++;
            V.back()-=poster[i];
        }
        else
        {
            while(V.back()<poster[i]&&V.size()) V.pop_back();
            i++;
        }
    }
    return cnt==k;

}
int findh()
{
    int l=1,r=1e9+1,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        bool can=post(mid);
        if(can) l=mid+1;
        else r=mid;
    }
    return l-1;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",f+i);
    for(int i=0;i<k;i++) scanf("%d",poster+i);
    int maxh=findh();
    printf("%d\n",maxh);

}