---
tags: Coding
---
# APCS 2022 1月
## P1
https://zerojudge.tw/ShowProblem?problemid=h081
:::spoiler code

#include <iostream>
using namespace std;
int main(){
    int n;
    while(cin >> n && n) {
        int d;
        int x =0;
        int price;
        int getting = 0;
        int having;
        cin >> d;
        for (int c=0; c<n;c++){
            cin >> price;
            if(x == 0 || (price <= (x-d) && (!having))){
                x = price;
                having = 1;
            }  
            if(price >= (x+d) && having){
                getting += price-x;
                x=price;
                having = 0;
            }
        }
        cout << getting <<endl;
    }
}

:::
## P2
https://zerojudge.tw/ShowProblem?problemid=h082
::: spoiler code

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
signed main() {
  int n,m,k;
  while(cin>>n>>m &&n &&m){
    int s[1005],t[100000];
    int lose[1005] = {0};
    vector<int> v,v1,v2;
    for(int i=1;i<=n;i++){
      cin>>s[i];
    }
    for(int i=1;i<=n;i++){
      cin>>t[i];
    }
    for(int i=0;i<n;i++){
      cin>>k;
      v.push_back(k);
    }
    while(v.size()>1){
      for(int i=0;i<v.size()-1;i+=2){
        int fi=v[i],se = v[i+1];
        int a=s[fi],b=t[fi];
        int c=s[se],d=t[se];
        if(a*b>=c*d){
          s[fi] = a+c*d/(2*b);
          t[fi] = b+c*d/(2*a);
          s[se] = c+c/2;
          t[se] = d+d/2;
          lose[se]++;
          if(lose[se]<m)v2.push_back(se);
          v1.push_back(fi);
        }else if(a*b<c*d){
          s[fi] = a+a/2;
          t[fi] = b+b/2;
          s[se] = c+a*b/(2*d);
          t[se] = d+a*b/(2*c);
          lose[fi]++;
          if(lose[fi]<m)v2.push_back(fi);
          v1.push_back(se);
        }
      }
      if((int)v.size()%2 == 1)v1.push_back(v.back());
      v=v1;
      v.insert(v.end(),v2.begin(),v2.end());
      v1.clear();
      v2.clear();
    }
    cout<<v[0]<<endl;
  }
}

:::
## P3
https://zerojudge.tw/ShowProblem?problemid=h083
::: spoiler code

#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m;
  while(cin>>m){
    set<string> str;
    string s;
    int ans=0;
    for(int i=0;i<m;i++){
      cin>>s;
      str.insert(s);
    }
    for(auto &a:str){
      int l=a.length();
      if(l<3)continue;
      for(int i=1;i<=l/2;i++){
        if(a.substr(0,i)==a.substr(l-i)){
          if(str.count(a.substr(i,l-2*i)))ans++; 
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

:::
## P4
### 想法一(記憶體不夠)失敗55分
https://zerojudge.tw/ShowProblem?problemid=h084
用離散化儲存每一層樓的相鄰的長度，如果沒有相鄰就砍斷。
::: spoiler code

#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
vector<int> dis;
int getID(int a){
    return lower_bound(all(dis),a)-dis.begin()+1;
}
int main () {
    int m,n,heigh=INT_MIN;
    cin>>m>>n;
    vector<int> H(m),W(n),tem(m);
    for(int i=0;i<m;i++){
        cin>>H[i];
        dis.pb(H[i]);
    }
    sort(all(dis));
    dis.erase(unique(all(dis)),dis.end());
    vector<vector<int>>cnt;
    for(int i=0;i<dis.size();i++){
        vector<int>k;
        cnt.push_back(k);
    }
    for(int i=0;i<m;i++){
        heigh=max(heigh,H[i]);
        int id=getID(H[i]);
        int preid=getID(H[i-1]);
        for(int j=0;j<id;j++){
            tem[j]++;
        }
        for(int j=id;j<preid && i!=0;j++){
            cnt[j].pb(tem[j]);
            tem[j]=0;
        }
        if(i==m-1){
            for(int j=0;j<id;j++){
                cnt[j].pb(tem[j]);
            }
        }
    }
    for(int i=0;i<n;i++)cin>>W[i];
    int i;
    for( i=getID(heigh)-1;i>=0;i--){
        int fined=0,k=0;
        for(auto j:cnt[i]){
            if(j>=W[k]){
                k++;
            }
            if(k==n){
                fined=1;
                break;
            }
        }
        if(fined)break;
    }
    cout<<dis[i];
}

:::
### 想法二 60分解
針對第一第二子題作答，找指定長度中的最小值，且找每組中最小值得最大解
::: spoiler code

#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
#define int long long
using namespace std;
signed main () {
    int n,k,head=0,ans=LLONG_MIN;
    vector<int> h(200005),w(5005);
    vector<int> minh;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>h[i];
    for(int i=0;i<k;i++)cin>>w[i];
    for(int i=0;i<n;i++){
        while(minh.size()>head && h[i]<h[minh.back()])minh.pop_back();
        minh.push_back(i);
        if(minh[head]<=i-w[0])head++;
        if(i>=w[0]-1 && h[minh[head]]>ans)ans=h[minh[head]];
    }
    cout<<ans;
}

:::
### 想法三
https://www.youtube.com/watch?v=w0ahlLRFSe0&t=299s
:::spoiler

#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
using namespace std;

bool test(vector<int>&h , vector<int>&w , int y){
    int hi=0,wi=0;
    while( wi<w.size()){
        int len=0;
        while(y<=h[hi] && len<w[wi] && hi<h.size()){
            len++;
            hi++;
        }
        if(len==w[wi])wi++;
        else if(hi==h.size())return false;
        else if(y>h[hi])hi++;
    }
    return true;
}

signed main(){
    int n,k;
    vector<int>h(2000005),w(5005);
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>h[i];
    for(int i=0;i<k;i++)cin>>w[i];
    int maxh=*max_element(all(h)),ans=0;
    int jump=maxh;
    while(jump > 0){
        while(ans+jump<=maxh && test(h,w,ans+jump)){
            ans+=jump;
        }
        jump>>=1;
    }
    cout<<ans;
}

:::