8.3
2022/8/4 23:27:24
本文主要是介绍8.3,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CF643C
题意:
有一种电子游戏,它由\(n\)个关卡组成,每个关卡都被赋予了一个值\(t_i\)。
现在,你要将这些关卡分成\(k\)个级别,每个级别\(j\)对应了一段连续的关卡\([l_j,r_j]\),且必有\(l_j\leq r_j\)。任何一个关卡在且仅在一个级别中。
然后,一名玩家将会从第\(1\)个关卡,按顺序一直刷到第\(n\)个关卡。当他打到第\(i\)个关卡时,设这个关卡所在的级别是\(j\),则他有 \(\dfrac{t_i}{\sum\limits_{x=l_j}^{i}t_x}\) 的概率在\(1\)小时内AC这个关卡,然后进入下一关;或者没有AC这个关卡(但仍然花了\(1\)小时),还得再次挑战这个关卡。
你需要找到一种划分方法,使得该玩家期望AK该游戏的期望时间最小。输出这个最小的期望时间。
( $ 1<=n<=200000 $ , $ 1<=k<=min(50,n) $ )
( $ 1<=t_{i}<=100000 $ )
题解:
\(k\)很小,所以可以\(O(nk)\)
考虑这种把一个序列划分成几个连续段的动态规划问题,一般都是斜率优化
列式子
设\(dp[i][k]\)表示前\(i\)个数字,分为\(j\)段的方案数
\(s[i]=\sum_{j=1}^it[i]\)
\(sb[i]=\sum_{j=1}^i\frac{1}{t[j]}\)
\(sc[i]=\sum_{j=1}^i\frac{s[j]}{t[j]}\)
\[dp[i][k]=min\{dp[j][k-1]+\sum_{p=j+1}^i\frac{s[p]-s[j]}{t[p]}\}\\ =min\{dp[j][k-1]+(sc[i]-sc[j])-s[j]*(sb[i]-sb[j])\} \]化成斜率优化的形式
\[dp[j][k-1]-sc[j]+s[j]*sb[j]=sb[i]*s[j]+dp[i][k]-sc[i] \]其中\(y=dp[j][k-1]-sc[j]+s[j]*sb[j],x=s[j],k=sb[i],b=dp[i][k]-sc[i]\)
观察斜率\(sb[i]\)单调增,而且求最小值,所以维护个下凸壳
千万别把段数放在里面循环,这样会导致要开\(k\)个\(sb\)的队列,放到外面循环就只用开一个了
#include<bits/stdc++.h> using namespace std; namespace red{ #define int long long #define double long double #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define lowbit(i) ((i)&(-i)) #define mid ((l+r)>>1) #define eps (1e-15) const int N=200000+10,mod=1e9+7,inv2=5e8+4,inf=1e18; const double pi=acos(-1.0); int n,m; double t[N],s[N]; double st[N],t1[N]; double dp[N][51]; int q[N]; int head,tail; double y(int i,int k) { return dp[i][k]-st[i]+s[i]*t1[i]; } double x(int i) { return s[i]; } double slope(int i,int j,int id) { if(x(i)==x(j)) return y(i,id)>y(j,id)?inf:-inf; return (y(i,id)-y(j,id))/(x(i)-x(j)); } int fcmp(double x,double y) { return fabs(x-y)<=eps?0:x>y?1:-1; } void main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); //(s[i]-s[j-1])/t[i] //dp[i][k]=dp[j][k-1]+st[i]-st[j]-s[j]*(t1[i]-t1[j]) //dp[j][k-1]-st[j]+s[j]*t1[j]=s[j]*t1[i]+dp[i][k]-st[i] cin>>n>>m; for(int i=1;i<=n;++i) { cin>>t[i]; s[i]=s[i-1]+t[i]; st[i]=st[i-1]+1.0*s[i]/t[i]; t1[i]=t1[i-1]+1.0/t[i]; } for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) dp[i][j]=1e18; dp[0][0]=0; for(int k=1;k<=m;++k) { head=1,tail=0; q[++tail]=0; for(int i=1;i<=n;++i) { while(head<tail&& fcmp(slope(q[head+1],q[head],k-1),t1[i] ) <= 0 ) ++head; int j=q[head]; dp[i][k]=dp[j][k-1]+st[i]-st[j]-s[j]*(t1[i]-t1[j]); while(head<tail&& fcmp(slope(i,q[tail-1],k-1),slope(q[tail],q[tail-1],k-1)) <= 0 ) --tail; q[++tail]=i; } } cout<<fixed<<setprecision(10)<<dp[n][m]<<'\n'; } } signed main() { red::main(); return 0; } /* 20 4 25 66 10 18 67 40 66 49 3 51 61 29 10 72 71 22 63 4 74 67 */
CF643E
题意:
给你一棵初始只有根为 \(1\) 的树。
共有 \(q\) 次操作。
1 x
表示加入一个以 \(x\) 为父亲的新点。
2 x
表示求以 \(x\) 为根的子树期望最深深度。
每条边都有 \(\frac{1}{2}\) 的概率断裂。
\(1\leq q\leq 5\times 10^5\)。
误差小于\(1e-6\)
题解:
这题的\(trick\)是误差有限,所以,深度大于\(60\)的概率远小于\(1e-6\),所以答案在\(60\)以内。
设计\(dp\):
\(dp[x][k]\)表示\(x\)节点为根的子树深度不超过\(k\)的概率,不妨认为\(dp[x][60]=1\)
\[dp[x][k]=\prod_{y\in son(x)} \frac{1}{2}(dp[y][k-1]+1) \]这个式子的含义是:要么节点\(x\)的子节点\(y\)深度不超过\(k-1\),要么节点\(x\)和节点\(y\)之间的边断掉,那么深度不超过\(k\)的概率是\(1\)
节点\(x\)的期望深度就是
\[E(x)=\sum_{i=1}^{60}i*(dp[x][i]-dp[x][i-1]) \]每次增加一个点只会修改它的不超过\(60\)级的祖先。
#include<bits/stdc++.h> using namespace std; namespace red{ #define int long long #define double long double #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define lowbit(i) ((i)&(-i)) #define mid ((l+r)>>1) #define eps (1e-15) const int N=5e5+10,mod=1e9+7,inv2=5e8+4,inf=1e18; const double pi=acos(-1.0); int n,m,idx; double dp[N][62]; int f[N]; void main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n;m=61;idx=1; for(int i=1;i<=m;++i) dp[1][i]=1; for(int i=1;i<=n;++i) { int opt,x; cin>>opt>>x; if(opt==1) { f[++idx]=x; for(int k=1;k<=m;++k) dp[idx][k]=1; vector<int> tmp; int k=0,now=idx; while(k<=60&&now) { tmp.emplace_back(now); now=f[now]; ++k; } for(int i=tmp.size()-2;i>0;--i) { dp[tmp[i+1]][i+1]/=(dp[tmp[i]][i]+1)/2.0; //cout<<tmp[i+1]<<"!!"<<'\n'; } for(int i=0;i+1<(int)tmp.size();++i) { dp[tmp[i+1]][i+1]*=(dp[tmp[i]][i]+1)/2.0; } } else { double ans=0; for(int i=1;i<=60;++i) { ans+=i*(dp[x][i]-dp[x][i-1]); } cout<<fixed<<setprecision(10)<<ans-1<<'\n'; } } } } signed main() { red::main(); return 0; } /* 20 4 25 66 10 18 67 40 66 49 3 51 61 29 10 72 71 22 63 4 74 67 */
CF1603C
题意:
对于一个数列,定义一次操作为选择数列中任何一个元素 \(a_i\) ,将这个位置替换成两个正整数 \(x,y\) 满足 \(x+y=a_i\)
定义一个数列的极端值为将这个数列变成不降数列的最小操作次数
给定一个长度为 \(n\) 的数列 \(a\) ( \(1\leq a_i\leq 10^5\) ),让你求它的所有非空子段的极端值之和,对 \(\text{998244353}\) 取模
一个测试点中有多组数据,保证所有数据 \(n\) 的规模总和不超过 \(10^5\)
题解:
考虑一个数字\(x\),如果要划分成最大值不超过\(v\),至少要分\(\lceil\frac{x}{v}\rfloor\)个
然后是尽可能让第一个数字最大
如果要把数字分成\(k\)份,最小值最大是\(\lfloor\frac{x}{k}\rfloor\)
设\(dp[i][x]\)表示从后往前第\(i\)个数字,最前面的元素是\(x\)的答案。
这样可以推出\(O(n^2)\)的做法,就是每次从后往前递推
假设\(y\in[l,r]\),满足\(\lfloor\frac{a[i]}{\lceil\frac{a[i]}{y}\rceil}\rfloor=x\)
那么有转移
\[dp[i][x]=\sum_{y=l}^rdp[i+1][y]*i*(\lceil\frac{a[i]}{y}\rceil-1) \]解释下式子,前面还有\(i\)个子区间包含这个位置,这个位置贡献了\((\lceil\frac{a[i]}{y}\rceil-1)\)次分裂
因为上式是一个向下取整的形式,所以每次转移来的不同\(x\)其实只有\(\sqrt{10^5}\)个,转移的复杂度应该是\(O(n\sqrt{N})\)
#include<bits/stdc++.h> using namespace std; namespace red{ #define int long long #define double long double #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define lowbit(i) ((i)&(-i)) #define mid ((l+r)>>1) #define eps (1e-15) const int N=1e5+10,mod=998244353,inv2=5e8+4,inf=1e18; const double pi=acos(-1.0); int n; vector dp(2,vector<int>(N)); void main() { cin>>n; vector<int> a(n+1); for(int i=1;i<=n;++i) { cin>>a[i]; } int opt=0,ans=0; vector v(2,vector<int>()); for(int i=n;i>=1;--i) { opt^=1; v[opt].emplace_back(a[i]); dp[opt][a[i]]=1; int pre=a[i]; for(auto x:v[opt^1]) { int y=dp[opt^1][x]; int t1=(a[i]+x-1)/x; int t2=a[i]/t1; ans=(ans+i*(t1-1)%mod*y%mod)%mod; dp[opt][t2]+=y; dp[opt][t2]%=mod; if(t2!=pre) v[opt].emplace_back(t2),pre=t2; } for(auto x:v[opt^1]) dp[opt^1][x]=0; v[opt^1].clear(); } for(auto x:v[opt]) dp[opt][x]=0; cout<<ans<<'\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int qwq=1;cin>>qwq; while(qwq--) red::main(); return 0; } /* 20 4 25 66 10 18 67 40 66 49 3 51 61 29 10 72 71 22 63 4 74 67 */
这篇关于8.3的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行