---
title: 'AtCoder Beginner Contest 271'
disqus: hackmd
---

AtCoder Beginner Contest 271
===

[TOC]
### [A - 484558](https://atcoder.jp/contests/abc271/tasks/abc271_a) [ascii code]
:::info
小知識:當數字>10，可以下列關係式轉換成英文
(char)('A'+b-10)
:::

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin>>n;
  int a=n/16,b=n%16;
  if(a<=9)cout<<a;
  else cout<<(char)('A'+a-10);
  if(b<=9)cout<<b;
  else cout<<(char)('A'+b-10);
  return 0;
}

### [B - Maintain Multiple Sequences](https://atcoder.jp/contests/abc271/tasks/abc271_b) [vector]
:::info
看到大小不固定的陣列，當然是直接開vector動態改變他阿!
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
vector<ll> vec[200010];
int main() {
  ll n,q;
  cin>>n>>q;
  for(ll i=0;i<n;i++){
    ll le;
    cin>>le;
    for(ll j=0,num;j<le;j++){
      cin>>num;
      vec[i].pb(num);
    }
  }
  while(q--){
    ll f,s;
    cin>>f>>s;
    cout<<vec[f-1][s-1]<<endl;
  }
  return 0;
}

### [C - Manga](https://atcoder.jp/contests/abc271/tasks/abc271_c) [雙指針]
:::danger
vec.erase()複雜度是O(n)!!!!!，所以會TLE。
:::
:::info
利用L、R維護左界(沒有第幾本書)、右界(目前有的書籍的最大編號)，複雜度O(n)(當兩指針疊在一起時)
:::

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
int main() {
  ll sold=0,n;
  cin>>n;
  vector<ll> a(n);//紀錄有什麼書籍
  vector<bool> vol(n+2,false);
  for(ll i=0;i<n;i++){
    cin>>a[i];
    if(a[i]>n) sold++;//最多讀到第n本，第n+1本以後的賣出
    else if(!vol[a[i]]) vol[a[i]]=1;//紀錄有的書
    else sold++;//多於一本賣掉
  }
  ll l=1,r=n+1;//維護目前沒有的書、最大擁有編號多少的書
  while(1){
    while(vol[l]) l++;//連續讀下去
    while(r!=0 && vol[r]==0) r--;//沒有這些書
    if(sold>=2){//書不夠讀了，交換書
      sold-=2;//少兩本
      vol[l]=1;//換一本
    }
    else{
      if(l>=r) break;//沒有的書編號>擁有的書編號，矛盾，停止
      vol[r]=false;//賣掉一本
      sold++;//多一本可能可以交換的書
    }
  }
  cout<<l-1<<endl;//只能讀到l-1本
  return 0;
}

TLE扣

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
vector<ll> sta;
int main() {
  ios::sync_with_stdio(0);
  cin.tie();cout.tie();
  ll n;
  cin>>n;
  for(ll i=0,num;i<n;i++){
    cin>>num;
    sta.pb(num);
  }
  ll ans=0;
  if((ll)sta.size()==1 && sta[0]==1){
    cout<<1<<endl;
    return 0;
  }
  else if((ll)sta.size()==1 && sta[0]!=1){
    cout<<0<<endl;
    return 0;
  }
  ll cnt=1;
  sort(sta.begin(),sta.end());
  while((ll)sta.size()>1){
    if(sta[0]==cnt){
      sta.erase(sta.begin());
      ans+=1;
    }
    else{
      sta.pop_back();
      sta.pop_back();
      ans++;
    }
    cnt++;
  }
  if(sta[0]==cnt) ans++;
  cout<<ans<<endl;
  return 0;
}

### [D - Flip and Adjust](https://atcoder.jp/contests/abc271/tasks/abc271_d) [dp]
:::info
通靈dp:
1. 定義初始狀態:
dp[0][0]=1,dp[0][x]=0(x>0)
2. 定義轉移式:
如果由第1張卡牌至第i張卡牌可以湊出j，定義dp[i][j]=1
3. dp性質:
如果$j+a_i \le S$，那dp[i+1][j+$a_i$]=1
如果$j+b_i \le S$，那dp[i+1][j+$b_i$]=1
4. 實作方法:
先掃過i，然後看($a_i+$多少$\le S$)有辦法走到，那就走那一格
:::

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[110][10000];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  ll n,s;
  cin>>n>>s;
  ll a[n],b[n];
  for(ll i=0;i<n;i++) cin>>a[i]>>b[i];
  dp[0][0]=1;
  for(ll i=0;i<n;i++){
    for(ll j=0;j<=s;j++){
      if(dp[i][j]){
        if(j+a[i]<=s){
          dp[i+1][j+a[i]]=1;
        }
        if(j+b[i]<=s){
          dp[i+1][j+b[i]]=1;
        }
      }
    }
  }
  if(dp[n][s]){
    cout<<"Yes\n";
    string str(n,'H');
    for(ll i=n-1;i>=0;i--){
      if(s>=a[i] && dp[i][s-a[i]]){//可以從前一格跳來
        str[i]='H';
        s-=a[i];
      }
      else{
        str[i]='T';
        s-=b[i];
      }
    }
    cout<<str<<endl;
  }
  else cout<<"No\n";
  return 0;
}

### [E - Subsequence Path ](https://atcoder.jp/contests/abc271/tasks/abc271_e)[dp]
:::info
看到這題超級通靈，竟然把圖論題當成dp來做。
定義dist[i]代表到i點距離的最小值，dist[0]=0(起點)，
走不到設成無限大。
:::
:::success
注意到因為是有向圖，所以b[e]必由a[e]走邊權c[e]的邊而來，
故dist[b[e]]=max(dist[b[e]],a[e]+c[e])
:::

#include <iostream>
#include <vector>
#define ll long long 
#define inf 10000000000000000
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  ll n,m,k;
  cin>>n>>m>>k;
  vector<ll> a(m),b(m),c(m),dist(n,inf);
  for(ll i=0;i<m;i++) {
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;b[i]--;
  }
  dist[0]=0;
  while(k--){
    ll e;
    cin>>e;
    e--;
    dist[b[e]]=min(dist[b[e]],dist[a[e]]+c[e]);
  }
  if(dist[n-1]!=inf){
    cout<<dist[n-1]<<"\n";
  }
  else cout<<-1<<endl;
  return 0;
}