---
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;
}
```
:::
Sign in with Wallet
Connect another wallet