【Fortuna OJ】10/15 Contest / 题解

Zepto -

Assassin’s Creed

题目描述

故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊心动魄、扣人心弦的探险和刺杀。

这次的故事就是他暗杀一位作恶多端的红衣主教。红衣主教可以吸取他周围人的生命力量，而他的红衣教徒也拥有这个力量。红衣主教的家是一个 $x*y$ 的长方形房间，也就是说，他的家的四个角坐标分别为$(0,0)(x,0)(0,y)(x,y)$。教堂的门在 $(0，0) $,而红衣主教就在 $(x,y)$ 的卧室休息。他的家中还有 $n$ 个守护着他的红衣教徒，站在 $(a_i,b_i)$。Ezio 想要趁主教休息时，从门进入潜入到他的卧室刺杀他，因为主教休息时会脱下红衣，这样吸取生命的力量就消失了。可是守卫他的红衣教徒依然很危险，离红衣教徒太近就会被吸取生命。因此，Ezio 想知道，在能刺杀主教的前提，从门到他的卧室的路上，他最远和离他最近的红衣教徒保持多远的距离。注意：教徒都在房间里。

思路

将每对教徒之间和教徒到房间边缘的边排序，依次加入并查集，直到房间的左上部分和右下部分联通，此时加入的边长度的一半即为答案。

代码

#include 
#define maxm 5000100
#define maxn 2010
#define ld double
using namespace std;
struct Edge{
    int from,to;
    ld dis;
    Edge(int a=0,int b=0,ld c=0){
        from=a,to=b,dis=c;
    }
    bool operator < (const Edge &x) const{
        return dissiz[fy])
    fa[fy]=fx,siz[fy]+=siz[fx];
    else fa[fx]=fy,siz[fx]+=siz[fy];
}
int main(){
    ld xx,yy,tx,ty;
    scanf("%lf%lf%d",&xx,&yy,&n);
    for (register int i=1;i

Darksoul

题目描述

oi_juruo热爱一款名叫黑暗之魂的游戏。在这个游戏中玩家要操纵一名有 点生命值的无火的余灰在一张地图中探险。地图中有n个篝火（也就是存档点）。在篝火处休息可以将生命值恢复满。每个篝火都会向其他篝火的其中之一连有一条通道（显然，通道是双向的），这些篝火之间都相互可达。也就是说，这是一张n个点，n条边的无向连通图。每条通道里都有一些怪物，经过oi_juruo的分析，他得到了每条边的怪物会对他造成的伤害值 .为了向oier们表演他高超的游戏技巧，他要从任意一个篝火跑到任意另一个篝火而不在之间的篝火休息，在此期间，他会和他经过的通道中的怪物战斗并损失 的生命值。现在oi_juruo想知道，他的生命值 至少为多少，才能完成任意一条旅途。oi_juruo并不傻，他会走最安全的路。

思路

求基环树直径。先暴力找出环，对于环上每个点 DFS 求这条枝杈上的直径和到这点的最长路径。最后的问题是在一个环上，每个点有权值，选出距离不超过环长度一半的点对，使其距离和权值之和最大。满足决策单调性，用单调队列 DP 即可。

特别地，此题可能出现自环和重边。对于自环直接舍去，对于重边，取两边最小值，然后求树的直径。

代码

//这份代码里没有判重边。。。

#include 
#define maxn 1000010
#define ll long long
using namespace std;
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1; static char buf[in_len],*s,*t; return (s="=t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;" } template  inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
struct Edge{
    int to,next;
    ll val;
    Edge(int a=0,int b=0,ll c=0){
        to=a,next=b,val=c;
    }
}l[maxn<<1]; int vis[maxn],rig[maxn],pre[maxn],head[maxn]; n,cnt="1,riz,jum[maxn];" inline void add(int a,int b,int c){ l[++cnt]="Edge(b,head[a],c);head[a]=cnt;" } set_rig(int u){ rig[u]="1,riz++;" if (!rig[pre[u]]) set_rig(pre[u]); bool find_rig(int u,int f){ (vis[u]){set_rig(u);return 1;} vis[u]="1;" for (int i="head[u];i;i=l[i].next){" v="l[i].to;" (v="=f)" continue; pre[v]="u,jum[v]=l[i].val;" (find_rig(v,u)) return 1; 0; ll f[maxn],g[maxn],inside[maxn],ans; len[maxn],prf[maxn],totlen; q[maxn],ql,qr; tree_find(int fa){ (register tree_find(v,u); (f[v]+l[i].val>f[u])
            g[u]=f[u],f[u]=f[v]+l[i].val;
        else if (f[v]+l[i].val>g[u])
            g[u]=f[v]+l[i].val;
        inside[u]=max(inside[u],max(inside[v],f[u]+g[u]));
    }
}
inline void print(ll x){
    if (!x) return;
    print(x/10);
    putchar('0'+x%10);
}
int main(){
    io>>n;
    bool flag=1;
    for (register int i=1,tx,ty;i<=n;++i){ ll v; io>>tx>>ty>>v;
        if (tx==ty) {flag=0;continue;}
        add(tx,ty,v);
    }
    if (flag) find_rig(1,0);
    else rig[1]=1;
    for (register int i=1;i<=n;++i) if (rig[i]){ rig[i]="0,tree_find(i,0),vis[i]=0," (!flag) break; } (!flag){ print(ans+1); return 0; for (int i="1;i<=n;++i)" int tot="0;" while(!vis[i]){ vis[i]="1;" len[++tot]="f[i];" prf[tot]="jum[i];" totlen="jum[i];" (register>0;--i)
        prf[i]+=prf[i+1];
    for (register int i=riz;i>=1;--i)
        prf[i]-=prf[i-1];
    prf[1]=0;
    for (register int i=1;i<=riz;++i) prf[i]*="-1,prf[i]+=prf[i-1];" totlen+="prf[riz];" for (register int i="1;i<=riz;++i)" len[i+riz]="len[i]," prf[i+riz]="prf[i]+totlen;" ql="1,qr=1;q[1]=1;" while(ql<="qr&&prf[i]-prf[q[ql]]">totlen/2) ql++;
        ans=max(prf[i]-prf[q[ql]]+len[i]+len[q[ql]],ans);
        while(ql<=qr&&len[i]-prf[i]>len[q[qr]]-prf[q[qr]]) qr--;
        q[++qr]=i;
    }
    print(ans+1);
}

Portal

题目描述

8102年，Normalgod 在 GLaDOS 的帮助下，研制出了传送枪。但 GLaDOS 想把传送枪据为己有，于是把 Normalgod 扔进了一间实验室。这间实验室是一棵有 n 个节点的树。现在 Normalgod 在一号节点，出口也在一号节点，但为了打开它，必须经过每一个节点按下每个节点的开关，出口才能打开。 GLaDOS 为了杀死 Normalgod，开始在实验室里释放毒气，因此 Normalgod 必须尽快逃出这间实验室。

当然，Normalgod 手中的传送枪是可以使用的。传送枪可以发射出两个颜色不同的传送门。Normalgod 可以从其中一个传送到另一个。尽管传送枪可以在视野范围内的任何一个经过特殊处理的表面打开一扇传送门，但这间实验室的设计使得 Normalgod 只能在他所处的房间内打开一个传送门。 在已经存在了一个同颜色的传送门时，打开新的传送门会使与它同颜色的旧门消失。传送和打开传送门所需时间为0。

显然，利用传送枪会让 Normalgod 更快解决谜题，可 Normalgod 死在了按下最后一个按钮的路上。尽管如此，GLaDOS 还是很想知道到底 Normalgod 最快能用多久逃出去，这对她的实验室设计方法论有重要的指导作用。作为 GLaDOS 的算法模块，你要完成这个任务。

代码

#include 
#define ll long long
#define maxn 1000100
using namespace std;
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1; static char buf[in_len],*s,*t; return (s="=t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;" } template  inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
struct Edge{
    int to,next,val;
    Edge(int a=0,int b=0,int c=0){
        to=a,next=b,val=c;
    }
}l[maxn<<1]; int head[maxn],cnt,n; ll mx[maxn][2],ans; void add(int a,int b,int c){ l[++cnt]="Edge(b,head[a],c);" head[a]="cnt;" } dfs(int u,int f){ for (int i="head[u];i;i=l[i].next){" v="l[i].to;" if (v="=f)" continue; dfs(v,u); mx[u][0]+="max(mx[v][0],mx[v][1]+(ll)l[i].val);" mx[u][1]="max(mx[u][1],mx[v][1]+(ll)l[i].val);" main(){ io>>n;
    for (int i=1,a,b,c;i>a>>b>>c;
        Add(a,b,c),Add(b,a,c);
        ans+=2ll*c;
    }
    dfs(1,0);
    printf("%lld",ans-mx[1][0]);
}