【NOIP2018模拟赛】

A. 【NOIP2018模拟赛】刺客信条（AC）

这道题第一眼看上去可能会想到找路径然后算距离，但发现这是不现实的。

所以我们通过限定答案的值来判断是否满足。

将答案设为 r （半径） ，每个棋盘上的点都由半径做圆，然后判断路径不触碰到圆的最大半径。

我们利用并查集将每个圆与墙进行处理，然后通过二分答案进行判断。

p.s. 记得要加eps （一个极小的数，调整精度）

#include<bits/stdc++.h>
using namespace std;
typedef double db;

const db e=1e-4;
const int N=2011;
int n,m,k,fa[N];
db x[N],y[N],dis[N][N];

int getf(int x){
    if(fa[x]==x) return x;
    else return fa[x]=getf(fa[x]);
}

void exchange(int x,int y){
    fa[getf(x)]=getf(y);
}

db two(db a){
    return a*a;
}

db d(int i,int j){
    return sqrt(two(x[i]-x[j])+two(y[i]-y[j]));
}

bool pd(double r){
    for(int i=1;i<=k+4;i++) fa[i]=i;
    for(int i=1;i<=k;i++){
        if(r-x[i]>e) exchange(k+1,i);//左墙 
        if(r-y[i]>e) exchange(k+2,i);//底墙 
        if(r-(n-x[i])>e) exchange(k+3,i);//右墙 
        if(r-(m-y[i])>e) exchange(k+4,i);//顶墙 
        for(int j=i+1;j<=k;j++){
            if(r*2-dis[i][j]>e || (fabs(r*2-dis[i][j])<e)) exchange(i,j);
        } 
    }
    if(getf(k+1)==getf(k+2)) return true;
    if(getf(k+1)==getf(k+3)) return true;
    if(getf(k+2)==getf(k+4)) return true;
    if(getf(k+3)==getf(k+4)) return true;
    return false;
}

int read(){
    int x=0,f=1;
    char s=getchar();
    while(!isdigit(s)) f*=(s=='-')? -1:1,s=getchar();
    do x=(x<<1)+(x<<3)+(s^48),s=getchar();
    while(isdigit(s));
    return x*f;
}

int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=k;i++){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k;j++){
            dis[i][j]=d(i,j);
        }
    }
    db l=0,r=1000000;
    while(r-l>e){
        db mid=(l+r)/2;
        if(pd(mid)) r=mid;
        else l=mid;
    }
    printf("%.2f",l);
    return 0;
} 

C. 【NOIP2018模拟赛】传送门 （portal）

一道树形dp的题。

设f[][]表示状态

f[x][0]：x和x的子树里没有传送门
f[x][1]：x和x的子树里有传送门

状态转移方程：
f[x][0]+=f[y][0]+2*w[i];

f[x][1]+=min(f[y][0]+w[i]-d[y],f[y][1]+w[i]*2);

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const long long null=1e15;

int n;
int head[MAXN],to[MAXN*2],next[MAXN*2],w[MAXN*2],cnt;
long long f[MAXN][2],d[MAXN];

void add(int u,int v,int l){
    cnt++;
    next[cnt]=head[u];
    to[cnt]=v;
    w[cnt]=l;
    head[u]=cnt;
}

void dp(int x,int fa){
    for(int i=head[x];i;i=next[i]){
        int y=to[i];
        if(y==fa)
            continue;
        dp(y,x);
        d[x]=max(d[x],d[y]+w[i]);
        f[x][0]+=f[y][0]+2*w[i];
        f[x][1]+=min(f[y][0]+w[i]-d[y],f[y][1]+w[i]*2);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,a;
        scanf("%d%d%d",&u,&v,&a);
        add(u,v,a);
        add(v,u,a);
    }
    dp(1,1);
    cout<<min(f[1][1],f[1][0]);
    return 0;
}

B. 【NOIP2018模拟赛】黑暗之魂(darksoul)

这是一颗环套树

题目要求的是这棵环套树的直径，再+1就是答案了。

我们把该环提出来，在上面操作。

那么直径要么是环上某点的子树内直径，要么是环上某两点子树内最长链再加一段环上路径。

子树内直径和最长链我们先算出来，剩下的就是如何求出环上两点使之匹配出来最大值。

枚举环上一点 i ，同时维护一个指针 j  往后指，表示从 i+1  到 j  是近一些，而 j 之后的点呢会绕环一圈来走回 i  更近一些。

那么 i+1  到 j的我们用一个单调队列来求最大值，绕一周的用一个后缀最大值算就好了。

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int tot=1,top,qx,qy,node;
ll ans,mx;
bool pd;
int first[N],nex[N<<1],en[N<<1],w[N<<1];
int st[N],dfn[N],d[N],len[N],col[N],q[N];
ll suf[N],pre[N],f[N];
bool bz[N];
inline int read(){
    int x=0,f=1;
    char s=getchar();
    while(!isdigit(s)) f*=(s=='-')? -1:1,s=getchar();
    do x=(x<<1)+(x<<3)+(s^48),s=getchar();
    while(isdigit(s));
    return x*f;
}
inline ll max(ll x,ll y)
{
    return x>y?x:y;
}
inline void in(int x,int y,int z)
{
    nex[++tot]=first[x];
    first[x]=tot;
    en[tot]=y;
    w[tot]=z;
}
void dfs(int x,int y)
{
    st[++top]=x;
    dfn[x]=top;
    for(int i=first[x];i && !pd;i=nex[i])
        if(i^y)
        {
            if(dfn[en[i]])
            {
                for(int j=dfn[en[i]];j<=top;j++)
                {
                    d[++d[0]]=st[j];
                    bz[st[j]]=true;
                }
                pd=true;
                return;
            }
            dfs(en[i],i^1);
        }
    top--;
}
void find(int x,int y,ll z,ll &num)
{
    if(z>num) num=z;
    for(int i=first[x];i;i=nex[i])
        if(en[i]^y && en[i]^x) find(en[i],x,z+w[i],num);
}
void get(int x,int y)
{
    if(y==d[0]) return;
    for(int i=first[x];i;i=nex[i])
        if(en[i]==d[y+1])
        {
            len[y]=w[i];
            get(en[i],y+1);
        }
}
void dg(int x,int y,ll z)
{
    if(z>mx) mx=z,node=x;
    col[x]=tot;
    for(int i=first[x];i;i=nex[i])
        if(en[i]^y && en[i]^x && !bz[en[i]]) dg(en[i],x,z+w[i]);
}
void dg1(int x,int y,ll z)
{
    if(z>mx) mx=z,node=x;
    for(int i=first[x];i;i=nex[i])
        if(en[i]^y && en[i]^x && col[en[i]]==tot) dg1(en[i],x,z+w[i]);
}
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        in(x,y,z);
        in(y,x,z);
    }
    dfs(1,0);
    tot=0;
    for(int i=1;i<=d[0];i++)
    {
        for(int j=first[d[i]];j;j=nex[j])
            if(!bz[en[j]]) find(en[j],d[i],w[j],f[i]);
        node=mx=0;
        tot++;
        dg(d[i],0,0);
        dg1(node,0,0);
        ans=max(ans,mx);
        if(f[i]>ans) ans=f[i];
    }
    get(d[1],1);
    for(int i=first[d[d[0]]];i;i=nex[i])
        if(en[i]==d[1])
        {
            len[d[0]]=w[i];
            break;
        }
    for(int i=2;i<=d[0];i++) pre[i]=pre[i-1]+len[i-1];
    for(int i=2;i<=d[0];i++) suf[i]=pre[d[0]]+len[d[0]]-pre[i]+f[i];
    for(int i=d[0]-1;i>1;i--) suf[i]=max(suf[i+1],suf[i]);
    int l=1,r=0;
    for(int i=1,j=1;i<d[0];i++)
    {
        while(l<r && q[l]<=i) l++;
        while(j<d[0] && pre[j+1]-pre[i]<=pre[d[0]]-pre[j+1]+len[d[0]]+pre[i])
        {
            j++;
            while(l<=r && f[q[r]]+pre[q[r]]<=f[j]+pre[j]) r--; 
            q[++r]=j;
        }
        ll num=0;
        if(j<d[0]) num=suf[j+1]+pre[i];
        if(i<j) num=max(num,f[q[l]]+pre[q[l]]-pre[i]);
        ans=max(ans,num+f[i]);
    }
    printf("%lld",ans+1);
    return 0;
}