HLOJ-DAY 8

Posted on By 张, 高畅 HLOJ-DAY 8无评论

我真的尽力了啊
继令人感伤的红雨后，又一道调不出的题出现了——音质检测。
现已加入首页题单，有缘再见。
都怪这个音质检测害我没时间打DP优化

[A]

原题
终于是做过的了。
其实就是如果可以一次更新多个的可以使用倍增优化。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int>PLI;
const int N=100005,M=17;
const LL INF=1e12;
int n,h[N],ga[N],gb[N],f[M][N][2],da[M][N][2],db[M][N][2];
void initg()
{
    set<PLI>S;
    S.insert({INF,0});
    S.insert({INF+1,0});
    S.insert({-INF,0});
    S.insert({-INF-1,0});
    for(int i=n;i;i--)
    {
        PLI t(h[i],i);
        auto j=S.lower_bound(t);
        j++;
        vector<PLI>cand;
        for(int k=0;k<4;k++)
        {
            cand.push_back(*j);
            j--;
        }
        LL d1=INF,d2=INF;
        int p1=0,p2=0;
        for(int k=3;k>=0;k--)
        {
            LL d=abs(h[i]-cand[k].first);
            if(d<d1)
            {
                d2=d1;
                d1=d;
                p2=p1;
                p1=cand[k].second;
            }
            else if(d<d2)
            {
                d2=d;
                p2=cand[k].second;
            }
        }
        ga[i]=p2;
        gb[i]=p1;
        S.insert(t);
    }
}
void initf()
{
    for(int i=0;i<M;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!i)f[0][j][0]=ga[j],f[0][j][1]=gb[j];
            else
            {
                for(int k=0;k<2;k++)
                {
                    if(i==1)f[1][j][k]=f[0][f[0][j][k]][1-k];
                    else f[i][j][k]=f[i-1][f[i-1][j][k]][k];
                }
            }
        }
    }
}
int get_dist(int a,int b){return abs(h[a]-h[b]);}
void initd()
{
    for(int i=0;i<M;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!i)
            {
                da[0][j][0]=get_dist(j,ga[j]);
                da[0][j][1]=0;
                db[0][j][1]=get_dist(j,gb[j]);
                db[0][j][0]=0;
            }
            else
            {
                for(int k=0;k<2;k++)
                {
                    if(i==1)
                    {
                        da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
                        db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];
                    }
                    else
                    {
                        da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
                        db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
                    }
                }
            }
        }
    }
}
void get_res(int p,int x,int &la,int &lb)
{
    la=lb=0;
    for(int i=M-1;i>=0;i--)
    {
        if(f[i][p][0]&&la+lb+da[i][p][0]+db[i][p][0]<=x)
        {
            la+=da[i][p][0];
            lb+=db[i][p][0];
            p=f[i][p][0];
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    initg();
    initf();
    initd();
    int x,res=0,Maxh=0;
    double Minratio=INF;
    scanf("%d",&x);
    for(int i=1;i<=n;i++)
    {
        int la,lb;
        get_res(i,x,la,lb);
        double ratio=lb?(double)la/lb:INF;
        if(ratio<Minratio||ratio==Minratio&&h[i]>Maxh)
        {
            Minratio=ratio;
            Maxh=h[i];
            res=i;
        }
    }
    printf("%d\n",res);
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int p,x,la,lb;
        scanf("%d%d",&p,&x);
        get_res(p,x,la,lb);
        printf("%d %d\n",la,lb);
    }
    return 0;
}

[B]

原题

不是大哥们手下留情啊，您们过了不代表我们可以过。
限制成100ms什么意思啊，让我手写取模？？
设 $dp{i,j}为已经匹配到s2的第i位，再走完2^j个s1，能新匹配s2的字符数。
转移：dp{i,j}=dp{i,j-1}+dp{(i+dp_{i,j-1})mod|s1|,j−1}$

$ $

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[105][105];
char s1[105],s2[105];
int n1,n2;
LL work()
{
    for(int i=0;i<strlen(s1);i++)
    {
        int pos=i;
        f[i][0]=0LL;
        for(int j=0;j<strlen(s2);j++)
        {
            LL cnt=0;
            while(s1[pos]!=s2[j])
            {
                pos=(pos+1)%strlen(s1);
                if(++cnt>=strlen(s1))return 0;
            }
            pos=(pos+1)%strlen(s1);
            f[i][0]+=cnt+1;
        }
    }
    for(int j=1;j<=30;j++)
    {
        for(int i=0;i<strlen(s1);i++)f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%strlen(s1)][j-1];
    }
    LL x=0,res=0;
    for(int k=30;k>=0;k--)
    {
        if(x+f[x%strlen(s1)][k]<=strlen(s1)*n1)
        {
            x+=f[x%strlen(s1)][k];
            res+=1<<k;
        }
    }
    return res/(LL)n2;
}
int main()
{
    while(scanf("%s %d\n%s %d",s2,&n2,s1,&n1)==4)printf("%lld\n",work());
    return 0;
}

[C]

原题
体感上最容易理解的一题。
首先写出暴力方程 $fi=\max(f{i-1},max_{k}{f_k+i-k}(s_i \geq s_k))但是这样是O(n^2)的，并不好过。
因此我们稍稍把二式变形，写成f_k-k+i的形式。
那么我们可以用某种数据结构维护f_k-k，这样就可以提高转移速度了。
很显然，能够单点修改，区间查询的东西毫无疑问可以是线段树。
因此，我们把s_i当成线段树下标，每次更新f_i后，同步更新f_i-i需要注意可能s_i$ 不是正数，因此可能需要离散化/提前预留下标。
CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long LL;
int n,cnt;
LL f[N],s[N];
LL tr[N<<2];
vector<LL>V;
unordered_map<LL,int>mp;
void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]=-1e12;
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    tr[u]=max(tr[u<<1],tr[u<<1|1]);
}
void modify(int u,int l,int r,int x,LL v)
{
    if(l==r)
    {
        tr[u]=v;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(u<<1,l,mid,x,v);
    else modify(u<<1|1,mid+1,r,x,v);
    tr[u]=max(tr[u<<1],tr[u<<1|1]);
}
LL query(int u,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return tr[u];
    int mid=l+r>>1;
    LL res=-1e12;
    if(L<=mid)res=max(res,query(u<<1,l,mid,L,R));
    if(mid<R)res=max(res,query(u<<1|1,mid+1,r,L,R));
    return res;
}
int main()
{
    scanf("%d",&n);
    V.push_back(0);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
        V.push_back(s[i]);
    }
    sort(V.begin(),V.end());
    V.erase(unique(V.begin(),V.end()),V.end());
    for(int i=0;i<V.size();i++)
    {
        if(!mp[V[i]])mp[V[i]]=++cnt;
    }
    build(1,1,cnt);
    modify(1,1,cnt,mp[0],0);
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1];
        f[i]=max(f[i],query(1,1,cnt,1,mp[s[i]])+i);
        modify(1,1,cnt,mp[s[i]],f[i]-(LL)i);
    }
    printf("%lld",f[n]);
    return 0;
}
训练日志

发表回复