2018.2.22 数据结构

考试

本次考试排名:Rank12
本次考试题目推荐:崎岖的山路(左偏树)
一如既往的细节炸因而要注意细节(具体参见T1心路历程)
还暂未更正T2(明天学吧)

1.勇斗恶龙

题面描述

D国受到了一条恶龙的袭击,为了保卫人民的生命财产安全,D国第一勇士盾盾挺身而出,与这条恶龙决一死战.这个战斗的过程可以看成由n个回合组成,对于每一个回合,盾盾先行动,恶龙再行动.战斗一开始时,盾盾有$A$点血,恶龙有$B$点血.盾盾有3个技能:
$ATTACK$:盾盾会向恶龙发起进攻,对恶龙造成$X$点伤害
$DEFEND$:盾盾该回合能处于绝对防御状态,这回合中恶龙无法对盾盾造成伤害
$HEAL$:盾盾能瞬间恢复$Y$点血而恶龙每一回合都只会向盾盾直接发起进攻,第$i$回合造成的伤害为$C_i$。一旦盾盾或是恶龙的血量小于或等于0了,他就会立即死亡.
可以看出,这场殊死搏斗中,盾盾与恶龙对战的策略是非常重要的,所以你需要帮盾盾设计一个最优的方案:如果盾盾能在$n$回合内战胜恶龙,你就要找出最少的回合;而如果无论如何盾盾都不能在$n$回合内战胜恶龙(盾盾是可能战死沙场的),你就需要算出盾盾能对恶龙造成的最大伤害值。

数据范围

对于 50%的数据,n<=10000,A,B<=5000,ci,X,Y<=200
对于 100%的数据,n<=100000,A,B<=1000000000,ci,X,Y<=10000

心路历程

第一眼便觉得是堆，然后纠结了十分钟血量能否超过上限，又花了十分钟打完，又花了十分钟打拍，结果只拍了是否"Win"or"Lose"，具体血量搞错了，WA成30分，早知道不死刚第二题，还不如多花些时间去搞第一题的细节,这不知是第n遍细节挂了，打成t=max(Y-c[i],c[i])

解法

由于要对龙造成最大伤害，所以我们要不必对自己的剩余血量太担心，先全力向恶龙进攻。而如果你还没把龙弄死你就挂了，这个时候我们其实是可以让“时光倒流”的——主动权在我们手上不是？这个时候我们就需要考虑要抵消之前的某一些回合的伤害直到让自己复活才行，比方说对于之前的第i回合，我们不去Attack恶龙了，改为进行防御性操作，我们能defend掉龙喷我们的a[i]点血，或是heal自己Y点血，而显然在要这两者之中选个大的作为我们的选择。如果我们到了第i回合后，自身血量小于或等于0了，我们就需要在之前的所有回合中选一个能回最多血的回合，然后让“时光倒流”，让我们的勇士在那个回合改为做相应的回复操作，如此重复直到血量大于0，而这个取最大值的操作可以用堆来实现。综上，我们就可以这样得到答案了。

好了，上代码

for(rg int i=1;i<=n;i++)
{
    rg ll t=Y,now;
    s2+=X;
    if(s2>=B)
    {
        puts("Win");
        cout<<i<<endl;
        return 0;
    }
    else
    {
        t=max(Y,c[i]);//原本是t=max(Y-c[i],c[i])，然后炸了
        atk.push(t);
        if(!atk.empty())now=atk.top();
        if(s1+c[i]>=A)
        {
            if(s1-now+c[i]>=A)
            {
                puts("Lose");
                ans=max(ans,s2);
                cout<<ans<<endl;
                return 0;
            }
            else
            {
                s1+=c[i]-now;
                ans=max(ans,s2);
                s2-=X;
                atk.pop();
            }
        }
        else
        {
            s1+=c[i];
        }
    }
    ans=max(ans,s2);
}

2.崎岖的山路

题面描述

哲哲非常喜欢登山."会当凌绝顶,一览众山小"的快感,哲哲一直向往着。但是,登山是一件非常累人的事情,崎岖的山路尤其摧残人的体力。因此,哲哲日思夜想,希望能将崎岖的山路改造得平坦些。终于有一天,一位叫耀耀的神仙受到了哲哲的感 召,找到了哲哲,表示愿意帮忙,用他的神力来改造山路。为了简化问题,我们可以将山路看成是由连续的$n-1$条线段构成的,那么就会有$n$个转折点,每个点的高度为 $a_i$,大仙可以用他的神力将任意一个点的高度改为任意高度.爬山自然是要往上爬的,哲哲不希望爬着爬着突然往下走,即哲哲需要设计一个改造方案b,对于 任意的$i$,不存在$j>i$使得$b_j\le b_i$.改造山路是十分费力气的:对于一个方案,它需要消耗大仙的精气值为

$$\sum_{i=1}^{n}|a_i-b_i|$$

数据范围

对于 70%的数据,$n\le 2,000$
对于 100%的数据,$n\le 100,000$
$0\le a_i \le 1,000,000,000$

解法

70分离散化+dp搞一搞(有闲情雅致的话可以滚掉第一维)
当然也可以跑个最小费用最大流啊
100分左偏树，利用中位数思想合并若干块堆

70分代码

for(rg int i=1;i<=n;i++)b[i]=read(),a[i]=(hand){b[i],i};
sort(a+1,a+1+n,cmp);
memset(f,63,sizeof(f));
rg int op=0;
for(rg int i=1;i<=n;i++)
    f[op][i]=abs(b[a[i].id]-b[n]);
for(rg int i=n-1;i>=1;i--)
{
    rg ll t=1e18;
    for(rg int j=n;j>=1;j--)
    {
        t=min(t,f[op][j]);
        f[op^1][j]=t+abs(b[a[j].id]-b[i]);
    }
    op^=1;
}
for(rg int i=1;i<=n;i++)
    ans=min(ans,f[op][i]);

AC代码

3.线路铺设

题面描述

经过台长哲哲的不懈努力,艰苦奋斗,QZTV已经成长壮大为国际大电视台了。最近, QZTV 刚刚打入D国市场,哲哲打算将QZTV的信号传至D国的n个城市中,每个城市的 人数为$w_i$,但由于D国内没有QZTV的相关线路,所以现在哲哲需要铺设一些线路来将信号传输至这n个城市。
由于城市之间的地理状况不尽相同,所以铺设费用也有所不同。QZTV设在D国的总信号站处于1号城市,即信号源是1号城市,除1号城市外的所有城市的信号需要由一线路从总信号站传输过来。哲哲经过综合分析评估,设计了m条备选线路,每条路线包含3个信息:$a_i$,$b_i$,$c_i$,表示这条线路中由$a_i$城市向$b_i$城市传输信号的单位费用为$c_i$。每条线路的负荷量为信号需要经过这条线路的城市的人数和,铺设一条线路的最终费用这条线路的(单位费用)*(负荷量)总的铺设费用为所有线路的费用之和。
哲哲希望每个城市都能接收到信号,同时他也希望总的铺设费用最少,你需要求出这个最少的铺设费用。如果不存在一个方案能使每个城市都接收到信号,输出“No Answer”(不含引号)。

数据范围

对于 30%的数据,$n\le 100$,$m\le 10000$
对于 100%的数据,$n\le 50000$,$m\le 100000$
$\sum w_i$、$\sum c_i$不超过maxlongint,可能存在两个城市之间有多条备选线路

解法

首先容易想到最优的情况下选出来的边会形成一棵以1为根的“有向生成树”直接计算原题中的和式有难度，所以我们考虑每条点权会被算几次，容易发现i号点会被算从源点到i的路径长度次，即原和式转化为
$\sum (Dis_i*a_i)$，所以只要从1号点求一次单源最短路即可得到答案

spfa();
for(rg int i=1;i<=n;i++)
{
    if(dis[i]!=dis[0])ans+=dis[i]*peo[i];
    else {puts("No Answer");return 0;}
}

OK，今天的题目于2.22搞完总结了，以后一定要坚持!(以后一定要注意细节啦)