\(noip模拟16\;solutions\)
hhhh只拿了100pts，10+40+50;
考试场面请自行脑补，脑子快要烧烂了，咋想也想不出来。。。
没啥感想，这次时间分配还是挺均匀的！！！
\(T1\;\;Star\,Way\,To\,Heaven\)
这第一题就挺悲惨的，上来就干到天堂去了，害，我真心疼这小孩！！！<笑哭><笑哭>
可以说我读题还是挺准确的，找到最小距离的最大值，这个自己理解题意吧，就是让这个最小值最大
要从左边走到右边，一定要经过一条可以将这个图分成左右两半的路径，而这条路径上的最大值就是你的答案
我们需要找最小生成树，为什么是最小？因为只有最小的时候，才能保证我经过这个分界线之后，不会再次经过别的比它还小的值
这个是一个完全图，我们将上界看作0节点，下界看作k+1节点，在这个完全图中跑prime
不会自己去百度。。。但是这里还有一个细节，当你连上到k+1的边的时候就要停止，不然答案会被更大的更新
这个正确性是显然的，边是无序的，后面的边是有可能比当前的大的
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=6005;
int n,m,k;
double ans,low[N];
double x[N],y[N];
double dis(int a,int b){
if(a==0)return y[b];
if(b==k+1)return m-y[a];
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
bool vis[N];
signed main(){
scanf("%d%d%d",&n,&m,&k);
for(re i=1;i<=k;i++)scanf("%lf%lf",&x[i],&y[i]);
vis[0]=1;y[0]=0;y[k+1]=m;
for(re i=1;i<=k+1;i++)low[i]=dis(0,i);//cout<<low[i]<<" ";
for(re i=1;i<=k;i++){
double minn=1000100.0;
int who;
for(re j=1;j<=k+1;j++){
if(vis[j])continue;
if(low[j]<minn)minn=low[j],who=j;
}
vis[who]=i;
//cout<<who<<endl;
ans=max(ans,minn);
if(who==k+1){
printf("%.10lf",ans/2.0);
return 0;
}
for(re j=1;j<=k+1;j++){
if(vis[j])continue;
low[j]=min(low[j],dis(who,j));
//cout<<low[j]<<endl;
}
}
printf("%.10lf",ans/2.0);
}
·
\(T2\;God\,Knows\)
这个题我的思路还是极其清晰的，首先我虽然不知道这是个极长上升子序列，但是我推出来的是一样的，只是不知道这个名字而已
所以我考场上打出来一个\(O(n^2)\)的算法，我还对原序列分了个块其实没啥用，可能可以快那么亿点点点
如果直接\(n^2\)的话，只有40pts，而我把它拆成若干个互不相干的块，就有了60pts，毕竟我的\(n^2\)远小于那个
为什么可以分块，因为这些块之间互不影响，就根据他们之间有没有联系来分块，当出现一条线两侧没有线相连的时候，就可以分成一个块
暴力_60pts
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=2e5+5;
int n;
int p[N],q[N],c[N];
int bl[N],cnt;
int kus[N][2];
int dp[N],ans;
int sol(int x){
int ret=0x3f3f3f3f;
int tmp=0x3f3f3f3f;
for(re i=kus[x][0];i<=kus[x][1];i++){
if(p[i]>tmp)continue;
dp[i]=c[i];tmp=p[i];
}
for(re i=kus[x][0];i<=kus[x][1];i++){
tmp=0;
for(re j=i-1;j>=kus[x][0];j--){
if(p[j]<tmp||p[j]>p[i])continue;
tmp=p[j];
dp[i]=min(dp[i],dp[j]+c[i]);
}
}
tmp=0;
for(re i=kus[x][1];i>=kus[x][0];i--){
if(p[i]<tmp)continue;
tmp=p[i];
ret=min(ret,dp[i]);
}
return ret;
}
signed main(){
scanf("%d",&n);memset(dp,0x3f,sizeof(dp));
for(re i=1;i<=n;i++)scanf("%d",&p[i]),q[p[i]]=i;
for(re i=1;i<=n;i++)scanf("%d",&c[i]);
for(re i=1;i<=n;i++){
kus[++cnt][0]=i;
kus[cnt][1]=p[i];
for(re j=i+1;j<=kus[cnt][1]&&j<=n;j++){
if(j<=kus[cnt][1])kus[cnt][1]=max(kus[cnt][1],p[j]);
if(p[j]<=kus[cnt][1])kus[cnt][1]=max(kus[cnt][1],j);
}
i=kus[cnt][1];
}
//for(re i=1;i<=cnt;i++)cout<<kus[i][0]<<" "<<kus[i][1]<<endl;
for(re i=1;i<=cnt;i++){
ans+=sol(i);
}
printf("%d",ans);
}
·
然后题解直接告诉我线段树优化一下就好了，我\(TM\)也是服了，我要是自己能想出来，我不就\(AC\)了？？
有人告诉我叫啥李超线段树。我也不知道，直接上网找代码，找代码之前我已经有了一点点思路
看到一个口胡标记的博客，直接看了他的解释，其实我只吸取了他的前半部分
如何用线段树维护极长上升子序列?？？我们先观察这些序列我们发现，如果将所有可以用来更新后面序列的点放到一个栈里
这个栈的\(i\)是递增的，而\(p[i]\)是递减的且\(p[i]<p[now]\)，所以我们根据这个性质，对\(p[i]\)建立一颗线段树
每次插入时更新当前节点的极长上升序列的最小值，
线段树一共维护2个值，终点在当前区间的极长上升子序列的最小值，就是暴力代码中的\(dp[i]\);
还有一个当前区间最大的i，注意这里线段树区间是指\(p[i]\)，而i指的是i，
\(query\)的时候，找<=p[i]-1的最小值，然后更新答案，这里会很麻烦
因为可以更新i点构成一个单调序列，我们从\(p[i]\)的右边向左扫，也就是从线段树的右边向左扫
那么\(p[i]\)在这个过程中就是递减的，那么我们就要求i是递增的，所以我们维护一个\(maxd\)来存储能够进入栈中的i的最小值
在我们不断在线段树中扫的过程中，这个\(maxd\)是要不断更新的，这样就可以\(O(nlogn)\)(其实是假的)解决这个问题
那我们如何在线段树中从右向左扫呢？？我们首先找到一个在线段树上的完整区间，注意一般线段树都会先左儿子后右儿子
这里我们先扫右儿子再扫左儿子，因为我们要从右向左扫嘛。
将这个完整区间放到一个\(work\)函数中，其实也就相当于O(n)扫一遍，所以我说这个复杂度是假的，最慢会被卡到\(O(n^2logn)\)
假复杂度的线段树
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int inf=0x3f3f3f3f;
const int N=2e5+5;
int n,c[N],p[N],maxd;
struct seg_tree{
#define ls x<<1
#define rs x<<1|1
int mndp[N*8],mxra[N*8];
int work(int x,int l,int r,int maxn){
if(l==r){
if(mxra[x]>maxn)return mndp[x];
else return inf;
}
int mid=l+r>>1;
if(maxn>mxra[x])return inf;
else if(maxn>mxra[rs])return work(ls,l,mid,maxn);
else{
int ret=inf;
ret=min(ret,work(rs,mid+1,r,maxn));
ret=min(ret,work(ls,l,mid,mxra[rs]));
return ret;
}
//上面三个判断是减小复杂度的关键，让这个复杂度没那么假
}
inline void up(int x,int l,int r){
mxra[x]=max(mxra[ls],mxra[rs]);
}
void build(int x,int l,int r){
mndp[x]=inf;
if(l==r)return ;
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
return ;
}
void ins(int x,int l,int r,int pos,int i,int v){
if(l==r){
mxra[x]=i;
mndp[x]=v;
return ;
}
int mid=l+r>>1;
if(pos<=mid)ins(ls,l,mid,pos,i,v);
else ins(rs,mid+1,r,pos,i,v);
up(x,l,r);return ;
}
int query(int x,int l,int r,int pos){
if(r<=pos){
int ret=work(x,l,r,maxd);
maxd=max(mxra[x],maxd);
return ret;
}
if(l==r){
//cout<<"sb"<<endl;
return 0;
}
int mid=l+r>>1,ret=inf;
if(pos>mid)ret=min(ret,query(rs,mid+1,r,pos));
ret=min(ret,query(ls,l,mid,pos));
return ret;
}
#undef ls
#undef rs
}xds;
int dp[N];
signed main(){
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d",&p[i]);
for(re i=1;i<=n;i++)scanf("%d",&c[i]);
xds.build(1,1,n);
for(re i=1;i<=n;i++){
maxd=0;
int tmp=xds.query(1,1,n,p[i]-1);
if(tmp==inf)dp[i]=c[i];
else dp[i]=tmp+c[i];
xds.ins(1,1,n,p[i],i,dp[i]);
}
maxd=0;
printf("%d",xds.query(1,1,n,n));
}
那么我们怎么把这个复杂度弄成真的呢?
我们发现，在一个区间中，左儿子的\(maxd\)(就是对左儿子中可以用来更新的点的i的要求)，一定是大于右区间的mxra的
大于当前右区间中的i的最大值，这样才可以保证递增，
这样的话，我们就可以用\(mndp[x]\)来记录当前区间的左儿子的最小值，那么就可以直接得到答案
这样的线段树的时间复杂度是均摊的；
我们只需要在up中加入对\(mndp\)值的更新，将\(work\)函数中对左儿子的递归改成\(mndp\)就好了
均摊复杂度的线段树
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int inf=0x3f3f3f3f;
const int N=2e5+5;
int n,c[N],p[N],maxd;
struct seg_tree{
#define ls x<<1
#define rs x<<1|1
int mndp[N*8],mxra[N*8];
int work(int x,int l,int r,int maxn){
if(l==r){
if(mxra[x]>maxn)return mndp[x];
else return inf;
}
int mid=l+r>>1;
if(maxn>mxra[x])return inf;
else if(maxn>mxra[rs])return work(ls,l,mid,maxn);
else{
int ret=inf;
ret=min(ret,work(rs,mid+1,r,maxn));
ret=min(ret,mndp[x]);
return ret;
}
}
inline void up(int x,int l,int r){
mxra[x]=max(mxra[ls],mxra[rs]);
mndp[x]=work(ls,l,l+r>>1,mxra[rs]);
}
void build(int x,int l,int r){
mndp[x]=inf;
if(l==r)return ;
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
return ;
}
void ins(int x,int l,int r,int pos,int i,int v){
if(l==r){
mxra[x]=i;
mndp[x]=v;
return ;
}
int mid=l+r>>1;
if(pos<=mid)ins(ls,l,mid,pos,i,v);
else ins(rs,mid+1,r,pos,i,v);
up(x,l,r);//cout<<"ins "<<l<<" "<<r<<" "<<x<<" "<<mxra[x]<<endl;
return ;
}
int query(int x,int l,int r,int pos){
//cout<<"query "<<x<<" "<<l<<" "<<r<<" "<<endl;
if(r<=pos){
//cout<<"work "<<x<<" "<<l<<" "<<r<<" "<<maxd<<" "<<mxra[x]<<endl;
/*if(mxra[x]==0){
cout<<"sb"<<endl;
return 0;
}*/
int ret=work(x,l,r,maxd);
maxd=max(mxra[x],maxd);
return ret;
}
if(l==r){
//cout<<"sb"<<endl;
return 0;
}
int mid=l+r>>1,ret=inf;
if(pos>mid)ret=min(ret,query(rs,mid+1,r,pos));
ret=min(ret,query(ls,l,mid,pos));
return ret;
}
#undef ls
#undef rs
}xds;
int dp[N];
signed main(){
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d",&p[i]);
for(re i=1;i<=n;i++)scanf("%d",&c[i]);
xds.build(1,1,n);
//cout<<"finish build"<<endl;
for(re i=1;i<=n;i++){
maxd=0;
int tmp=xds.query(1,1,n,p[i]-1);
if(tmp==inf)dp[i]=c[i];
else dp[i]=tmp+c[i];
xds.ins(1,1,n,p[i],i,dp[i]);
//cout<<"finish "<<i<<" "<<dp[i]<<endl;
}
//cout<<"finish insert"<<endl;
maxd=0;
printf("%d",xds.query(1,1,n,n));
}
但是吧，这个题目亲测，假复杂度的线段树比均摊复杂度的线段树快多了，快一倍
假复杂度：\(1806ms\)
均摊复杂度：\(4198ms\)
·
\(T3\;Lost\,My\,Music\)
真的，这个题我只会打暴力，而且是极其丑的暴力几乎接近\(O(n^2)\)说白了就是硬往上跳
看完题解之后，我一直在犹豫，我是维护上凸包，还是下凸包啊，咱也不知道，就去手摸
后来我发现，上下两个变量所属的点要是对应的，不对应的话，根本求不了斜率，我们就要先对式子进行化简
\(\huge\frac{C_v-C_u}{dis(u,v)}=\frac{C_v-C_u}{dep_u-dep_v}=-\frac{C_u-C_v}{dep_u-dep_v}\)
这样我们就成功的将原始式子转换成了一个可以用凸包来维护的东西
我们发现，这个dep还是天然递增的，这就非常的不错，直接往后加就完事了
这个出题人有点狗，他故意卡你暴力弹栈，所以你必须使用数组模拟栈，而且要二分的去弹，二分找到那个应该弹出的点
二分的时候，注意一下你找到的到底是应该弹出的第一个点还是留在栈里的最后一个点
你还发现这是一棵树，回溯的时候需要把之前弹出去的都压回来，
所以我们就在弹出去的时候记录一下弹的是啥，然后在给装回来就行了，反正是数组，怎么搞都没问题
你要是非得用\(stack\)，那也没人能救你了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=5e5+5;
int n;
struct POT{
double x,y;
}sca[N],sta[N],clear;
int to[N],nxt[N],head[N],rp;
double ans[N];
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int get_mid(int x,int y){
int l=1,r=y;
while(l<r){
int mid=l+r+1>>1;
double tmp=(sta[mid].y-sta[mid-1].y)/(sta[mid].x-sta[mid-1].x);
double now=(sca[x].y-sta[mid-1].y)/(sca[x].x-sta[mid-1].x);
if(mid==1||now-tmp>0)l=mid;
else r=mid-1;
}
ans[x]=(sca[x].y-sta[l].y)/(sca[x].x-sta[l].x);
//cout<<sca[x].y<<" "<<sta[l-1].y<<endl;
//printf("%d %d %.10lf\n",x,l,ans[x]);
return l;
}
void dfs(int x,int y){
int now=1;
POT ji;
//cout<<x<<" "<<y<<" "<<sca[x].x<<endl;
if(y){
now=get_mid(x,y);now++;
}
//cout<<x<<" "<<y<<" "<<now<<" "<<sca[x].x<<endl;
ji=sta[now];
sta[now]=sca[x];
for(re i=head[x];i;i=nxt[i]){
int v=to[i];
sca[v].x=sca[x].x+1;
dfs(v,now);
}
sta[now]=ji;
}
signed main(){
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%lf",&sca[i].y);
for(re i=2,x;i<=n;i++)scanf("%d",&x),add_edg(x,i);
sca[1].x=1.0;dfs(1,0);
for(re i=2;i<=n;i++)printf("%.10lf\n",-ans[i]);
}
思路确实很恶心，看到可持久化栈的时候人都傻了，但其实代码只有这么短