HGOI20191115 模拟赛 题解
Problem A 表演
有$n$个有点权的点，$m$个有边权的边。对于每个点$u$，输出从这个点出发到$v$，其路径权值的两倍加上v的点权和最小的值。
对于$100\%$的数据，满足$1 leq n,m leq 2 imes 10^5 $
Solution :
考虑一个简单的转移，$f[u]$表示点$u$的最小答案，最初$f[u]$ 为$u$的点权。
每一次更新，就是相邻的两个点$u,v$之间，用边权的两倍来更新答案。
如果在图上DP，那么就相当于，将初始这些点权加入priority_queue，跑最短路即可。
时间复杂度为$O(m log_2 n)$
# include <bits/stdc++.h> # define int long long using namespace std; const int N=2e5+10; struct rec{ int pre,to,w;}a[N<<1]; int n,m,tot; bool inq[N]; int head[N],d[N],val[N]; namespace Fast_IO { inline int read() { int x=0,w=0; char c=0; while (c<'0'||c>'9') w|=c=='-',c=getchar(); while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return w?-x:x; } void write(int x) { if (x<0) x=-x,putchar('-'); if (x>9) write(x/10); putchar('0'+x%10); } void writeln(int x) { write(x); putchar(' '); } }; using namespace Fast_IO; void adde(int u,int v,int w) { a[++tot].pre=head[u]; a[tot].to=v; a[tot].w=w*2; head[u]=tot; } struct Node { int id,val; }; struct cmp { bool operator () (Node a,Node b) { return a.val > b.val; } }; priority_queue<Node,vector<Node>,cmp>q; void dijkstra() { for (int i=1;i<=n;i++) { d[i]=val[i]; inq[i]=true; q.push((Node){i,val[i]}); } while (q.size()) { int u=q.top().id; q.pop(); inq[u]=false; for (int i=head[u];i;i=a[i].pre) { int v=a[i].to; if (d[v]>d[u]+a[i].w) { d[v]=d[u]+a[i].w; if (!inq[v]) q.push((Node){v,d[v]}); } } } } signed main() { n=read();m=read(); for (int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); adde(u,v,w); adde(v,u,w); } for (int i=1;i<=n;i++) val[i]=read(); dijkstra(); for (int i=1;i<n;i++) write(d[i]),putchar(' '); writeln(d[n]); return 0; }
Problem B 逮虾户
要求的车速是一个大于等于0的值，设第$i$次估计的车速为$v_i$,走的路程为$s_i$，
设$v'$表示真实速度，则有偏差值$d$的定义式为 $d = v' - v_i$。
考虑对速度的估计的偏差值d每一次都恒定。
给出$n$次测算的结果$s_i , v_i$，和这几次测试总共的用时$t$，输出$d$的值。
对于$100\%$的数据满足$1 leq nleq 10^3,1 leq s_i leq 10^3 , |v_i| leq 10^3$
Solution :
考虑$t$这个函数是在$n+1$段不连续的定义域中单调减的。
所以，我们可以做$n+1$二分，就能找到些定义域中和d最相近的。
、 注意，最后统计答案的时候，需要check一下实际车速大于等于0.
时间复杂度为$O(n ^2 log_2 S)$，其中$S$表示确定实数域大小。
# include <bits/stdc++.h> using namespace std; const int N=1e3+10; const double eps = 1e-9; struct rec{double s,v;}a[N]; int n,t; vector<double>ans; bool cmp (rec x, rec y) { return x.v>y.v; } double f (double x) { double res = 0; for (int i=1;i<=n;i++) res += (double)a[i].s/(double)(x+a[i].v); return res; } double work(double l,double r) { while (fabs(r-l)>=eps) { double mid = (l+r)/2.0; if (f(mid)<=t) r=mid; else l=mid; } return l; } double calc(double x) { return fabs(f(x)-t); } int main() { scanf("%d%d",&n,&t); for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].s,&a[i].v); sort(a+1,a+1+n,cmp); double l=-1e9; for (int i=1;i<=n;i++) { ans.push_back(work(l,-a[i].v-eps)); l=-a[i].v+eps; } ans.push_back(work(l,1e9)); double res = ans[0], delta =calc(ans[0]); for (int i=1;i<ans.size();i++) { bool ok = true; for (int j=1;j<=n;j++) if (a[j].v+ans[i]<eps) { ok = false; break; } if (!ok) continue; double tmp = calc(ans[i]); if (tmp <= delta) { res = ans[i]; delta = tmp; } } printf("%.10lf ",res); return 0; }