# TIOJ
## [地雷區](https://tioj.ck.tp.edu.tw/problems/1420)
想法：
每次讀入炸彈座標，如果這裡被其他的炸彈覆蓋過了，那就併入覆蓋他的炸彈，再將他九宮格範圍內的一同併入，如果沒有的話那就自己獨立成新的一群，最後再看有幾群就好。

sol : (Implementation, dsu, 2d array)

#include<bits/stdc++.h>
#define ll long long
#define rep(a,b,c) for(int a=b; a<c; ++a)
#define pb emplace_back
#define f first
#define s second
#define gao pair<int,int>
using namespace std;
const int maxn=1e5+5;
int mx[8]={-1,-1,-1,0,0,1,1,1};
int my[8]={-1,0,1,-1,1,-1,0,1};
ll exp(ll idx,ll k,ll mod){
    if(k==1) return idx;
    if(k%2) return idx*(exp(idx,k-1,mod))%mod;
    else{
        ll hehe=exp(idx,k/2,mod);
        return hehe*hehe%mod;
    }
}
vector<int> anc(50001,0);
int find(int idx){
    if(idx==anc[idx]) return idx;
    else return anc[idx]=find(anc[idx]);
}
void merge(int a,int b){
    int f1=find(a),f2=find(b);
    if(f1==f2) return;
    anc[f2]=f1;
    return ;
}
void solve(){
    int x,y,b;
    cin>>x>>y>>b;
    int graph[x][y];
    rep(i,0,x){
        rep(j,0,y) graph[i][j]=0;
    }
    rep(i,1,b+1) anc[i]=i;
    rep(i,1,b+1){
        int bx,by;
        cin>>bx>>by;
        bx--,by--;
        if(graph[bx][by]) merge(graph[bx][by],anc[i]);
        else graph[bx][by]=anc[i];
        rep(j,0,8){
            int tx=bx+mx[j],ty=by+my[j];
            if(tx<0||tx>=x||ty<0||ty>=y) continue;
            if(graph[tx][ty]) merge(graph[tx][ty],anc[i]);
            else graph[tx][ty]=anc[i];
        }
    }
    set<int> s;
    rep(i,1,b+1){
        int f=find(i);
        if(s.find(f)==s.end()) s.insert(f);
    }
    cout<<s.size()<<'\n';
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
}

## [貨物運送計畫](https://tioj.ck.tp.edu.tw/problems/1641)
想法：
你開乘會跟我的物理段考一樣裂開，用log來代替乘法，就變加法了。
最後就pow回來，整數部分代表次方，那剩餘的就是你完整的值的樣子。
sol : (math, dijkstra)

#include<bits/stdc++.h>
#define int long long
#define rep(a,b,c) for(int a=b; a<c; ++a)
#define gao pair<int,double>
#define lol pair<double,int>
#define f first
#define s second
#define pb emplace_back
using namespace std;
const int maxn=1e4+5;
const int lim=1e15;
vector<gao> path[maxn];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    rep(i,0,m){
        int u,v;
        double w;
        cin>>u>>v>>w;
        path[u].pb(v,double(log10(w+1)));
    }
    double dis[maxn];
    rep(i,0,maxn) dis[i]=lim;
    priority_queue<lol,vector<lol>,greater<lol>> pq;
    dis[s]=double(0);
    pq.push({dis[s],s});
    while(!pq.empty()){
        auto t=pq.top();
        pq.pop();
        for(auto son:path[t.s]){
            if(dis[son.f]>t.f+son.s){
                dis[son.f]=t.f+son.s;
                pq.push({dis[son.f],son.f});
            }
        }
    }
    double ans=dis[t];
    int left=floor(ans);
    ans-=left;
    cout<<fixed<<setprecision(2)<<pow(10,ans)<<"e+";
    if(left<100){
        if(left<10) cout<<"00"<<left;
        else cout<<"0"<<left;
    }
    else cout<<left;
    cout<<'\n';
}

## [烏龜暗殺 梗](https://tioj.ck.tp.edu.tw/problems/1706)
想法：
仔細看一下會有單調性，要嘛第一天最好，要不然就最後一天，剩下就實作。
sol : (greedy, dijkstra)

#include<bits/stdc++.h>
#define int long long
#define rep(a,b,c) for(int a=b; a<c; ++a)
#define gao pair<int,int>
#define f first
#define s second
#define pb emplace_back
using namespace std;
const int maxn=2e5+5;
const int lim=1e15;
vector<gao> path[maxn];
vector<gao> rev[maxn];
int d1(int start,int end){
    priority_queue<gao,vector<gao>,greater<gao>> pq;
    int dis[maxn];
    rep(i,0,maxn) dis[i]=lim;
    dis[start]=0;
    pq.push({dis[start],start});
    while(!pq.empty()){
        auto t=pq.top();
        pq.pop();
        for(auto son:path[t.s]){
            if(dis[son.f]>t.f+son.s){
                dis[son.f]=t.f+son.s;
                pq.push({dis[son.f],son.f});
            }
        }
    }
    return dis[end];
}
int d2(int start,int end){
    priority_queue<gao,vector<gao>,greater<gao>> pq;
    int dis[maxn];
    rep(i,0,maxn) dis[i]=lim;
    dis[start]=0;
    pq.push({dis[start],start});
    while(!pq.empty()){
        auto t=pq.top();
        pq.pop();
        for(auto son:rev[t.s]){
            if(dis[son.f]>t.f+son.s){
                dis[son.f]=t.f+son.s;
                pq.push({dis[son.f],son.f});
            }
        }
    }
    return dis[end];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,r,a,b,d;
    cin>>n>>r>>a>>b>>d;
    rep(i,0,r){
        int u,v,c1,p1,c2,p2;
        cin>>u>>v>>c1>>p1>>c2>>p2;
        path[u].pb(v,c1);
        path[v].pb(u,c2);
        rev[u].pb(v,c1+p1*(d-1));
        rev[v].pb(u,c2+p2*(d-1));
    }
    int f1_go=d1(a,b);
    int f1_back=d1(b,a);
    int f2_go=d2(a,b);
    int f2_back=d2(b,a);
    cout<<min(f1_go+f1_back,f2_go+f2_back)<<'\n';
}

## [algae](https://tioj.ck.tp.edu.tw/problems/1677)
想法：
可以觀察到數列是費氏數列，但知道這個性質只夠我們找到當天的枝數，
再觀察可以發現，每n項數列剛好也是n-1項跟n-2項合併。(多寫個幾項出來)
所以就從中間猛拆，最後會拆到1或2，這是你絕對知道答案的狀況。
sol : (math, binary search)

#include<bits/stdc++.h>
#define int long long
#define rep(a,b,c) for(int a=b; a<c; ++a)
using namespace std;
int f[101];
void init(){
    f[0]=0;
    f[1]=1;
    rep(i,2,101) f[i]=f[i-1]+f[i-2];
}
void solve(){
    int n,k;
    cin>>n>>k;
    if(f[n]<k) cout<<-1<<'\n';
    else{
        if(n==1) cout<<0<<'\n';
        else if(n==2) cout<<1<<'\n';
        else{
            int t=n;
            while(t>=3){
                if(f[t-2]>=k){
                    t=t-2;
                }
                else{
                    k-=f[t-2];
                    t=t-1;
                }
            }
            cout<<(t==1?0:1)<<'\n';
        }
    }
}
signed main(){
    init();
    int t;
    cin>>t;
    while(t--) solve();
}

## [害蟲決戰時刻](https://tioj.ck.tp.edu.tw/problems/1699)
想法：
裸莫隊，只是題敘搞耍，種族的範圍會超大，我沒有離散化被搞翻，謝謝衣服幫我檢查。
詳情明天補，蔡昀熹是馴龍騎士。

#include<bits/stdc++.h>
#define ll long long
#define rep(a,b,c) for(int a=b; a<c; ++a)
#define pb emplace_back
#define f first
#define s second
#define lpos pos*2
#define rpos pos*2+1
#define gao pair<ll,ll>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int maxn=1e5+5;
struct que{
    int l,r,k,order,kuai;
};
bool cmp(que a,que b){
    if(a.kuai==b.kuai) return a.r<b.r;
    else return a.kuai<b.kuai;
}
que ques[maxn];
vector<int> vec(maxn);
int cnt[maxn]={0},hehe[maxn]={0};
int n,q,ans=0;
void add(int idx){
    hehe[cnt[idx]]--;
    cnt[idx]++;
    hehe[cnt[idx]]++;
    //cout<<ans<<" "<<idx<<'\n';
    ans=max(ans,cnt[idx]);
}
void rem(int idx){
    hehe[cnt[idx]]--;
    cnt[idx]--;
    hehe[cnt[idx]]++;
    while(!hehe[ans]) ans--;
}
void PF(){
    sort(ques,ques+q,cmp);
    int L=1,R=1;
    add(vec[1]);//bruh
    hehe[0]=n;
    bitset<maxn> b;
    b.reset();
    rep(i,0,q){
        while(R<ques[i].r) add(vec[++R]);
        while(L>ques[i].l) add(vec[--L]);
        while(R>ques[i].r) rem(vec[R--]);
        while(L<ques[i].l) rem(vec[L++]);
        if(1.0*ans>=1.0*(ques[i].r-ques[i].l+1)/ques[i].k) b[ques[i].order]=1;
    }
    rep(i,0,q) cout<<(b[i]?"Yes":"No")<<'\n';
}
void solve(){
    cin>>n>>q;
    map<int,int> m;
    rep(i,1,n+1) cin>>vec[i],m[vec[i]]++;
    int stamp=0;
    for(auto &t:m) t.s=++stamp;
    rep(i,1,n+1) vec[i]=m[vec[i]];
    int standard=sqrt(n);
    rep(i,0,q){
        cin>>ques[i].l>>ques[i].r>>ques[i].k;
        ques[i].order=i;
        ques[i].kuai=(ques[i].l/standard);
    }
    PF();
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
}

## [領土](https://tioj.ck.tp.edu.tw/problems/1280https://tioj.ck.tp.edu.tw/problems/1280)
裸凸包
有個可以注意的地方是在convex_hull cross的部分
<0 會把斜率一樣的push_back
<=0 會把斜率一樣的捨棄，如果答案要最少點可以這樣

#include<bits/stdc++.h>
#define int long long
#define rep(a,b,c) for(int a=b; a<c; ++a)
#define pb push_back
#define gao pair<int,int>
#define f first
#define s second
using namespace std;
vector<gao> vec;
gao operator - (gao x,gao y){
    return {x.f-y.f,x.s-y.s};
}
int cross(gao x,gao y){
    return x.f*y.s-x.s*y.f;
}
vector<gao> convex_hull(){
    vector<gao> ret;
    sort(vec.begin(),vec.end());
    rep(i,0,2){
        int t=ret.size();
        for(auto pt: vec){
            while(ret.size()-t>=2&&cross(ret.back()-ret[ret.size()-2],pt-ret[ret.size()-2])<0) ret.pop_back();
            ret.pb(pt);
        }
        ret.pop_back();
        reverse(vec.begin(),vec.end());
    }
    return ret;
}
void solve(){
    int n;
    cin>>n;
    vec.resize(n);
    rep(i,0,n){
        cin>>vec[i].f>>vec[i].s;
    }
    vector<gao> ans=convex_hull();
    //for(auto t:ans) cout<<t.f<<" "<<t.s<<'\n';
    int b=ans.size();
    int cnt=0;
    ans.pb(ans.front());
    rep(i,0,b){
        cnt+=(cross(ans[i],ans[i+1]));
        //cout<<cnt<<" ";
    }
    cout<<cnt/2+cnt%2<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
}