---
# System prepended metadata

title: DDJ Regular Contest Round#4 "DD Jet" Tutorial
tags: [DDJRC]

---

---
tags: DDJRC
---

# DDJ Regular Contest Round#4 "DD Jet" Tutorial

## a611: A. 栄、国士無双
<code>tags: treap, RMQ</code>

RMQ問題，一般來說可以用線段樹、BIT、或是treap來解
但這題的鍵值非整數，所以用treap比較方便

實作上要注意詢問是左閉右閉，所以用同一個`split`函數來處理可能會少掉一邊的邊界沒取到
這時候可以寫兩個`split`來解決 :poop:

:::spoiler code by *konchin.shih*
```cpp=
mt19937 mt;

struct node{
    int a,b,mx,v;
    node *l,*r;
    node* update(){
        mx=a;
        if(l) mx=max(mx,l->mx);
        if(r) mx=max(mx,r->mx);
        return this;
    }
    node(int x,int y):
        a(x),b(y),mx(x),v(mt()),l(nullptr),r(nullptr){}
};
using treap = node*;

treap merge(treap a,treap b){
    if(!a||!b) return a?:b;
    if(a->v<b->v)
        return a->r=merge(a->r,b),a->update();
    else
        return b->l=merge(a,b->l),b->update();
}

void lower_split(treap t,int ka,int kb,treap& a,treap& b){
    if(!t){a=b=nullptr;return;}
    if(1LL*t->a*kb<1LL*t->b*ka)
        a=t,lower_split(a->r,ka,kb,a->r,b),a->update();
    else
        b=t,lower_split(b->l,ka,kb,a,b->l),b->update();
}

void upper_split(treap t,int ka,int kb,treap& a,treap& b){
    if(!t){a=b=nullptr;return;}
    if(1LL*t->b*ka<1LL*t->a*kb)
        b=t,upper_split(b->l,ka,kb,a,b->l),b->update();
    else
        a=t,upper_split(a->r,ka,kb,a->r,b),a->update();
}

void insert(treap& t,int x,int y){
    treap l,r;
    lower_split(t,x,y,l,r);
    t=merge(merge(l,new node(x,y)),r);
}

int query(treap& t,int la,int lb,int ra,int rb){
    treap l,m,r;
    lower_split(t,la,lb,l,r);
    upper_split(r,ra,rb,m,r);
    int ret=m?m->mx:-1;
    t=merge(merge(l,m),r);
    return ret;
}

inline void solve() {
    treap tree=nullptr;
    int n;cin>>n;
    while(n--){
        int op;cin>>op;
        if(op){
            int la,lb,ra,rb;
            cin>>la>>lb>>ra>>rb;
            cout<<query(tree,la,lb,ra,rb)<<endl;
        }else{
            int a,b; cin>>a>>b;
            insert(tree,a,b);
        }
    }
}
```
:::

---

## a597: B. DD的背包問題
<code>tags: DP, knapsack</code>

經典的分組背包問題，不過每個頻道只能選一種訂閱層級
所以轉移時必須從上一個頻道的最佳解進行轉移

:::spoiler code by *konchin.shih*
```cpp=
inline void solve() {
    int n,c; cin>>n>>c;
    vector<long long> dp(c+1,0);
    while(n--){
        static int k; cin>>k;
        auto pre = dp;
        while(k--){
            static int v,w; cin>>v>>w;
            for(int i=c;i>=w;i--)
                dp[i]=max(dp[i],v+pre[i-w]);
        }
    }
    cout<<dp.back()<<endl;
}
```
:::

---

## a605: C. 指揮官的背包問題
<code>tags: DP, knapsack</code>

也是背包問題，不過背包的容量(經驗值)太大無法用容量DP
再者，可以觀察到物品的價值總和(等級%數)最多只會有 $n\times 100$ 種
於是可以用價值作為DP的參數
具體來說就是對於每個價值，儲存最少需要使用多少容量
最後遍歷一次，在容量不超過 $exp$ 的情況下取最大價值就好

另外要注意輸入有浮點數，建議轉成整數再做運算

:::spoiler code by *konchin.shih*
```cpp=
using ll=long long;
inline void solve() {
    ll n,exp; cin>>n>>exp;
    vector<ll> dp(100001,1e15+5); dp[0]=0;
    while(n--){
        ll a,b; string str;
        cin>>a>>str;
        str.resize(str.find('.')+3,'0');
        str.resize(remove(str.begin(),str.end(),'.')-str.begin());
        sscanf(str.data(),"%lld",&b);
        cout<<b<<endl;
        for(int i=100000;i>=b;i--)
            dp[i]=min(dp[i],a+dp[i-b]);
    }
    for(int i=100000;i>=0;i--)
        if(dp[i]<=exp){
            cout<<fixed<<setprecision(2)<<i/100.0<<endl;
            return;
        }
}
```
:::

---

## a607: D. 馬娘玩家的末路
<code>tags: convex hull</code>

這題就是求凸包面積，要注意的是題敘裡有提到**與原點**所構成的面積
所以要在點集裡面加上原點才會正確

:::spoiler code by *konchin.shih*
```cpp=
using ll=long long;
template<typename T> using V=vector<T>;
template<typename T1,typename T2=T1> using P=pair<T1,T2>;
inline void solve() {
    int n; cin>>n;
    V<P<ll>> v(n);
    for(auto& i:v)
        cin>>i.first>>i.second;
    v.emplace_back(0,0),n++;
    sort(v.begin(),v.end());
    V<P<ll>> s{v[0],v[1]};
    auto cross = [](P<ll> o,P<ll> a,P<ll> b){
        return (a.first-o.first)*(b.second-o.second)
            -(b.first-o.first)*(a.second-o.second);
    };
    auto revs=[&]{return s.rbegin();};
    for(int i=2;i<n;s.emplace_back(v[i++]))
        while(s.size()>=2&&cross(revs()[1],revs()[0],v[i])<=0)
            s.pop_back();
    for(int i=n-2,t=s.size()+1;i>=0;s.emplace_back(v[i--]))
        while(int(s.size())>=t&&cross(revs()[1],revs()[0],v[i])<=0)
            s.pop_back();
    auto area=[](P<ll> a,P<ll> b){
        return abs(a.first*b.second-a.second*b.first);
    }; 
    ll sum=0;
    for(int i=1;i<int(s.size());i++)
        sum+=area(s[i-1],s[i]);
    ll maxn=0,k;
    for(int i=0;i<11;i++)
        cin>>k,maxn=max(maxn,k<<1);
    if(maxn<sum)
        cout<<"nice"<<endl;
    else
        cout<<"sleep"<<endl;
}
```
:::

---

## a609: E. Getting Over Orange
<code>tags: math, Gaussian elimination</code>

由題目可以推得以下公式

$t=$ 到終點的期望時間$$t_i=a_i(1+t_{i+1})+b_i(1+t_i)+c_i\sum^{k<i}_{k=0}(\frac{1+t_k}{i})$$

則可以化簡成$$a_it_{i+1}+(b_i-1)t_i+c_i\sum_{k=0}^{k<i}\frac{t_k}{i}=-a_i-b_i-c_i$$

又 $\because a_i+b_i+c_i=1$ $$\therefore\ a_it_{i+1}+(b_i-1)t_i+c_i\sum_{k=0}^{k<i}\frac{t_k}{i}=-1$$

可以發現最終可以列出 $n$ 條 $n$ 元一次方程式
則可以用高斯消去法求解

注意實作時需要利用模逆元求 $Q^{-1}$
也可以看個人習慣實作分數，取代頻繁的取反元素

:::spoiler code by *konchin.shih*
```cpp=
constexpr int mod = 1e9+7;

struct frac{
    ll a,b;
    frac(ll x=0,ll y=1):
        a((x%mod+mod)%mod),b(y%mod){}
    operator bool(){return bool(a);}
};
frac operator+(frac a,frac b){
    return frac(a.a*b.b+a.b*b.a,a.b*b.b);
}
frac operator-(frac a){
    return frac(mod-a.a%mod,a.b);
}
frac operator/(frac a,frac b){
    return frac(a.a*b.b,a.b*b.a);
}
frac operator*(frac a,frac b){
    return frac(a.a*b.a,a.b*b.b);
}

ll fpow(ll a,ll b){
    ll ret=1;
    for(a%=mod;b;b>>=1,a=a*a%mod)
        if(b&1) ret=ret*a%mod;
    return ret;
}

ll rev(ll a){return fpow(a,mod-2);}
template<typename T> using V=vector<T>;
template<typename T,int N> using A=array<T,N>;
inline void solve() {
    int n;cin>>n;
    V<V<frac>> dp(n+1,V<frac>(n+1,frac(0)));
    V<A<frac,3>> v(n);
    for(auto& i:v)
        for(auto& j:i){
            int k;cin>>k;
            j=frac(k)/frac(100);
        }
    for(int i=0;i<n;i++){
        dp[i][i]=-v[i][1]+frac(1);
        dp[i][i+1]=-v[i][0];
        for(int k=0;k<i;k++)
            dp[i][k]=-v[i][2]/frac(i);
        dp[i][n]=frac(1);
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n&&!dp[i][i];j++)
            dp[i].swap(dp[j]);
        if(!dp[i][i])
            continue;
        for(int j=0;j<n;j++){
            if(i==j) continue;
            frac t=-dp[j][i]/dp[i][i];
            for(int k=i;k<=n;k++)
                dp[j][k]=dp[j][k]+t*dp[i][k];
        }
    }
    
    frac ans=dp[0][n]/dp[0][0];
    cout<<ans.a*rev(ans.b)%mod<<endl;
}
```
:::

### 另解 
> inspired by *ub33*

如果把 $t$ 定義成從第 $i$ 個難關到第 $i+1$ 個難關的期望時間

就可以不用消元，達到 $O(n)$ 的複雜度

:::spoiler code by *konchin.shih* 
```cpp=
constexpr int mod = 1e9+7;

inline ll rev(ll a,ll b=mod-2){
    ll ret=1;
    for(a%=mod;b;b>>=1,a=a*a%mod)
        if(b&1) ret=ret*a%mod;
    return ret;
}

inline void solve() {
    int n;cin>>n;
    ll a,b,c,prev=0,sum=0,cur;
    for(int i=1;i<=n;i++){
        cin>>a>>b>>c;
        b=b*rev(100)%mod;
        c=c*rev(100)%mod;
        cur=(1+prev*rev(i-1)%mod*c)%mod;
        cur=cur*100LL%mod*rev(a)%mod;
        sum=(sum+cur)%mod;
        prev=(prev+cur*i)%mod;
    }
    cout<<sum<<endl;
}
```
:::