HGOI20191115 模拟赛 题解
阅读原文时间:2023年07月10日阅读:2

Problem A 表演

有$n$个有点权的点,$m$个有边权的边。对于每个点$u$,输出从这个点出发到$v$,其路径权值的两倍加上v的点权和最小的值。

对于$100\%$的数据,满足$1 \leq n,m \leq 2\times 10^5 $

Solution :

  考虑一个简单的转移,$f[u]$表示点$u$的最小答案,最初$f[u]$ 为$u$的点权。

  每一次更新,就是相邻的两个点$u,v$之间,用边权的两倍来更新答案。

  如果在图上DP,那么就相当于,将初始这些点权加入priority_queue,跑最短路即可。

  时间复杂度为$O(m log_2 n)$

# include

define int long long

using namespace std;
const int N=2e5+;
struct rec{ int pre,to,w;}a[N<<]; int n,m,tot; bool inq[N]; int head[N],d[N],val[N]; namespace Fast_IO { inline int read() { int x=,w=; char c=; while (c<''||c>'') w|=c=='-',c=getchar();
while (c>='' && c<='') x=(x<<)+(x<<)+(c^),c=getchar(); return w?-x:x; } void write(int x) { if (x<) x=-x,putchar('-'); if (x>) write(x/);
putchar(''+x%);
}
void writeln(int x) {
write(x); putchar('\n');
}
};
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*;
head[u]=tot;
}
struct Node {
int id,val;
};
struct cmp {
bool operator () (Node a,Node b) {
return a.val > b.val;
}
};
priority_queue,cmp>q;
void dijkstra() {
for (int i=;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=;i<=m;i++) {
int u=read(),v=read(),w=read();
adde(u,v,w); adde(v,u,w);
}
for (int i=;i<=n;i++) val[i]=read();
dijkstra();
for (int i=;i<n;i++) write(d[i]),putchar(' ');
writeln(d[n]);
return ;
}

exciting.cpp

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 n\leq 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
using namespace std;
const int N=1e3+;
const double eps = 1e-;
struct rec{double s,v;}a[N];
int n,t;
vectorans;
bool cmp (rec x, rec y) {
return x.v>y.v;
}
double f (double x) {
double res = ;
for (int i=;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=;i<=n;i++) scanf("%lf%lf",&a[i].s,&a[i].v);
sort(a+,a++n,cmp);
double l=-1e9;
for (int i=;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[], delta =calc(ans[]);
for (int i=;i<ans.size();i++) {
bool ok = true;
for (int j=;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\n",res);
return ;
}

dejavu.cpp

Problem C 跳一跳

如果序列中任意相邻两个元素,都是极值点,其中一个是极大值点,另外一个极小值点。

   那么这个序列叫做波浪序列。

  给出对于长度为$n$序列,输出最长波浪序列的长度。

  对于$100\%$的数据满足 $1 \leq n \leq 10^5 , 1 \leq a_i \leq 10^9 $

Solution :

  由于元素只进行比较,所以我们可以将其离散化。

  设$f[i][0]$表示第$i$个元素作为极小点为结尾的最长波浪序列长度,$f[i][1]$表示第$i$个元素作为极大点为结尾的最长波浪序列长度。

  转移方程为:$f[i][0] = max(f[j][1] + 1) (a_i < a_j) , f[i][1] = max (f[j][0] + 1) (a_i > a_j)$

  可以用值域线段树来维护这个$DP$。时间复杂度为$O(n log_2 n)$

# include
using namespace std;
const int N=1e5+;
int a[N],n,f[N][];
vectortmp;
namespace Fast_IO {
inline int read() {
int x=,w=; char c=;
while (c<''||c>'') w|=c=='-',c=getchar();
while (c>='' && c<='') x=(x<<)+(x<<)+(c^),c=getchar(); return w?-x:x; } void write(int x) { if (x<) x=-x,putchar('-'); if (x>) write(x/);
putchar(''+x%);
}
void writeln(int x) {
write(x); putchar('\n');
}
};
using namespace Fast_IO;
struct Segment_Tree {
int tr[N<<]; # define ls (x<<) # define rs (x<<|) # define mid (l+r>>)
# define lson ls,l,mid
# define rson rs,mid+,r
void update(int x,int l,int r,int pos,int opx) {
if (l==r) {
tr[x]=max(tr[x],opx);
return;
}
if (pos<=mid) update(lson,pos,opx); else update(rson,pos,opx); tr[x]=max(tr[ls],tr[rs]); } int query(int x,int l,int r,int opl,int opr) { if (opl<=l && r<=opr) return tr[x]; int ret=; if (opl<=mid) ret=max(ret,query(lson,opl,opr)); if (opr>mid) ret=max(ret,query(rson,opl,opr));
return ret;
}
}tr0,tr1;
int main() {

n=read();  
for (int i=;i<=n;i++) {  
    tmp.push\_back(a\[i\]=read());  
}  
sort(tmp.begin(),tmp.end());  
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());  
int m = tmp.size();  
for (int i=;i<=n;i++) {  
    a\[i\]=lower\_bound(tmp.begin(),tmp.end(),a\[i\])-tmp.begin()+;  
}  
int ans = ;  
for (int i=;i<=n;i++) {  
    f\[i\]\[\]=f\[i\]\[\]=;  
    if (a\[i\]->=) f\[i\]\[\] = max(f\[i\]\[\],tr0.query(,,m,,a\[i\]-)+);  
    if (a\[i\]+<=m) f\[i\]\[\] = max(f\[i\]\[\],tr1.query(,,m,a\[i\]+,m)+);  
    ans = max(ans,max(f\[i\]\[\],f\[i\]\[\]));  
    tr0.update(,,m,a\[i\],f\[i\]\[\]);  
    tr1.update(,,m,a\[i\],f\[i\]\[\]);  
}  
writeln(ans);  
return ;  

}

jump.cpp