ABC 263
2022/8/8 6:24:12
本文主要是介绍ABC 263,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
E.Sugoroku 3(概率 DP)
Problem
一个数轴上标有\(1\)到\(N\),第\(i\)个点有一个骰子,骰子上的数字标号从\(0\)到\(A_i\),在第\(i\)个点上可以投掷骰子,投掷出来的数字代表下一步可以前进多少步,每个数字被投掷出来的概率相同,问从\(1\)号点到\(N\)号点期望投掷骰子多少次,答案对\(998244353\)取模
- \(2\le N\le 2\times 10^5\)
- \(1\le A_i\le N-i\)
- 全部都是正整数
Solve
令\(dp[i]\)表示从\(i\)到\(N\)号点需要投掷骰子的期望次数
概率\(DP\)一般有两种思考方式
- 从终点出发更新前面的状态
- 从起点出发更新后面的状态
这里\(DP\)的定义方法实际上是为了从终点出发更新前面的状态,那么显然有\(dp[N]=0\)
考虑\(i=N-1\text{,}N-2\text{,}\cdots,1\),则有
\[dp[i]=\frac{dp[i]}{A_i+1}+\frac{\sum_{j=1}^{A_i}dp[i+j]}{A_i+1}+1\\ dp[i](1-\frac{1}{A_i+1})=\frac{\sum_{j=1}^{A_i}dp[i+j]}{A_i+1}+1\\ dp[i]=\frac{\sum_{j=1}^{A_i}dp[i+j]}{A_i}+\frac{A_i+1}{A_i} \]注意到\(\sum_{j=1}^{A_i}dp[i+j]\)是一段连续的和,所以可以用前缀和优化
\[dp[i]=\frac{suf[i+1]-suf[i+A_i+1]}{A_i}+\frac{A_i+1}{A_i} \]Code
#include <bits/stdc++.h> #define ll long long using namespace std; const int mod=998244353; ll power(ll x,int y){ ll res=1; while(y){ if(y&1)res=res*x%mod; x=x*x%mod; y>>=1; } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int>A(n+1); for(int i=1;i<n;i++) cin>>A[i]; vector<ll>dp(n+1),suf(n+2); dp[n]=0; for(int i=n-1;i>=1;i--){ ll inv=power(A[i],mod-2); dp[i]=((suf[i+1]-suf[i+A[i]+1]+mod)%mod*inv%mod+(A[i]+1)*inv%mod)%mod; suf[i]=(suf[i+1]+dp[i])%mod; } cout<<dp[1]<<'\n'; return 0; }
F - Tournament
Problem
有\(2^N\)个人,从\(1\)到\(2^N\)标号,进行剪刀石头布的比赛。令\(2M\)表示人的总数,因此有\(M\)对选手,第\(i\)对是标号为\((2i-1)\)和\((2i)\)的人比赛,胜利的人会进行下一场,胜利人的保持彼此之间的编号的相对大小不变继续比赛,知道决出一个人胜利,因此总共有\(N\)次比赛。如果第\(i\)个人获胜\(j\)场会得到\(C_{ij}\)元,请求出\(2^N\)个人可能获得的总钱数的最大值
Solve
这个比赛过程实际上是一棵满二叉树,一开始的状态是从最底下的叶子节点开始,树高为\(N\)
所以考虑树形 DP,令\(dp[i][j]\)表示在第\(i\)号节点获胜的人最终可以获胜\(j\)场的最大收益
不妨假设第\(i\)号节点的左儿子获胜,并且假设到\(i\)号节点进行了\(cnt\)场比赛,那么转移就是\(dp[i][j]=dp[ls][i]+dp[rs][cnt-1]\),由于是左儿子获胜,所以\(i\)号节点要继承左儿子的,而右儿子在这一轮比赛中输掉了,所以在右儿子获胜的人最终只能获胜\(cnt-1\)场就止步于此了,所以用这两个的和来转移即可。根据对称性,右儿子的获胜的转移也是一样的。
Code
#include <bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define ll long long using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<vector<int>> c((1<<n)+1,vector<int>(n+1)); for(int i=1;i<=(1<<n);i++){ for(int j=1;j<=n;j++){ cin>>c[i][j]; } } vector<vector<ll>>dp((1<<(n+1))+1,vector<ll>(n+1)); //2^{n+1}个结点 auto dfs=[&](auto self,int rt,int l,int r,int cnt)->void{ //i,j分别表示左右两边获胜者获胜的场数 if(l==r){ for(int i=1;i<=n;i++) dp[rt][i]=c[l][i]; return ; } int mid=(l+r)>>1; self(self,ls,l,mid,cnt-1); self(self,rs,mid+1,r,cnt-1); for(int i=0;i<=n;i++) dp[rt][i]=max(dp[ls][i]+dp[rs][cnt-1],dp[ls][cnt-1]+dp[rs][i]); }; dfs(dfs,1,1,1<<n,n); cout<<dp[1][n]<<'\n'; }
Ex - Intersection 2(计算集合、二分、极角排序、树状数组)
Problem
给定\(N\)条线段,这\(N\)条线段总共有\(\frac{N(N-1)}{2}\)个交点,并且保证没有两条直线平行。输出距离原点距离第\(K\)大的点的距离。
线段以\(A_ix+B_iy+C_i=0\)的形式给出
- \(2\le N\le 5\times 10^4\),
- \(-1000\le |A_i|,|B_i|,|C_i|\le 1000\)
- \(A_i\ne 0\)或\(B_i\ne 0\)
Solve
考虑二分这个距离的大小,为什么可以二分?若以原点为圆心,二分的距离为半径,显然,半径越大,圆内包含的交点数越多,半径越小,园内包含的交点数越少,具有单调性,所以可以用二分。
接着考虑怎么求圆内的交点个数,我们可以把所有与圆有两个交点的直线的交点先算出来,然后把它们按照极角序排序,选定一个方向,显然,一条直线和其他直线在圆内有交点,当且仅当它的两个交点和其他直线的两个交点是交错的,也就是我们可以统计一条直线会贡献多少个交点,假设这条直线开始与它的某一个交点\(l\),我们在扫到它的另一个端点\(r\)的时候把它的交点贡献加入答案,然后删除它的贡献。
然后直线与圆的交点就用解析法求就好了
Code
#include <bits/stdc++.h> using namespace std; const double eps=1e-8; int sgn(double x){ if(fabs(x)<eps)return 0; else if(x>0) return 1; else return -1; } int dcmp(double x,double y){ if(fabs(x-y)<eps) return 0; else if(x>y)return 1; else return -1; } struct Point{ double x,y; Point(){} Point(double x_,double y_):x(x_),y(y_){} double operator ^ (const Point &t)const{ return x*t.y-y*t.x; } }; bool comp(Point l, Point r) { //极角排序 bool lf = l.y > 0; bool rf = r.y > 0; if (lf != rf) return !lf; if (lf) return l.x > r.x; else return l.x < r.x; //浮点数极角排序用atan2,但复杂度太高了 // if(sgn(atan2(l.y, l.x) - atan2(r.y, r.x)) == 0) //dcmp为判断浮点数是否为0的函数 // return l.x < r.x; // return atan2(l.y, l.x) < atan2(r.y, r.x); } struct Circle{ Point c; double r; Circle(){} Circle(Point c_,double r_):c(c_),r(r_){} }; struct Line{ double A,B,C; Line(){} Line(double A_,double B_,double C_):A(A_),B(B_),C(C_){} }; vector<Point> crosspoint(Circle cir,Line l){ //用解析法求交点 vector<Point> res; double d=abs(l.C)/sqrt(l.A*l.A+l.B*l.B); if(dcmp(d,cir.r)>=0) return res; if(l.A==0){ double y=-l.C/l.B; double x=sqrt(cir.r*cir.r-y*y); res.emplace_back(x,y); res.emplace_back(-x,y); return res; } if(l.B==0){ double x=-l.C/l.A; double y=sqrt(cir.r*cir.r-x*x); res.emplace_back(x,y); res.emplace_back(x,-y); return res; } double a=l.B*l.B+l.A*l.A, b=2*l.A*l.C, c=l.C*l.C-l.B*l.B*cir.r*cir.r; double x1=(-b+sqrt(b*b-4*a*c))/(2*a); double x2=(-b-sqrt(b*b-4*a*c))/(2*a); double y1=(-l.C-l.A*x1)/l.B; double y2=(-l.C-l.A*x2)/l.B; res.emplace_back(x1,y1); res.emplace_back(x2,y2); return res; } const int N=1e5+10; int tr[N]; void add(int p,int x){ p++; for(;p<=100000;p+=p&-p) tr[p-1]+=x; } int ask(int p){ int res=0; for(;p;p-=p&-p) res+=tr[p-1]; return res; } int sum(int l,int r){ return ask(r)-ask(l); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout<<fixed<<setprecision(10); int n,k; cin>>n>>k; vector<Line>line(n+1); for(int i=1;i<=n;i++){ double a,b,c; cin>>a>>b>>c; line[i]=Line(a,b,c); } auto check=[&](Circle c)->int{ vector<pair<Point,int>>v; for(int i=1;i<=n;i++){ auto p=crosspoint(c,line[i]); if(p.size()<2) continue; v.emplace_back(p[0],i); v.emplace_back(p[1],i); } sort(v.begin(), v.end(),[&](pair<Point,int> a,pair<Point,int> b){ return comp(a.first,b.first); }); vector<int>l(n+1,-1); int cnt=0; for(int i=0;i<int(v.size());i++){ int id=v[i].second; if(l[id]==-1){ add(i,1); }else{ add(l[id],-1); cnt+=sum(l[id],i); } l[id]=i; } return cnt; }; double l=0,r=1e9; Point o=Point(0,0); for(int i=1;i<=50;i++){ double mid=(l+r)/2; Circle c=Circle(o,mid); if(check(c)>=k) r=mid; else l=mid; } cout<<l<<'\n'; }
这篇关于ABC 263的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升