500 C

題意

給你一個(gè)棧，棧中有若干個(gè)帶權(quán)的元素，開始時(shí)有 \(n\) 個(gè)元素 \(1-n\) ，你可以進(jìn)行以下操作：

• 將元素 \(x(x\in [1,n])\) 取出棧，花費(fèi)為在 \(x\) 上面所有元素的權(quán)值和，再將 \(x\) 放在棧頂

現(xiàn)在給你一個(gè) \(x\) 序列，問怎么安排初始的棧使花費(fèi)最小。
\((n\le 10^5)\)

Examples

input
3 5
1 2 3
1 3 2 3 1
output
12

解

考慮貪心，將先取的書放在上面。

500 D

題意

有一棵樹，有邊權(quán)，現(xiàn)在隨機(jī)選擇一個(gè)三元組 \((x,y,z)\) 花費(fèi)為 \(dis(x,y)+dis(y,z)+dis(z,x)\) ，求三元組花費(fèi)的期望。
\((n\le 10^5)\)

Examples

input
3
2 3 5
1 3 3
5
1 4
2 2
1 2
2 1
1 1
output
14.0000000000
12.0000000000
8.0000000000
6.0000000000
4.0000000000
input
6
1 5 3
5 3 2
6 1 7
1 4 4
5 2 3
5
1 2
2 1
3 5
4 1
5 2
output
19.6000000000
18.6000000000
16.6000000000
13.6000000000
12.6000000000

解

對于這種題最好的方法是找規(guī)律
通過一番尋找，我們發(fā)現(xiàn)每條邊對答案的貢獻(xiàn)為 \(\frac{邊的兩個(gè)端點(diǎn)的兩顆子樹大小的乘積*(n-2)}{C^{n}_{3}}\)
注意這道題某些中間過程能讓long long都炸掉，開double

500 E

題意

在坐標(biāo)軸上有 \(n\) 個(gè)多米諾骨牌，原理如圖

現(xiàn)在你可以給每一個(gè)骨牌的長度 \(+1\)
現(xiàn)在有 \(m\) 組詢問，問從 \(x\) 到 \(y\) 最少需要 \(+1\) 多少次
\((n,m\le 10^5)\)

Examples

input
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6
output
0
1
1
2

解

把多米諾骨牌平攤在 \(x\) 軸上，然后把相交的骨牌連在一個(gè)聯(lián)通塊里，從后往前掃，用單調(diào)棧維護(hù)。詢問需離線。

Code

#include<bits/stdc++.h> #define maxn 200003 #define INF 1050000000 using namespace std; int n,Q,top,stk[maxn],f[maxn],sum[maxn],L[maxn],R[maxn],ans[maxn]; struct data{int x,len;}a[maxn]; struct QQ{int l,r,num;bool operator <(const QQ& x)const{return l<x.l;}}q[maxn]; int find(int x){return x!=f[x]?f[x]=find(f[x]):f[x];} void Union(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy)f[fx]=fy;} int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].len);scanf("%d",&Q);for(int i=1;i<=Q;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i;sort(q+1,q+Q+1);for(int i=1;i<=n+1;i++)f[i]=i;L[n+1]=a[n].x+a[n].len;for(int i=n,j=Q;i>=1;i--){while(top&&a[i].x+a[i].len>=a[stk[top]].x+a[stk[top]].len)Union(i,stk[top]),top--;if(top&&a[i].x+a[i].len>=a[stk[top]].x)Union(i,stk[top]);int now=find(i),nxt=find(find(i)+1);if(now==i){R[now]=a[i].x+a[i].len;sum[now]=sum[nxt]+L[nxt]-R[now];}else{R[now]=max(R[now],a[i].x+a[i].len);sum[now]=min(sum[now],sum[nxt]+L[nxt]-R[now]);}L[now]=a[i].x;for(now=find(q[j].l);j>=1&&q[j].l>=i;j--){nxt=find(q[j].r);ans[q[j].num]=sum[now]-sum[nxt];}stk[++top]=i;}for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/BlogOfchc1234567890/p/10618999.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 500的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。