2021.7.15考试总结[NOIP模拟16]
2024-09-06 05:50:16
ZJ模拟D2就是NB。。
T1 Star Way To Heaven
谁能想到这竟是个最小生成树呢？（T1挂分100的高人JYF就在我身边
把上边界和下边界看成一个点和星星跑最小生成树，从上边界开始跑到下边界，一定会出现一条将矩阵纵向一分为二的折线，其中线段都是最小距离，答案就是其中最长的线段的一半。
我直呼NB
由于这是个完全图，kruscal比prim多个log，会炸。
code：
1 #include<bits/stdc++.h>
2 #define debug exit(0)
3 using namespace std;
4 const double eps=1e-8;
5 const int NN=6e3+5;
6 int n,m,k,nod;
7 double ans,dis[NN],x[NN],y[NN];
8 bool vis[NN];
9 inline int read(){
10 int x=0,f=1;
11 char ch=getchar();
12 while(ch<'0'||ch>'9'){
13 if(ch=='-') f=-1;
14 ch=getchar();
15 }
16 while(ch>='0'&&ch<='9'){
17 x=(x<<1)+(x<<3)+(ch^48);
18 ch=getchar();
19 }
20 return x*f;
21 }
22 double ds(int a,int b){
23 return sqrt(1.0*(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
24 }
25 int main(){
26 n=read(); m=read(); k=read();
27 for(int i=1;i<=k;i++)
28 x[i]=read(), y[i]=read();
29 for(int i=1;i<=k;i++)
30 dis[i]=m-y[i];
31 dis[k+1]=m; dis[0]=1e9;
32 while(1){
33 int to=0;
34 for(int i=1;i<=k+1;i++)
35 if(!vis[i]&&dis[i]<dis[to]) to=i;
36 ans=max(ans,dis[to]); vis[to]=1;
37 if(to==k+1){
38 printf("%.8lf\n",ans/2);
39 return 0;
40 }
41 for(int i=1;i<=k;i++)
42 dis[i]=min(dis[i],ds(i,to));
43 dis[k+1]=min(dis[k+1],1.0*y[to]);
44 }
45 }
T1
T2 God Knows
用B哥的话说，第一眼DP，第二眼不会。
看这题满脑子状压，但数据范围无情地把我拉回现实。
又想了一会树规，但假了。无奈之下，还是不想打状压，一调一小时于是果断糊了个DFS拿了20。
正解是个NB东西。把p看作带权序列，问题转化成求最小权极长上升子序列。
n2无法过掉，考虑神仙优化。如何优化呢？
万能的线段树！
发现能更新dpi的j满足它的p是从j到i中所有小于pi的最大值，但仍难以维护。
于是可以在线段树中维护以p为下标，i为关键值的一个单调栈。那么又到了我不懂的东西。
在每个节点上维护一个单调栈，记录栈底元素（i最大值），其中最小的权值（即为dp数组），和左儿子被右儿子最大值更新后的最小权值。
写一个cal函数计算当前节点的栈中加入关键值为val的元素后的最小权值。
用一个nxt计接下来要向栈中压进的元素，因为要把右儿子栈底压进左边，每次查询先询问右边来得到接下来询问范围。
code：
1 #include<bits/stdc++.h>
2 #define ld rt<<1
3 #define rd (rt<<1)|1
4 #define debug exit(0)
5 using namespace std;
6 const int NN=2e5+5,inf=2e9;
7 int n,p[NN],c[NN],nxt;
8 inline int Min(int a,int b){ return a<b?a:b; }
9 inline int Max(int a,int b){ return a<b?b:a; }
10 inline int read(){
11 int x=0,f=1;
12 char ch=getchar();
13 while(ch<'0'||ch>'9'){
14 if(ch=='-') f=-1;
15 ch=getchar();
16 }
17 while(ch>='0'&&ch<='9'){
18 x=(x<<1)+(x<<3)+(ch^48);
19 ch=getchar();
20 }
21 return x*f;
22 }
23 void write(int x){
24 if(x<0) putchar('-'), x=-x;
25 if(x>9) write(x/10);
26 putchar(x%10+'0');
27 }
28 struct segment_tree{
29 int l[NN<<2],r[NN<<2],mn[NN<<2],um[NN<<2],mx[NN<<2];
30 int cal(int rt,int val){
31 if(l[rt]==r[rt]) return mx[rt]>val?mn[rt]:inf;
32 if(mx[rd]>val) return Min(um[ld],cal(rd,val));
33 return cal(ld,val);
34 }
35 void pushup(int rt){
36 mx[rt]=Max(mx[ld],mx[rd]);
37 mn[rt]=Min(mn[rd],um[ld]=cal(ld,mx[rd]));
38 }
39 void build(int rt,int opl,int opr){
40 l[rt]=opl; r[rt]=opr;
41 mn[rt]=um[rt]=inf; mx[rt]=-1;
42 if(opl==opr) return;
43 int mid=opl+opr>>1;
44 build(ld,opl,mid); build(rd,mid+1,opr);
45 }
46 int query(int rt,int opl,int opr){
47 if(l[rt]>=opl&&r[rt]<=opr){
48 int ans=cal(rt,nxt);
49 nxt=Max(nxt,mx[rt]);
50 return ans;
51 }
52 int mid=l[rt]+r[rt]>>1,ans=inf;
53 if(opr>mid) ans=Min(ans,query(rd,opl,opr));
54 if(opl<=mid) ans=Min(ans,query(ld,opl,opr));
55 return ans;
56 }
57 void insert(int rt,int pos,int i,int val){
58 if(l[rt]==r[rt]){ mn[rt]=val; mx[rt]=i; return; }
59 int mid=l[rt]+r[rt]>>1;
60 if(pos<=mid) insert(ld,pos,i,val);
61 else insert(rd,pos,i,val);
62 pushup(rt);
63 }
64 }s;
65 int main(){
66 n=read();
67 for(int i=1;i<=n;i++) p[i]=read();
68 for(int i=1;i<=n;i++) c[i]=read();
69 ++n; p[n]=n; s.build(1,0,n); s.insert(1,0,0,0);
70 for(int i=1;i<=n;i++){
71 nxt=-1;
72 int tmp=s.query(1,0,p[i]-1)+c[i];
73 s.insert(1,p[i],i,tmp);
74 if(i==n) write(tmp), putchar('\n');
75 }
76 return 0;
77 }
T2
T3 Lost My Music
一看就是个斜率，但我没学
用单调栈（可持久化）维护一个下凸包，每次求凸包切线。
暴力弹栈会炸，于是学着用了个倍增。代码挺短
贴个斜率优化博客
code：
1 #include<bits/stdc++.h>
2 #define debug exit(0)
3 using namespace std;
4 const double eps=1e-8;
5 const int NN=5e5+5;
6 int n,fa[NN][21],to[NN],nex[NN],head[NN],num,dep[NN],ans[NN],c[NN];
7 inline int read(){
8 int x=0,f=1;
9 char ch=getchar();
10 while(ch<'0'||ch>'9'){
11 if(ch=='-') f=-1;
12 ch=getchar();
13 }
14 while(ch>='0'&&ch<='9'){
15 x=(x<<1)+(x<<3)+(ch^48);
16 ch=getchar();
17 }
18 return x*f;
19 }
20 inline void add(int a,int b){
21 to[++num]=b; nex[num]=head[a]; head[a]=num;
22 }
23 inline double Min(double a,double b){
24 return a<b?a:b;
25 }
26 inline double calc(int x,int y){
27 return 1.0*(c[y]-c[x])/(dep[x]-dep[y]);
28 }
29 void dfs(int st){
30 int father=fa[st][0];
31 for(int i=19;i>=0;i--){
32 if(fa[father][i]<2) continue;
33 if(calc(st,fa[father][i])>=calc(st,fa[fa[father][i]][0])) father=fa[father][i];
34 }
35 if(calc(st,father)>=calc(st,fa[father][0])&&father>1) father=fa[father][0];
36 ans[st]=fa[st][0]=father;
37 for(int i=1;i<=19;i++)
38 fa[st][i]=fa[fa[st][i-1]][i-1];
39 for(int i=head[st];i;i=nex[i]){
40 dep[to[i]]=dep[st]+1;
41 dfs(to[i]);
42 }
43 }
44 int main(){
45 n=read();
46 for(int i=1;i<=n;i++) c[i]=read();
47 for(int i=2;i<=n;i++){
48 fa[i][0]=read();
49 ans[i]=1e9+1e7;
50 add(fa[i][0],i);
51 }
52 dfs(1);
53 for(int i=2;i<=n;i++)
54 printf("%.10lf\n",calc(i,ans[i]));
55 return 0;
56 }
T3
最新文章
- docker学习
- Linux(五)__硬盘分区
- [译]git的那些flag
- pe创建激活administrator后消除问题，删除用户问题
- office 2010 2013卸载工具
- wp8 入门到精通 启动系统分享照片任务
- IntelliJ IDEA中怎么查看方法说明？
- JS正则表达式验证账号、手机号、电话、邮箱、货币
- 【转】DynDNS使用随笔
- Bug跟踪的流程
- unity 本地帮助文档 慢
- python中的深拷贝和浅拷贝理解
- 数据压缩算法---LZ77算法 的分析与实现
- win10电脑安装win7
- php中一个"异类"语法： $a && $b = $c; 【转载】
- 背水一战 Windows 10 (99) - 关联启动: 关联指定的文件类型, 关联指定的协议
- [转]boost::python开发环境搭建
- ZOJ 3632 ----dp+优先队列
- Java之Https请求
- JAVA框架 Mybaits 一对一、一对多